# Determine the remainder when $2^{1930}$ is divided by $840$

Determine $\Phi(840)$. Hence, determine the remainder when $2^{1930}$ is divided by $840$.

I determined $\Phi(840) = \Phi(2^3*3*5*7) = 480$, however I don't know how I can use this to solve the problem.

Since $\operatorname{gcd}(2, 840)$ is not $1$, how can I apply Euler's theorem which states if $n \geq 1$ and $\operatorname{gcd}(a, n) = 1$ then $a^{\Phi(n)}$ is congruent to $1 (\operatorname{mod} n)$?

Or is there a different approach to solving a problem like this?

-

Before you run, learn to walk (yes, even though running is fun).

Translation: Before you apply Euler's Theorem, apply Modulo Arithmetic (yes, even though Euler's Theorem seems all powerful to deal with these scenarios).

Like you mentioned, we know that $2^{1930} \equiv 0 \pmod{8}$. Hence, it remains to calculate the value of $2^{1930} \pmod{105}$. Once you have this value, use Chinese remainder theorem to calculate the value of $2^{1930} \pmod {840}$.

-

We can not apply Euler's Totient Theorem directly as $2,840$ are not relatively prime.

Let $2^{1930}=840r+s\implies s=8(2^{1927}-105r)\implies 8\mid s,s=8t$(say)

So, $2^{1927}\equiv t\pmod {105}$

Now we can safely apply Totient Theorem.

As $\phi(105)=\phi(3)\phi(5)\phi(7)=2\cdot4\cdot6=48\implies 2^{48}\equiv1\pmod{105}--->(1)$

In fact,we can potentially find some lower exponent $(e)$ of $2$ such that $2^e\equiv1\pmod{105}$ by applying Carmichael Function.

As $\lambda(105)=lcm(\lambda(3),\lambda(5),\lambda(7))$ $=lcm(\phi(3),\phi(5),\phi(7))=lcm(2,4,6)=12 \implies 2^{12}\equiv1\pmod {105}--->(2)$

So, $2^{1920}=(2^{48})^{40}\equiv1^{40}\pmod{105}=1$ by $(1)$

or $2^{1920}=(2^{12})^{160}\equiv1^{160}\pmod{105}=1$ by $(2)$

So in any case, $2^{1920}=1+105u$ for some integer $u$

$2^{1930}=2^{10}\cdot2^{1920}=2^{10}(1+105u)$ $\equiv2^{10}\pmod{2^{10}\cdot105}\equiv1024\pmod{2^{10}\cdot105}\equiv 1024\pmod{840}\equiv184$

Alternatively, $1927\equiv7\pmod {48}\equiv7\pmod {12}$

So, $2^{1927}\equiv 2^7\pmod {105}\equiv128\equiv 23$

So, $2^{1930}\equiv 2^3\cdot 23\pmod {840}\equiv 184$

-
Note: You didn't need to apply Carmichael, since Euler gives us $\phi(105) = 2 \times 4 \times 6 = 48$ and $1927 = 40 \times 48 + 7$. – Calvin Lin Dec 29 '12 at 13:12
@CalvinLin, in general it's always better to use Carmichael function as it allows us to play with smaller exponents. Admittedly, here it did not make any difference. – lab bhattacharjee Dec 29 '12 at 13:35
I agree with you in principle. My point was to flaming, that he should think of the basic ways to approach this problem, since he doesn't have it down solidly. Instead of trying to learn even more high powered different approaches. – Calvin Lin Dec 29 '12 at 13:49
@CalvinLin: Since $840=2^3\cdot 3\cdot 5\cdot 7$, we have $a^2\equiv 1\pmod{3}$ and so on. So $a^{12}\equiv 1\pmod{840}$. Perhaps Carmichael could have been mentioned after solution was given. – André Nicolas Dec 29 '12 at 15:41
@AndréNicolas Precisely! My point was that he should have learnt how to apply Modulo Arithmetic properly first. By being unable to solve this problem, he demonstrates that he doesn't think of modulo arithmetic in the prime power sense, which is (one of) the first thing you should be doing. – Calvin Lin Dec 29 '12 at 15:52