Welcome to our community

Be a part of something great, join today!

Number Theory Least residue

crypt50

New member
Jun 29, 2013
21
Compute the least residue of 3^215 (mod 65537) (65537 is prime).

I've tried to use Euler's theorem, Fermat's little theorem and Wilson's theorem, but nothing seems to work, please help.
 

chisigma

Well-known member
Feb 13, 2012
1,704
Compute the least residue of 3^215 (mod 65537) (65537 is prime).

I've tried to use Euler's theorem, Fermat's little theorem and Wilson's theorem, but nothing seems to work, please help.
The number 65537 is not a 'whatever prime', it is a Fermat's prime because is in the form $\displaystyle F_{n}= 2^{2^{n}}+1$. For a Fermat's prime the following holds...

$\displaystyle 3^{\frac{F_{n}-1}{2}} = -1\ \text{mod}\ F_{n}\ (1)$

For n=4 the (1) becomes...

$\displaystyle 3^{2^{15}} = -1\ \text{mod}\ 65537\ (2)$

In your post is written $\displaystyle 3^{215}$ and not $\displaystyle 3^{2^{15}}$... the question is: are You sure to have written correctly?...


Kind regards


$\chi$ $\sigma$
 
Last edited:

crypt50

New member
Jun 29, 2013
21
Thanks, a lot I didn't realize it was 3^2^15. Thanks for calling my attention to it.