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

Question

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.

Answer 1

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}$