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

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

Tags:

Modular Arithmetic

Elementary Number Theory

Related

Limits using L'Hopital's rule $\lim_{x\to0^+} (x^{x^x-1})$ Normal bundle to complete intersection in $\mathbb{P}^n$ How can I prove that $2^{\sqrt 7}$ is bigger than $5$? If $A$ and $B$ are normal such that $AB=0$, does it follows that $BA=0$? Different Applications of Sylow Theorems Continuous function that is uniformly continuous on a dense subset Easy way of memorizing or quickly deriving summation formulas Prove that matrix equation $AX-XA=I$ doesn't have a solution for any $A\in M_n(\mathbb{R})$ Intuitive or visual understanding of the real projective plane Show that a generalized knight can return to its original position only after an even number of moves How many possible phone words exist for a phone number of length N when also counting words less than length N within that phone number? If a matrix is triangular, is there a quicker way to tell if it is can be diagonalized?

Recent Posts