0
$\begingroup$

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?

2 Answers 2

3

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

3

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$

  • 0
    @labbhattacharjee What you had is/was correct, and would be the way I normally favor. I was just remarking that OP should seek to apply the basics first (as in my proof, or Andre's) instead of thinking that everything 'hard' has to be resorted to a fancy high power theorem. Sometimes thinking properly goes a long way.2012-12-29