Question

6 use fermat’s theorem to find a number x between 0 and 28 with x85 congruent to 6 modulo 29. (

Answer 1

If

$x^{85}\equiv6\mod29$

then we have

$\dfrac{x^{85}}6\equiv1\mod29$

By Fermat's little theorem, if $a$ is not divisible by a prime $p$, then

$a^{p-1}\equiv1\mod p$

This works for $x=6$; in this case, we would have

$\dfrac{6^{85}}6=6^{84}=\left(6^3\right)^{28}=\left(6^3\right)^{29-1}\equiv1\mod29$