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