# Thread: proplems in primitives roots

1. ## proplems in primitives roots

please i need help in foloowing propems

1) if r is primitive root of $\displaystyle p^k$, then r is a primitive root of $\displaystyle p^i$ , $\displaystyle 1<i<k$

[hint: use induction of i ]

2) le t be a prime , r be any primitive root of p , let a be any positive integer with gcd(a,p)=1 , then ; prove that $\displaystyle r^n\equiv a(modp)$ iff $\displaystyle a\equiv ind a(mod p^-1)$

3) let p be prime , r any primitive root of p , let a be any (+ve) integer such that gcd(a,p)=1 then prove that the order of a modoulo p is $\displaystyle \phi(p)/gcd(\phi(p),inda)$

4) show that if $\displaystyle a^k\equiv1(modp)$,$\displaystyle a^h\equiv1(modp)$ ,then $\displaystyle a^hp\equiv 1(modp^2)$

2. Originally Posted by midosoft
please i need help in foloowing propems
1) if r is primitive root of $\displaystyle p^k$, then r is a primitive root of $\displaystyle p^i$ , $\displaystyle 1<i<k$

[hint: use induction of i ]
To prove this we need to use the following fact: if $\displaystyle a\equiv b (\bmod p^n)$ for $\displaystyle n\geq 1$ then $\displaystyle a^p \equiv b^p (\bmod p^{n+1} )$. To prove this we write $\displaystyle a = b + c\cdot p^n$ and so $\displaystyle a^p = (b+c\cdot p^n)^p = b^p + d\cdot p^{n+1}$ where $\displaystyle d$ is everything in between the binomial expansion, here we are using a well-known fact that $\displaystyle p$ divides the innermost binomial coefficients, but because of the presence of $\displaystyle p^n$ it means that the innermost binomial coefficients are all divisible by $\displaystyle p^n$ too, and so everything in the middle is divisible by $\displaystyle p^{n+1}$, thus, $\displaystyle a^p \equiv b^p (\bmod p^{n+1})$. Now we have the tool to prove what you wish to show. Suppose $\displaystyle r$ is a primitive root of $\displaystyle p^k$, $\displaystyle k\geq 1$. This means the order of $\displaystyle r$ is $\displaystyle \phi (p^k) = p^k - p^{k-1}$. Now we claim that $\displaystyle r$ is a primitive root of $\displaystyle p^{k-1}$ too, this means we have to show the order of $\displaystyle r$ mod $\displaystyle p^{k-1}$ is $\displaystyle \phi (p^{k-1}) = p^{k-1} - p^{k-2}$. Suppose it is not a primitive root with order $\displaystyle m < p^{k-1} - p^{k-2}$ then $\displaystyle r^m \equiv 1 (\bmod p^{k-1})$ using the above result it means $\displaystyle r^{mp} \equiv 1 (\bmod p^k )$ but $\displaystyle mp < (p^{k-1} - p^{k-2})p = p^k - p^{k-1} = \phi (p^k)$, and so it contradicts the fact that $\displaystyle r$ is a primitive root of $\displaystyle p^k$. Now we can prove that $\displaystyle r$ is a primitive root of $\displaystyle p^{k-2}$, i.e. the order is $\displaystyle \phi (p^{k-2}) = p^{k-2} - p^{k-3}$, suppose the order of $\displaystyle r$ was $\displaystyle m < p^{k-2} - p^{k-3}$ then $\displaystyle r^m \equiv 1 (\bmod p^{k-2})$ and that means $\displaystyle r^{mp} \equiv 1 (\bmod p^{k-1})$ but then $\displaystyle mp < p(p^{k-2} - p^{k-3}) = p^{k-1} - p^{k-2} = \phi (p^{k-1})$ which is a contradiction. And now work yourself down by induction. And thus, for $\displaystyle 1\leq i\leq k$ we have that $\displaystyle r$ is primitive root of $\displaystyle p^i$.

3. Originally Posted by midosoft
2) le t be a prime , r be any primitive root of p , let a be any positive integer with gcd(a,p)=1 , then ; prove that $\displaystyle r^n\equiv a(modp)$ iff $\displaystyle a\equiv ind a(mod p^-1)$
This problem just does not make any sense.

3) let p be prime , r any primitive root of p , let a be any (+ve) integer such that gcd(a,p)=1 then prove that the order of a modoulo p is $\displaystyle \phi(p)/gcd(\phi(p),inda)$
Let us make a more general proof. Let $\displaystyle n\geq 2$ be a positive integer that has a primitive root $\displaystyle r$. Let $\displaystyle a$ be an integer such that $\displaystyle \gcd (a,n) = 1$. Then if $\displaystyle k = \mbox{ord}(a)$ it means $\displaystyle k$ is the least positive exponent such that $\displaystyle a^k \equiv 1 (\bmod n)$. Now is $\displaystyle s = \mbox{ind}(a)$ then it means $\displaystyle a \equiv r^s (\bmod n)$ and so $\displaystyle a^k \equiv 1 \implies (r^s)^k \equiv 1 (\bmod n )$. Thus, we are looking for the order of $\displaystyle r^s$ which is $\displaystyle \phi(n)/\gcd(\phi(n),s)$ (this is a theorem you should know).