# Fermat's Little theorem and least value of power

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?

• It's difficult to see when this happens. All we do know is that the least power will be a divisor of $P-1$, but we can't say anything more in the case of $a$ and $P$ being co prime. – Teresa Lisbon Oct 8 '16 at 5:20
• Actually $13^3 \equiv 1 \bmod 61$. A number $g$ for which $k=60$ is the smallest positive exponent giving $g^k \equiv 1 \bmod 61$ is a primitive root modulo $61$. $2$ is an example. – Joffan Oct 8 '16 at 5:36

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$.