Proving 2 as a Primitive Root of Z_83: A Step-by-Step Approach

[fishturtle1]

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?

 

[Dick]

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.

 

[fishturtle1]

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

 

[Dick]

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.

 

[fishturtle1]

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.