# Show that $101^2$ does not divide $2^{50}+1$ and that $2$ is a primitive root modulo $101^{101}$

The first task is to show that $$101^2$$ does not divide $$2^{50}+1$$.

For this I first found out that $$2$$ is a primitive root modulo $$101$$, by just looking at the power of $$2$$.

I assume by contrary that $$101^2$$ divides $$2^{50}+1$$, so $$2^{50}= -1 \pmod {101^2}$$.

On the other hand, by calculation of powers of $$2$$: $$2^{25}= 10 \pmod {101}$$, so $$2^{25} = 10+ 101k$$, and $$2^{50}= 100 + 2020k \pmod {101^2}$$.

We get that $$100 + 2020k = -1 \pmod {101^2}$$, but I am not sure how that causes a contradiction.

The second task is to show that $$2$$ is a primitive root modulo $$101^{101}$$.

Since $$\phi(101) = 101^{100} * 100$$, I need to show that this is the order of $$2$$.

I can use that $$2$$ is a primitive root of $$101$$ to get that $$2^n \neq 1 \pmod {101^{101}}$$ for $$n < 100$$, but I don't know how to follow from here.

Help would be appreciated.

• It is enough to prove that $2$ is a primitive root modulo $101^2$ – lhf Jun 28 at 19:50
• This could help. math.stackexchange.com/questions/31679/… – Anurag A Jun 28 at 19:55
• I still don't manage to solve the first part of my question – Gabi G Jun 28 at 21:06
• another way is $2^{16}=65536\equiv4330\bmod10201$, so $2^{32}\equiv4330^2\equiv9663$, so $2^{50}=2^{32}2^{16}2^2\equiv9663\times4330\times4\equiv5554\bmod10201$ – J. W. Tanner Jun 29 at 17:55
• Okay then, thanks! – Gabi G Jun 29 at 18:30

## 1 Answer

Comment:

We have:

$$2^{101-1}-1⇒ ≡0 \ mod(101)$$

$$(2^{50}+1)(2^{50}-1) ≡ 0 \mod (101)$$

$$2^{50}+1≡0 \ mod(101) =101 k$$

$$2^{50}-1 ≡ -2 \mod (101)$$

Now if $$k=101 k_1$$ then we must have:

$$k ≡0 \mod(101)$$

$$k_1 (2^{50}+1) ≡0 \mod (101^2)$$

This contradicts what we want to show.

Now $$2^{50} ≡-1 \mod (101)$$

Clearly $$(2^{50})^{n} ≡ -1\mod (101)$$

if n is odd. $$101$$ is odd and we have:

$$(2^{50})^{101}≡ -1\mod (101)^{101}$$

That means $$2$$ is the primitive root of $$101^{101}$$