MHB Finding the Least Residue of 3^215 (mod 65537)

[toni07]

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]

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$

 

[toni07]

Thanks, a lot I didn't realize it was 3^2^15. Thanks for calling my attention to it.