1
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ It is enough to prove that $2$ is a primitive root modulo $101^2$ $\endgroup$ – lhf Jun 28 at 19:50
  • 2
    $\begingroup$ This could help. math.stackexchange.com/questions/31679/… $\endgroup$ – Anurag A Jun 28 at 19:55
  • $\begingroup$ I still don't manage to solve the first part of my question $\endgroup$ – Gabi G Jun 28 at 21:06
  • 1
    $\begingroup$ 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$ $\endgroup$ – J. W. Tanner Jun 29 at 17:55
  • 1
    $\begingroup$ Okay then, thanks! $\endgroup$ – Gabi G Jun 29 at 18:30
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.