# How to show that 2 is primitive root modulo $101^{101}$?

Given the facts:

(a) 2 is primitive root modulo 101

(b) $$2^{50}+1$$ isn't divisible by $$101^{2}$$

I have been asked to show that 2 is a primitive root modulo $$101^{101}$$.

How do I do that?

I started by defining $$m:=\operatorname{ord}_{101^{101}}(2)$$.

Then we get $$2^{m}=1 \mod 101$$. And from (a) we get $$100\mid m$$.

So in fact $$m=100k$$, and we would like to show that $$k=101^{100}$$, therefore $$m=101^{100}\cdot100=\phi(101^{101})$$.

That's what I have.

• What have you tried? See How to ask a good question. – Saad Jun 22 at 13:06
• If you just search for "primitive roots $\pmod {p^n}$" you'll find many useful results. – lulu Jun 22 at 13:14
• @Saad question updated – Daniel Jun 22 at 13:18
• You've got that $2$ is a primitive root modulo $101$. Then, in number theory, either $a$ or $a+p$ is a primitive root modulo $p^2$. So check to see whether $103$ is a primitive root modulo $101^2$. If not, then $2$ is a primitive root modulo $101^2$ and furthermore, is a primitive root modulo $101^{n}$ which again, is another result that can be proved. – thesmallprint Jun 22 at 13:48
• math.stackexchange.com/questions/31679/… – lab bhattacharjee Jun 24 at 18:04