Question

Find a primitive root modulo 2401 = 7^4. Be sure to mention which exponentiations you checked to prove that your final answer is indeed a primitive root. (You may use Wolfram Alpha for exponentiations modulo 2401, but you may not use any of Wolfram Alpha’s more powerful functions.)

Answer 1

Note that

Now, and is the smallest positive integer such that

So, is a primitive root modulo .

My claim is that is a primitive root modulo .

For that, we will need the following strong lemma.

Lemma:

Proof of lemma is by induction on .

Base case: .

Then

So, base case is true.

Induction hypothesis: Assume that for some .

Induction step: We will prove it for .

By Euler's theorem, we have,

for some integer .

If , then for some and so,

which is a contradiction to induction hypothesis.

So, .

Now,

since

since

by binomial theorem

Now, every term from onwards is divisible by . Why? Let us check one by one.

divisible by

divisible by

divisible by

divisible by

divisible by

divisible by

So, modulo , we have only the first two terms.

Now, we have to prove that

Suppose on the contrary that

Then

which is a contradiction.

So, the result is also true for .

Hence, by induction principle, the lemma is proved.

-------------------------------------------------------------------------------------------------------------------------

Now that we have the lemma, Put .

Then

To prove, is a primitive root modulo .

Let be the smallest positive integer such that

If we want to prove that is a primitive root modulo , our goal must be to show that .

Now, since , we have,

But is the smallest positive integer such that

Let for some positive integer

Now, and are coprime. So, by Euler's theorem,

But is the smallest positive integer such that .

where

where .

We will show that .

Suppose not. i.e., .

Now, which implies

So,

, say,

since

This is a contradiction to the equation .

So, our assumption was false.

That means, and hence,

So, is a primitive root modulo .