Tips to find the minimum period of an exponential congruence

33 Views Asked by At

I have to find the minimum period of this congruence: $2^x \equiv 8\;(11)$ $$ 2^1 \equiv2,\;2^2 \equiv4,\;2^3 \equiv8,\;2^4 \equiv5,\;2^5 \equiv-1,\; 2^{10} \equiv1 $$

My question is: how do I know that it is not necessary to calculate the congurences from $2^6$ to $2^9$?

1

There are 1 best solutions below

2
On BEST ANSWER

You know by Fermat's little theorem that the period has to divide $10$, since $11$ is a prime. Since you worked out that $2^5\not\equiv1\bmod10$, this shows that the period cannot be strictly less than $10$, so it is $10$.