Good day! I'm currently studying on the primitive roots mod n. Eventually, I fully understand the concept of calculating the primitive roots of a number by practice, but I encounter the following problems that is out of my league. Please help me understand the following concept. Any idea will be of great help.

  1. Show that $$ Fn = 2 ^ {2 ^ n} + 1 $$ , n > 1, is a prime, then 2 is not a primitive roots of Fn.

  2. Show that if p = 1 (mod 4) and $g$ is a primitive root of $p$, then so is $-g$. Show by a numerical example that this need not be the case if p = 3 (mod 4).

  3. Prove that if $a$ has order hk (mod m), then $a^{k}$ has order k mod n.

  4. Prove that if a has order 2k modulo p the odd prime p, then a^k = -1 (mod p).

  • $\begingroup$ 3 currently has three "$k$"s and one "$h$". Perhaps one "$k$" should be an "$h$"? $\endgroup$ – Eric Towers Sep 6 '16 at 14:28
  • $\begingroup$ Sir I copy the question as it is,,i dont if there is a flaw in the problem $\endgroup$ – rosa Sep 6 '16 at 14:37
  • $\begingroup$ I notice that you have asked four questions and, so far, the two proposed solutions have addressed different questions. At different times, each has been selected as the "correct answer", even though they can both be correct simultaneously. This is why we try to ask only one question per Question on this site. $\endgroup$ – Eric Towers Sep 6 '16 at 16:00
  • $\begingroup$ Ouch sorry sir not that much familiar with the system of this site ... sorry :( $\endgroup$ – rosa Sep 6 '16 at 16:10

(3) We show the correct fact: $h$ is the order of $a^k$ modulo $n$.

Since $a$ has order $hk$ modulo $m$, we have $a^{hk} \cong 1 \pmod{n}$ and $hk$ is the least positive power of $a$ congruent to $1$. The powers of $a^k$ are a subsequence of the powers of $a$ and $a^{hk} = (a^k)^h$ is the smallest positive power of $a$ that is congruent to $1$ and so $h$ is the smallest power of $a^k$ that is congruent to $1$. Therefore, $h$ is the order of $a^k$ modulo $n$.

  • $\begingroup$ ah?? I see your point... yes maybe the question has flaws in it,,,tnx very much sir... $\endgroup$ – rosa Sep 6 '16 at 14:56

Here is a solution to the first question. (Maybe ill add more as I see fit, the others are easier.) Let $p=2^{2^n}+1$ be prime. Then $$2^{2^n}\equiv -1 \mod p$$ so

$$2^{2^{n+1}}\equiv 1 \mod p$$ Now if $2$ were a primitive root its order would be $p-1$ and so $p-1|2^{n+1}$ or $2^{2^n}|2^{n+1}$ which means that $2^n\leq n+1$ which is false for $n>1$. Thus $2$ is not a primitive root.

  • $\begingroup$ thank you sir i'll study your answer. It seems that i have to go back on divisibility rules... $\endgroup$ – rosa Sep 6 '16 at 14:38
  • 1
    $\begingroup$ Some basic group theory (cyclic groups) will help with this material. $\endgroup$ – Rene Schipperus Sep 6 '16 at 14:40
  • $\begingroup$ ouch! not yet familiar with those terms... $\endgroup$ – rosa Sep 6 '16 at 14:46

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.