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


`\frac{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


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