# Thread: need some help on these

1. ## need some help on these

1) Let p be an odd prime. Prove that there is a primitive root of p
whose (p-1)th power is NOT congruent to 1 mod p^2.
Hint: Let g be any primitive root of p. If g works, done.
If g doesn't work, then show that the primitive root g+p of p
does work.

2) For n > 2, let M = 2^n. Prove by induction on n that
5^(M/8) is congruent to 1 + M/2 mod M.

3) Show that the solutions to x^e - 1 = 0 mod p in RRS(p)
are the d numbers b, b^2, ..., b^d mod p, where d=gcd(e,p-1)
and b is an element mod p of order d.
Hint: Write d as a linear combination...

1) Let p be an odd prime. Prove that there is a primitive root of p
whose (p-1)th power is NOT congruent to 1 mod p^2.
Let $a$ be primitive root mod $p$. If $a^{p-1}\equiv 1(\bmod p^2)$ then $(a+p)^{p-1}\equiv a^{p-1} + (p-1)a^{p-2}p\equiv 1 + (p-1)a^{p-2}p\not \equiv 1(\bmod p^2)$.
But $a+p$ is primitive root mod $p$ also.

2) For n > 2, let M = 2^n. Prove by induction on n that
5^(M/8) is congruent to 1 + M/2 mod M.
I know what you are trying to get at, I just do not like how you wrote it. Here is a redone version which looks nicer.

Prove: $5^{2^{k-3}}\equiv 1 + 2^{k-1} (\bmod 2^k)$ for $k\geq 3$.

Of course $k=3$ is true by so we argue by induction.
Say $5^{2^{k-3}}\equiv 1 + 2^{k-1}$ then $\left( 5^{2^{k-3}} \right)^2 \equiv \left( 1 + 2^{k-1} \right)^2 (\bmod 2^{k+1})$.
Thus, $5^{2^{k-2}}\equiv 1 + 2^k + 2^{2k-2} \equiv 1 + 2^k(\bmod 2^{k+1})$.

Let $a$ be primitive root of $p$ (assuming it is odd). Say $x$ solves $x^e = 1(\bmod p)$. Then $x\equiv a^y$ and so $a^{ey}\equiv 1(\bmod p)$ this means $ey\equiv 0(\bmod p-1)$. There are $d=\gcd(e,p-1)$ solutions for $y$. This tells us that $x^e\equiv 1(\bmod p)$ has at most $d$ solutions. It is easy to check that $b,b^2,...,b^d$ are all distinct and each solves $x^e\equiv 1(\bmod p)$. Using the above result that there are at most $d$ solutions it tells us that $b,b^2,...,b^d$ is a complete set of solutions (up to congruence).