What is the remainder of $\frac{2^{2015}}{36}$?

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?

• +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). – Ethan Bolker Dec 7 '15 at 14:55
• This post might be useful for you. – Martin Sleziak Dec 7 '15 at 15:06

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}$$
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