# Thread: proplems in primitives roots

1. ## proplems in primitives roots

please i need help in foloowing propems

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

[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 $r^n\equiv a(modp)$ iff $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 $\phi(p)/gcd(\phi(p),inda)$

4) show that if $a^k\equiv1(modp)$, $a^h\equiv1(modp)$ ,then $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 $p^k$, then r is a primitive root of $p^i$ , $1

[hint: use induction of i ]
To prove this we need to use the following fact: if $a\equiv b (\bmod p^n)$ for $n\geq 1$ then $a^p \equiv b^p (\bmod p^{n+1} )$. To prove this we write $a = b + c\cdot p^n$ and so $a^p = (b+c\cdot p^n)^p = b^p + d\cdot p^{n+1}$ where $d$ is everything in between the binomial expansion, here we are using a well-known fact that $p$ divides the innermost binomial coefficients, but because of the presence of $p^n$ it means that the innermost binomial coefficients are all divisible by $p^n$ too, and so everything in the middle is divisible by $p^{n+1}$, thus, $a^p \equiv b^p (\bmod p^{n+1})$. Now we have the tool to prove what you wish to show. Suppose $r$ is a primitive root of $p^k$, $k\geq 1$. This means the order of $r$ is $\phi (p^k) = p^k - p^{k-1}$. Now we claim that $r$ is a primitive root of $p^{k-1}$ too, this means we have to show the order of $r$ mod $p^{k-1}$ is $\phi (p^{k-1}) = p^{k-1} - p^{k-2}$. Suppose it is not a primitive root with order $m < p^{k-1} - p^{k-2}$ then $r^m \equiv 1 (\bmod p^{k-1})$ using the above result it means $r^{mp} \equiv 1 (\bmod p^k )$ but $mp < (p^{k-1} - p^{k-2})p = p^k - p^{k-1} = \phi (p^k)$, and so it contradicts the fact that $r$ is a primitive root of $p^k$. Now we can prove that $r$ is a primitive root of $p^{k-2}$, i.e. the order is $\phi (p^{k-2}) = p^{k-2} - p^{k-3}$, suppose the order of $r$ was $m < p^{k-2} - p^{k-3}$ then $r^m \equiv 1 (\bmod p^{k-2})$ and that means $r^{mp} \equiv 1 (\bmod p^{k-1})$ but then $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 $1\leq i\leq k$ we have that $r$ is primitive root of $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 $r^n\equiv a(modp)$ iff $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 $\phi(p)/gcd(\phi(p),inda)$
Let us make a more general proof. Let $n\geq 2$ be a positive integer that has a primitive root $r$. Let $a$ be an integer such that $\gcd (a,n) = 1$. Then if $k = \mbox{ord}(a)$ it means $k$ is the least positive exponent such that $a^k \equiv 1 (\bmod n)$. Now is $s = \mbox{ind}(a)$ then it means $a \equiv r^s (\bmod n)$ and so $a^k \equiv 1 \implies (r^s)^k \equiv 1 (\bmod n )$. Thus, we are looking for the order of $r^s$ which is $\phi(n)/\gcd(\phi(n),s)$ (this is a theorem you should know).