Primitive root of Z_83

  • #1
334
44

Homework Statement


Prove that 2 is a primitive root of ##\mathbb{Z}/83\mathbb{Z}## by hand. Hint: Think hard about ##2^{41}##.

Homework Equations


Euler's theorem, Euler's Totient function, Chinese remainder theorem(not sure if its relevant).

We don't really have anything else.

The Attempt at a Solution


So the solution I handed in was just checking ##2^1, 2^2, 2^3, ...##.. I calculated ##2^{41} \equiv -1 (\mod 83)## so the calculations were a little easier..

But listening to my classmates there was a better way.. I heard someone say you just need to check ##2^{41} \not\equiv 1 (\mod 83)## and ##2^{2} \not\equiv 1 (\mod 83)##. And I see that 41 and 2 are the prime divisors of ##\phi(83) = 82##.. So I think we can prove that ##\text{ord}_{83}(2) ## divides ##\phi(83)##.

My attempt is:
Suppose ##x^a \equiv 1 (\mod n)##. Where ##n \epsilon \mathbb{Z}## and ##x \epsilon \mathbb{Z}_n^*##. This means ##x^a \equiv x^{\phi(n)} (\mod n)##. So ##a \equiv \phi(n) \equiv 0 (\mod \phi(n))##. So ##a \equiv 0 (\mod \phi(n)##. This implies ##a = \phi(n) \cdot k## for some integer ##k##. ..

This seems like a dead end... I think I need to start the proof differently but I'm not sure how, or maybe there is a better way to do the original problem?
 

Answers and Replies

  • #2
Dick
Science Advisor
Homework Helper
26,263
619

Homework Statement


Prove that 2 is a primitive root of ##\mathbb{Z}/83\mathbb{Z}## by hand. Hint: Think hard about ##2^{41}##.

Homework Equations


Euler's theorem, Euler's Totient function, Chinese remainder theorem(not sure if its relevant).

We don't really have anything else.

The Attempt at a Solution


So the solution I handed in was just checking ##2^1, 2^2, 2^3, ...##.. I calculated ##2^{41} \equiv -1 (\mod 83)## so the calculations were a little easier..

But listening to my classmates there was a better way.. I heard someone say you just need to check ##2^{41} \not\equiv 1 (\mod 83)## and ##2^{2} \not\equiv 1 (\mod 83)##. And I see that 41 and 2 are the prime divisors of ##\phi(83) = 82##.. So I think we can prove that ##\text{ord}_{83}(2) ## divides ##\phi(83)##.

My attempt is:
Suppose ##x^a \equiv 1 (\mod n)##. Where ##n \epsilon \mathbb{Z}## and ##x \epsilon \mathbb{Z}_n^*##. This means ##x^a \equiv x^{\phi(n)} (\mod n)##. So ##a \equiv \phi(n) \equiv 0 (\mod \phi(n))##. So ##a \equiv 0 (\mod \phi(n)##. This implies ##a = \phi(n) \cdot k## for some integer ##k##. ..

This seems like a dead end... I think I need to start the proof differently but I'm not sure how, or maybe there is a better way to do the original problem?

Sounds like a job for Lagrange's theorem applied to the multiplicative group ##\mathbb{Z}^*_{83}##. Think about that.
 
Last edited:
  • #3
334
44
Sounds like a job for Lagrange's theorem applied to the multiplicative group ##\mathbb{Z}^*_{83}##. Think about that.
Thanks for the response Dick. I am not allowed to use Lagrange's theorem. The class I'm in we are learning the algebra as we go and the professor emphasizes using fundamentals as much as possible over heavy machinery(algebra was not a prereq).

My professor posted the answer online to this specific question... I tried to generalize it here. I just want to make it clear that this proof is HEAVILY based on my professor's proof and so I'm not taking any credit for the correct things. But I deserve blame for any mistakes in the following proof.

We look to show if ##x## is not a primitive root of ##\mathbb{Z}_m^*## then ##x##'s order, call it ##k##, must divide ##\phi(m)## and ##k \neq 0##.

