# Using Fermat's Little Theorem to find the smallest k for which $a ^k$≡ 1(mod 11) for a = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

We know that $$a^{11-1} ≡1\bmod{11}$$ for all positive integers $$a$$ less than $$11$$, by Fermat’s Little Theorem.

But $$(11 − 1)$$= $$10$$ is not the smallest k for which $$a ^k$$ ≡ 1(mod 11) for all such a.How do we find the smallest k for which $$a ^k$$$$1(mod 11)$$ for a = 1, 2, 3, 4, 5, 6, 7, 8, 9, 10.

$$[$$Examples: (i) $$3^5$$ ≡ 1(mod 11). Here k = 5 for a = 3. (ii)$$10^2$$$$1(mod 11)$$. Here k = 2 for a =10.$$]$$

How are the values of k related to $$(11 − 1)= 10?$$

• You pose this as if it is a homework problem, as you are commanding us to "find the smallest $k\ldots$". Can you tell us what you have done yourself on this question? For example, have you tried to answer it for $a = 1$, $2$, $3$, and $4$?
– KCd
Oct 14, 2020 at 13:28
• So far you have found $2$ and $5$. The relationship between these and $10$ is not difficult to guess. Oct 14, 2020 at 13:32
• $k$ is a factor of $10$. Are you familiar with primitive roots? Oct 14, 2020 at 13:32
• No am [email protected] Oct 14, 2020 at 13:32
• @user57048: see Bernard's answer below Oct 15, 2020 at 4:21

The multiplicative group $$\mathbf F^\times_{11}$$ is cyclic, so you can determine a generator of this group (i.e. a primitive root of unity in $$\mathbf F_{11}$$. It happens that (as is often the case) $$2$$ is such a generator:$$\DeclareMathOperator{\ord}{ord}$$
$$\begin{array}{|r|cccccccccc|} \hline n=& 1&2&3&4&5&6&7&8&9&10 \\\hline 2^n& 2 & 4 & 8 & 5 & 10 & 9 & 7 & 3 & 6 & 1 \\\hline \end{array}$$ For the orders of the other elements, write each of them as $$2^k$$ and use that the order of such an element is $$\ord(2^k)=\frac{\ord(2)}{\gcd(k,\ord 2)}.$$
• The problem is that many beginners compute non recursively the powers of all these elements, and lose time checking their calculations, whereas this way, it has to be done only for the small element $2$, and the rest is much less error-prone. Furthermore, if you're asked the list of all primitive elements, you have them instantly: they're given by the powers $k$ coprime to $10$. Oct 14, 2020 at 14:46
• @user57048: I computed by hand the powers of $2$ recursively (meaning that, for instance, once you have calculated that $2^4=5$, you deduce instantly that $2^5=2\cdot5$). As to your first question, the only fact that Fermat asserts is that the order of any element is a divisor of $\varphi(11)=10$. So when you compute the powers of an element, you really have to test only $2$ and $5$. Oct 15, 2020 at 9:20
EDIT: if you mean that the $$a$$ are independent of each other, then you are asking for a computation of multiplicative order, which is known to be a difficult problem. As far as I am aware, there is no direct formula for it.