6
$\begingroup$

I'm trying to calculate $2^{47}\pmod{\! 65}$, but I don't know how...

I know that: $65=5\cdot 13$ and that:

$2^{47}\equiv 3 \pmod{\! 5}$ and $2^{47}\equiv 7\pmod{\! 13}$... (I used Euler)

But how should I continue from here? (I saw at WolframAlpha that the result is 33, but I don't have any idea how to get it...)

I'd like to get any help...

Thank you!

$\endgroup$
7
  • $\begingroup$ What is $2^6$? How does that help? $\endgroup$ Jun 20, 2015 at 23:03
  • $\begingroup$ @Yoar, just to use fermat little theorem $\endgroup$ Jun 20, 2015 at 23:03
  • $\begingroup$ Hint: $65=64+1$ $\endgroup$
    – anon
    Jun 20, 2015 at 23:03
  • $\begingroup$ @whacka - but 65 is not prime... $\endgroup$
    – CS1
    Jun 20, 2015 at 23:04
  • 1
    $\begingroup$ but you can write it as sum of primes number such that :65=47+7+11 $\endgroup$ Jun 20, 2015 at 23:06

4 Answers 4

5
$\begingroup$

$\varphi(65)=(5-1)(13-1)=48$, so by Euler's theorem (since $(2,65)=1$):

$$2x\equiv 2\cdot 2^{47}\equiv 2^{48}\equiv 1\pmod{\! 65}$$

$$2x\equiv 66\stackrel{:2}\iff x\equiv 33\pmod{\! 65}$$

$\endgroup$
0
4
$\begingroup$

$2^6=64$, so $\,2^6\equiv -1 \pmod{\! 65}\,$ and $47=6\cdot 7+5$; then $2^{47}\equiv (2^6)^7\cdot 2^5\equiv (-1)^7\cdot 32\equiv -32 \equiv 33 \pmod{\! 65}$

$\endgroup$
2
$\begingroup$

You might find these two facts helpful. $$2^6 =64\equiv -1\ \ \pmod{65} $$ and $$(2^a)^b=2^{ab}$$

$\endgroup$
1
$\begingroup$

As $65=5\cdot13$ with $(5,13)=1,$

$2^6=64\equiv-1\pmod{13}$ and $2^6\equiv-1\pmod5$

$\implies2^6=64\equiv-1\pmod{13\cdot5}$

Now $47\equiv-1\pmod6\implies2^{47}\equiv2^{-1}\pmod{65}$

As $33\cdot2-65=1,2\cdot33\equiv1\pmod{65}\iff2^{-1}\equiv33$

$\endgroup$

Not the answer you're looking for? Browse other questions tagged .