# 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 $\displaystyle a$ be primitive root mod $\displaystyle p$. If $\displaystyle a^{p-1}\equiv 1(\bmod p^2)$ then $\displaystyle (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 $\displaystyle a+p$ is primitive root mod $\displaystyle 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: $\displaystyle 5^{2^{k-3}}\equiv 1 + 2^{k-1} (\bmod 2^k)$ for $\displaystyle k\geq 3$.

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

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