0

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

Shyvert
  • 177

1 Answers1

0

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

Parcly Taxel
  • 103,344
  • So in general, if the module $p$ is prime, do I have to see only the exponents that divide $p-1$?

    For example: $4^x\equiv3;(13)$ $$p -1 = 12 \rightarrow1,2,3,4,6,12|12$$ $$ 4^1 \equiv4,;4^2 \equiv3,; 4^3 \equiv-1,;4^4 \equiv9,;4^6 \equiv1,; $$

     – Shyvert Apr 12 '20 at 14:32
  • @Shyvert Yes. This is just a special case of Lagrange's theorem on $\mathbb Z^×$. – Parcly Taxel Apr 12 '20 at 16:56