6
$\begingroup$

I am unfamiliar with modular arithmetic. I am attempting to solve this problem as practice for mathleague competitions.

In an attempt to solve this problem, I first attempted to define what the remainder is by the following expression: $$2^{2015} - 36\left\lfloor{\frac{2^{2015}}{36}}\right\rfloor$$ Which can be simplified to... $$2^{2015} - 36\left\lfloor{\frac{2^{2013}}{9}}\right\rfloor$$ After that though, I didn't know what I should do. I thought about rewriting the original expression all in terms of $2^x$ like so... $$\frac{2^{2015}}{2^5+2^2}$$ Yet that still wasn't helpful.

This morning, I finally realized that $2^{k+dx}\mod36$, where $k$ and $d$ are constants, has a pattern that must repeat itself at some point since the result of the operation must be an integer greater than 0 and less than 36 (it has a finite set of possible results).

I know that 2015 is divisible by 5. And using a calculator I found out that... $$2^5\mod{36} = 2^{35}\mod{36}$ = 32$$ To test if I had found a solution, I verified that there was an integer solution to the following equation (plugging values in for $k$ and $d$ above): $$5 + 30x = 2015$$ And found that $x=67$, so therefore the remainder of $\dfrac{2^{2015}}{36}$ must be $32$.

Is there a faster and/or better approach to this particular problem or problems like these?

$\endgroup$
  • $\begingroup$ +1 for figuring this out on your own. And +1 for asking for a better way. If you're interested in math competitions you'd do well to learn the Euclidean algorithm and Euler's theorem (as in @Leg 's answer). $\endgroup$ – Ethan Bolker Dec 7 '15 at 14:55
  • 2
    $\begingroup$ This post might be useful for you. $\endgroup$ – Martin Sleziak Dec 7 '15 at 15:06
7
$\begingroup$

Since $\gcd(2,9) = 1$, we have from Euler's theorem, that $2^{\phi(9)} \equiv 1 \pmod{9} \implies 2^6 \equiv 1 \pmod{9}$

This gives us that $$2^{2010} \equiv 1 \pmod9 \implies 2^{2015} \equiv 2^5 \pmod9 \equiv 5 \pmod9$$

This means the only solutions can be $5,14,23,32 \pmod{36}$. Further, since $2^{2015}$ is divisible by $4$, the only possible solution is $$2^{2015} \equiv 32 \pmod{36}$$

$\endgroup$
  • $\begingroup$ I'm unfamiliar with euler's theorem, but I accepted your answer on account of that it gave me a theorem to research for solving future problems like these. $\endgroup$ – CaptainObvious Dec 7 '15 at 20:15
-1
$\begingroup$

not much familiar with modular division but surely can give simpler method $2015=13.31.5$ implying $\frac{2^{5}}{36}$ would yield same result as its one of the prime multiple of $2015$ now we can calculate $2^{5}=32$ so remainder when $32$ is divided by $36$ is $32$ . hope its clear

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.