Proof: Let ##x \epsilon \mathbb{Z}_m##. Suppose ##x## is not a primitive root. Let ##k## be the smallest positive integer such that ##x^k \equiv 1 (\mod m)##. Because ##x## is not a primitive root, we have ##k < \phi(m)##.

We now show ##k \vert \phi(m)##. We proceed by contradiction. Suppose ##k## does not divide ##\phi(m)##. Then ##\phi(m) = km + y## for some integers ##m,y## where ##0 < y < k##. We have the following: ##1 \equiv x^{\phi(m)} \equiv x^{km+y} \equiv x^{km}x^y \equiv x^{k^m}x^y \equiv 1\cdot x^y \equiv x^y (\mod m)##. So ##x^y \equiv 1 (\mod m)##. But this contradicts our assumption that ##k## was the smallest positive integer such that ##x^k \equiv 1 (\mod m)##.

We conclude that ##k \vert \phi(m)##. []

So what I get from this is that, when seeing if some ##x## is a generator of some ##\mathbb{Z}_m##, we just need to compute ##\phi(m)## and then check ##x## raised to any of ##\phi(m)##'s factors.. and if it is a primitive root then ##x## raised to any factor of ##\phi(m)## will not be congruent to 1 (mod m).
 
  • #4
Dick
Science Advisor
Homework Helper
26,263
619
Thanks for the response Dick. I am not allowed to use Lagrange's theorem. The class I'm in we are learning the algebra as we go and the professor emphasizes using fundamentals as much as possible over heavy machinery(algebra was not a prereq).

My professor posted the answer online to this specific question... I tried to generalize it here. I just want to make it clear that this proof is HEAVILY based on my professor's proof and so I'm not taking any credit for the correct things. But I deserve blame for any mistakes in the following proof.

We look to show if ##x## is not a primitive root of ##\mathbb{Z}_m^*## then ##x##'s order, call it ##k##, must divide ##\phi(m)## and ##k \neq 0##.

Proof: Let ##x \epsilon \mathbb{Z}_m##. Suppose ##x## is not a primitive root. Let ##k## be the smallest positive integer such that ##x^k \equiv 1 (\mod m)##. Because ##x## is not a primitive root, we have ##k < \phi(m)##.

We now show ##k \vert \phi(m)##. We proceed by contradiction. Suppose ##k## does not divide ##\phi(m)##. Then ##\phi(m) = km + y## for some integers ##m,y## where ##0 < y < k##. We have the following: ##1 \equiv x^{\phi(m)} \equiv x^{km+y} \equiv x^{km}x^y \equiv x^{k^m}x^y \equiv 1\cdot x^y \equiv x^y (\mod m)##. So ##x^y \equiv 1 (\mod m)##. But this contradicts our assumption that ##k## was the smallest positive integer such that ##x^k \equiv 1 (\mod m)##.

We conclude that ##k \vert \phi(m)##. []

So what I get from this is that, when seeing if some ##x## is a generator of some ##\mathbb{Z}_m##, we just need to compute ##\phi(m)## and then check ##x## raised to any of ##\phi(m)##'s factors.. and if it is a primitive root then ##x## raised to any factor of ##\phi(m)## will not be congruent to 1 (mod m).

Guess I don't think of Lagrange's theorem as 'heavy machinery', but you can do it that way as well. The only quibble I have with your proof is that you have used ##m## to mean two different things. You might want to clean that up.
 
  • #5
334
44
Guess I don't think of Lagrange's theorem as 'heavy machinery', but you can do it that way as well. The only quibble I have with your proof is that you have used ##m## to mean two different things. You might want to clean that up.
Thanks, I meant ##\phi(m) = k \cdot l + y##.. for some integers l, y where 0 < y < k.
 

Related Threads on Primitive root of Z_83

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
950
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
9
Views
5K
  • Last Post
Replies
3
Views
734
  • Last Post
Replies
8
Views
2K
  • Last Post
Replies
13
Views
2K
  • Last Post
Replies
5
Views
1K
Replies
2
Views
1K
Replies
4
Views
2K
Top