# Number TheoryLeast residue

#### crypt50

##### New member
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
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
Thanks, a lot I didn't realize it was 3^2^15. Thanks for calling my attention to it.