3
$\begingroup$

So I'm working through a textbook and the question asks:

Consider the prime $p =13$. For each divisor $d = 1,2,3,4,6,12$ of $12= p-1$, mark which of the natural numbers in the set $\{1,2,3,4,5,6,7,8,9,10,11,12\}$ have order $d$.

I know that the order is when: $$ a^n \equiv 1 \mod n$$ given $(a,n)=1$.

From my understanding, from Fermat's Little Theorem or an extension of Euler's Theorem, since $13$ is a prime and all the natural numbers in that set is relatively prime to $13.$ I can use the formula: $$ a^{\phi(n)} \equiv 1 \mod n $$, since $p$ is prime, I know $\phi(p)= p-1$, therefore $\phi(13)=12$.

Therefore all the orders of all the elements would be 12 not the other divisors. Is this line of reasoning correct or am I misunderstanding the question?

Thank you for any guidance.

$\endgroup$
4
  • 4
    $\begingroup$ the order of an element $a$ is the least positive integer $n$ such that $a^n\equiv1$ $\endgroup$ Aug 27, 2019 at 0:24
  • 2
    $\begingroup$ Consider the number 1. While $1^{12} \equiv 1$ mod $13$, $1^1 \equiv 1$ mod $13$ $\endgroup$ Aug 27, 2019 at 0:25
  • $\begingroup$ @ZacharyHunter I actually discovered that as well but couldn't find an example for the other numbers. $\endgroup$
    – fynmnx
    Aug 27, 2019 at 0:31
  • 1
    $\begingroup$ @Safder: for example $3^3=27=2\times13+1\equiv1\mod13$ $\endgroup$ Aug 27, 2019 at 1:13

4 Answers 4

5
$\begingroup$

The reasoning is off a little. You can only conclude the order of each element divides $12$.

Thus you still have to check the orders. Note: only $\varphi (12)=4$ of them will have order $12$. These are the so-called primitive roots mod $13$.

In fact, there will be $\varphi (d)$ elements of order $d$ for each $d$ dividing $12$.

$\endgroup$
4
  • $\begingroup$ Okay so in this case I should check if all the divisors and then pick the lowest one as the order. How would you go about this problem given a much larger number say $p=101$ then $\phi(101)$ has a large number of divisors? Also, could you further explain the last statement about the number of elements? $\endgroup$
    – fynmnx
    Aug 27, 2019 at 0:35
  • $\begingroup$ Yeah. It's well known in case $n$ is $1,2,4$, a power of an odd prime or twice a power of an odd prime, the multiplicative group $U(n)$ is cyclic. The statement about the number of elements of order $d$ can be understood by taking a generator, and considering what happens when you raise it to various powers. Recall that $g^k$ has order $\dfrac {\mid g\mid}{\operatorname {gcd}(\mid g\mid,k)}$. $\endgroup$
    – user403337
    Aug 27, 2019 at 0:50
  • 1
    $\begingroup$ For the first question, the better you are at modular arithmetic, the easier it will be. $\endgroup$
    – user403337
    Aug 27, 2019 at 0:54
  • $\begingroup$ Perfect, makes sense. A little beyond the scope of what I've learned thus far but I'll definitely look into it. Thanks! $\endgroup$
    – fynmnx
    Aug 27, 2019 at 1:00
3
$\begingroup$

If $a$ is a primitive root of $n$ where $\phi(n)=kd$, consider the order of $a^k$. Also consider $a^{mk}$ where $(m,d)=1$. Since by definition there are $\phi(d)$ numbers $m<d$ which satisfy this (by definition), we get $\phi(d)$ elements of order $d$. I leave the rigorous proof as an exercise.

$\endgroup$
3
  • $\begingroup$ Just to ensure my understanding of a primitive root is clear, a is a primitive root given then the order of a is $\phi(p) = p-1$. So for the case mentioned above, for 1 since the order is 1, it is not a primitive root. Am I correct? $\endgroup$
    – fynmnx
    Aug 27, 2019 at 0:49
  • 1
    $\begingroup$ yes, correct. $1 \equiv a^{\phi(n)}$ mod $n$ however, and $\phi(n) = \phi(n)\cdot 1$, so in a round about manner we can use this to conclude that 1 has order 1. $\endgroup$ Aug 27, 2019 at 0:52
  • $\begingroup$ Awesome, thank you. $\endgroup$
    – fynmnx
    Aug 27, 2019 at 1:00
0
$\begingroup$

You are wrong about the definition of the order of an element. In particular the order of a mod n is the smallest positive $k$ such that $a^k\equiv 1 mod(n)$.

For example the order of $3$ $mod(13)$ is $3$, in fact $3^3 \equiv 27 \equiv 1 mod(13)$ and $3^1 \equiv 3 mod(13)$, $3^2 \equiv 9 mod(13)$.

Another example is the order of $4$ $mod(13)$, that is $6$, in fact $4^6 \equiv 2^{12} \equiv 1 mod(13)$ and $4^1 \equiv 4 mod(13)$, $4^2 \equiv 3 mod(13)$, $4^3 \equiv 12 mod(13)$ and $4^4 \equiv 9 mod(13)$.

I can not check $4^5$ because the order of an element, mod n, certainly divided $\phi(n)$, in particular $5$ doesn't divided $\phi(13)=12$

$\endgroup$
2
  • 1
    $\begingroup$ Isn't $2^6 mod 13 = 12$ therefore how can it be the order because it is not congruent to the $1 mod 13$? $\endgroup$
    – fynmnx
    Aug 27, 2019 at 0:59
  • $\begingroup$ yes sorry, i will change my example @Safder $\endgroup$ Aug 27, 2019 at 1:01
0
$\begingroup$

Since $1^n=1$ and $-1^2n=1$ exist, all we can conclude is that that the exponent that creates remainder 1 has all it's multiples turn out to produce 1. This, and using the known highest possible minimal exponent, says if 12 creates 1(given); either one of it's divisors creates 1, or no exponent before 6 can create -1. Attempting it, we get the following:$$1^1\equiv 1\\2^{12}\equiv 1\\3^3\equiv 1\\4^6\equiv 1\\5^4\equiv 1\\6^{12}\equiv 1\\7^{12}\equiv 1\\8^4\equiv 1\\9^6\equiv 1\\10^6\equiv 1\\11^{12}\equiv 1\\12^2\equiv 1$$ All mod 13.

You'll note if we needed values above 1, there is almost a perfect symmetry. This comes from equivalent naming in modular arithmetic, and $$(-x)^{2n}=x^{2n}$$ So in cases where an even order occurs on one, only if -1 is in the powers will the negative create a lower order. odd powers being equivalent to opposite signs of each other.

$\endgroup$
1
  • $\begingroup$ @quid how can this be edited before posted ? $\endgroup$
    – user645636
    Oct 31, 2019 at 23:26

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.