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
    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$.2012-12-29
  • 0
    @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.2012-12-29
  • 0
    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.2012-12-29
  • 0
    @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.2012-12-29
  • 0
    @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.2012-12-29
  • 0
    @CalvinLin: I strongly agree. Using Euler directly seems less "hands on" than using the factorization and working modulo prime powers. One needs the experience of working with "little" numbers.2012-12-29
  • 0
    @CalvinLin, how about the current version?2012-12-29
  • 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