0
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$ – Teresa Lisbon Oct 8 '16 at 5:20
  • 1
    $\begingroup$ 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. $\endgroup$ – Joffan Oct 8 '16 at 5:36
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.