1
$\begingroup$

For 1420172017 mod 60 I used a logarithm rule to solve it: 1420172017 mod 60 => lg(14) a = 20172017 In essence, I calculated 20172017 mod 60 = 37 (using Euler's Theorem). Then I used that result as a power of 14: 1437 mod 60 = 44.

I figured that the same principle would also apply to 2232.

So, first I tried to get the result of 232 mod 11. Since the point of this is not to use a calculator, I simplified the term using exponentation laws: 232 = 22 mod 11 * 230 11 = 4 * 1 = 4.

I checked the result and 232 mod 11 really is 4.

The problem appears during the next step: 24 mod 11 = 5. But 2232 mod 11 = 9. Therefore, my result is wrong.

$\endgroup$
3
$\begingroup$

Note that $2^{10}\equiv 1\pmod{11}$ (Fermat), hence if $2^{32}\equiv n\pmod{10}$, then $2^{2^{32}}\equiv 2^n\pmod{11}$.

So what is $2^{32}\bmod{10}$? Start by computing $2^{32}\bmod 5$. As $2^4\equiv 1\pmod 5$, clearly $2^{32}=(2^4)^8\equiv1\pmod 5$ as well. Of course $2^{32}$ is even, so (ultimately by the Chinese Remainder Theorem) $2^{32}\equiv6\pmod{10}$.

Thus we need only compute $2^6\equiv 64\equiv 9\pmod{11}$.

$\endgroup$
2
$\begingroup$

$\!\bmod 11\!:\,\ \underbrace{2^{\large 2^{\Large 32}}\!\!\equiv 2^{\large\color{#c00} 6}}_{\Large 2^{\Large\color{#0a0}{10}}\ \equiv\ 1}\,\ $ by $\ \overbrace{2^{\large 32}\!\bmod\color{#0a0}{10} = 2\underbrace{(2^{\large 31}\!\bmod 5)}_{\large 2^{\Large 4}\ \equiv\ 1}}^{\large ab\,\bmod\, ac\ \ =\ \ a(b\bmod c)\ \ \ }= 2(2^{\large 3}\!\bmod 5) = \color{#c00}6 $

$\endgroup$
  • $\begingroup$ Underbraced are by little Fermat, and overbrace is the mod Distributive Law. $\endgroup$ – Bill Dubuque Apr 30 at 15:14
  • $\begingroup$ And $2^6\cong9\pmod{11}$. $\endgroup$ – Chris Custer Apr 30 at 15:15
  • 1
    $\begingroup$ @Chris The point is to highlight the nontrivial aspects of the problem (so I purposely remove trivial parts that may obfuscate that). $\endgroup$ – Bill Dubuque Apr 30 at 15:17
0
$\begingroup$

The multiplicative order of $2$ mod $11$ is $10$, not $11$. So you want to compute $2^{32} \bmod 10$.

$\endgroup$
0
$\begingroup$

$2^5\equiv-1\pmod{11}$

Now $2^{31}=2\cdot4^{15}=2(5-1)^{15}\equiv\equiv2(-1)\equiv3\pmod5,$

$2^{31}=5a+3$(say for some integer $a>0$)

$2^{2^{32}}=(2^{2^{31}})^2=(2^{5a+3})^2=(2^5)^{2a}\cdot2^6\equiv(-1)^{2a}\cdot2^4\equiv2^6\pmod{11}\equiv?$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.