3

Is there any quick way to find $2^{37} \bmod 77$?

I have tried breaking it down into 2 components for example ..

$2^{37} \bmod 7$ and $2^{37} \bmod 11$ but still no luck.

Any ideas?

Thanks

Thomas Andrews
  • 177,126
bob tutpo
  • 51

5 Answers5

3

${\rm mod}\ \ \ 7\!:\,\ \color{#c00}{2^3\ \equiv\ 1}\,\ \Rightarrow\ 2^{37}\equiv 2(\color{#c00}{2^3})^{12}\equiv 2(\color{#c00}1)^{12}\equiv\,\color{#b70} 2$

${\rm mod}\ 11\!:\,\ \color{#c00}{2^5\equiv -1}\,\Rightarrow\, 2^{37}\equiv 2^2(\color{#c00}{2^5})^{7}\equiv 4(\color{#c00}{-1})^{7}\equiv\color{#0a0}{ -4}\,\Rightarrow\, 2^{37} = \color{#0a0}{11n\!-\!4},\,$ so by CRT

${\rm mod}\ 7\!:\,\ \color{#b70}2\equiv 2^{37}\equiv\color{#0a0}{11n\!-\!4}\equiv -3n\!+\!3\iff 3n\equiv 1\equiv-6\iff \color{#a0f}{n\equiv -2\equiv 5}$

Therefore $\quad\ \ 2^{27}\equiv 11\color{#a0f}n\!-\!4\equiv 11(\color{#a0f}{5\!+\!7k})-4\equiv 51+77k$

Remark $\ $ Per comments, we can compute the powers using only little Fermat as follows:

${\rm mod}\ \ \ 7\!:\,\ \ \color{#c00}{2^6 \equiv 1}\ \Rightarrow\ 2^{37}\equiv 2(\color{#c00}{2^6})^{6}\equiv 2(\color{#c00}1)^{6}\equiv\,\color{#b70} 2$

${\rm mod}\ 11\!:\,\ \color{#c00}{2^{10}\equiv 1}\,\Rightarrow\, 2^{37}\equiv 2^7 (\color{#c00}{2^{10}})^{3}\equiv 128(\color{#c00}{1})^3\equiv 11^2+7\equiv\color{#0a0}{7}$

Bill Dubuque
  • 272,048
  • Is this done with accordance to ferret theorem? – bob tutpo May 02 '15 at 22:53
  • @bob By little Fermat, mod odd prime $,p,,$ we have $,x \equiv 2^{(p-1)/2}\Rightarrow, x^2\equiv 2^{p-1}\equiv 1,,$ so $,x\equiv \pm1,,$ so it will be easy to compute powers of $,x.,$ But for such small $p$ we could also simply check small powers of $2$ till we reach $,\pm1,,$ so we don't need to know Fermat to proceed as above. – Bill Dubuque May 02 '15 at 23:02
  • @bob I added a remark which shows how to compute the powers using only little Fermat. – Bill Dubuque May 02 '15 at 23:14
  • Why did you cite CRT? Elementary manipulations is all that is used afterwards. – user26486 May 03 '15 at 11:57
  • @user31415 The method used is an algorithmic form of CRT, i.e. solve the first congruence, substitute its solution into the second congruence, solve that, etc. – Bill Dubuque May 03 '15 at 13:50
1

$2^5=32$ and $32^2=1024$, i.e. $2^{10}=1024$. Then $770+3\cdot77=770+231=1001$, so $2^{10}=1024-1001=23\mod 77$. Then $23^2=529$ and $77\cdot 7=11\cdot 49=539$, hence $2^{20}=23^2=529-539=-10\mod 77$. Then, $2^{30}=23\cdot(-10)=-230=-230+231=1\mod 77$. Thus $2^{37}=2^7\mod 77$ hence $2^{37}=128-77=51\mod 77$. This is also the answer that my computer gives me.

You could also take a look at wiki, Modular_exponentiation

Mirko
  • 13,445
1

The answers above are good, I am just posting a different way here.

Directly consider modulo 77. $2 \equiv 2, 2^2 \equiv 4, 2^4 \equiv 16, 2^8 \equiv 25, 2^{16} \equiv 9, 2^{32} \equiv 4$ (just do squaring modulo 77 for some time). Since $2^{37} = 2^{32+4+1}$, so we can have $2^{37} \equiv 4 \times 16 \times 2 \equiv 51 \mod 77$.

This method is relatively bad in this scenario, but it works well (can I say "the best"?) in general.

MonkeyKing
  • 3,178
  • Actually repeated squaring is rather efficient here. But it's not much help for learning how to use little Fermat or CRT, which presumably is the point of the exercise. – Bill Dubuque May 02 '15 at 23:24
  • @Bill Dubuque A good point indeed. Thanks for pointing out. – MonkeyKing May 03 '15 at 00:25
1

Carmichael function $\lambda(77)=30$

As $(2,77)=1,2^{30}\equiv1\pmod{77}\implies2^{37}=2^7\cdot2^{30}\equiv2^7\cdot1\pmod{77}$

Finally, $2^7\equiv51\pmod{77}$

lab bhattacharjee
  • 274,582
0

Hint: $2^3=8=7+1$ and $2^5=32=33-1=3\cdot11-1$. Using this, evaluate the remainders of $2^{37}$ when divided by $7$ and $11$, respectively. This will yield a Diophantine equation of the form $0\le7k+a=11n+b<77$, which is trivial to solve.

Lucian
  • 48,334
  • 2
  • 83
  • 154