Fermat's Little theorem and least value of power

418 Views Asked by At

We know that ${13^{60}} \equiv 1\left( {\bmod 61} \right)$ as per Fermat's little theorem as $61$ is prime. $\left(\because {{a^{p - 1}} \equiv 1\left( {{\mathop{\rm modP}\nolimits} } \right)} \right)$

But ${13^{30}} \equiv 1\left( {\bmod 61} \right)$ also true.

I wonder, by using Fermat's little theorem, we get one possible value where the congruence is valid and How do I know there exist some other numbers lesser than $p-1$ exist?

1

There are 1 best solutions below

0
On

You are effectively asking about primitive roots modulo $61$. These are numbers $g$ for which $k=60$ is the smallest positive exponent giving $g^k \equiv 1 \bmod 61$. $2$ is an example.

Once a primitive root $g$ is available, raising that number to any exponent which has a common factor with $60$ (in this case; $p-1$ in general) will result in a number that is not a primitive root. Using $2$ as an example again, $2^{40} \equiv 13 \bmod 61$, and so of course $13^3 \equiv 2^{120} \equiv (2^{60})^2 \equiv 1^2 \equiv 1 \bmod 61$.