3
$\begingroup$

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

$\endgroup$
8
  • 1
    $\begingroup$ 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$? $\endgroup$
    – KCd
    Oct 14, 2020 at 13:28
  • $\begingroup$ So far you have found $2$ and $5$. The relationship between these and $10$ is not difficult to guess. $\endgroup$
    – Henry
    Oct 14, 2020 at 13:32
  • 3
    $\begingroup$ $k$ is a factor of $10$. Are you familiar with primitive roots? $\endgroup$ Oct 14, 2020 at 13:32
  • $\begingroup$ No am [email protected] $\endgroup$
    – Pole_Star
    Oct 14, 2020 at 13:32
  • 1
    $\begingroup$ @user57048: see Bernard's answer below $\endgroup$ Oct 15, 2020 at 4:21

2 Answers 2

2
$\begingroup$

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

$\endgroup$
4
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Bernard
    Oct 14, 2020 at 14:46
  • 1
    $\begingroup$ How do I approach it if I am a beginner here. And how do I answer with Fermat's little theorem only.@Bernard. $\endgroup$
    – user57048
    Oct 15, 2020 at 4:27
  • $\begingroup$ meaning I want to know from where this table is derived from $\endgroup$
    – user57048
    Oct 15, 2020 at 4:54
  • $\begingroup$ @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$. $\endgroup$
    – Bernard
    Oct 15, 2020 at 9:20
1
$\begingroup$

You are seeking the Carmichael lambda function. The Wikipedia article shows how to compute this function using Euler's totient function and the lcm function.

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .