Number Theory Help: Homework Equation on Prime Generator

[Kindayr]

Yep, we had to use the fact that $a+p\in\mathbb{Z}_{p^{2}}^{\times}$ is a generator, hence showing that it is cyclic. My original question was the starting point to this proof.

I'm still confused on how exactly we showed that $\gcd(k,p)=1$.

Also, thank you so much for your help otherwise!

 

[Dick]

Yep, we had to use the fact that $a+p\in\mathbb{Z}_{p^{2}}^{\times}$ is a generator, hence showing that it is cyclic. My original question was the starting point to this proof.

I'm still confused on how exactly we showed that $\gcd(k,p)=1$.

Also, thank you so much for your help otherwise!

If gcd(k,p) is not 1 then p divides k. So kp is divisible by p^2. You should fill in the rest.

 

[Kindayr]

If gcd(k,p) is not 1 then p divides k. So kp is divisible by p^2. You should fill in the rest.

Then $a^{p-1}\equiv 1 \mod (p^{2})$

Why is this a problem?

 

[Dick]

Then $a^{p-1}\equiv 1 \mod (p^{2})$

Why is this a problem?

If that's true then cp or kp must be divisible by p^2. Deveno dug up an example where that's true. You don't see a problem with that?

 

[Kindayr]

I'm still confused as to where I'm supposed to go with all of this.

Let $p$ be an odd prime. For each $d|p-1$, let $f(d)$ be the amount of elements of $\mathbb{Z}_{p}^{\times}$ such that those elements have order $d$. Clearly $$\sum_{d|p-1}f(d)=p-1.$$ Fix $a \in\mathbb{Z}_{p}^{\times}$ such that $ord(a)=d$, for fixed $d|p-1$. Then $G=\{1,a,a^{2},\dots,a^{d-1}\}$ is a cyclic group of order $d$. Note $ord(a^{r})=d$ iff $\gcd (r,d)=1$. Hence there are up to $\varphi(d)$ many elements in $\mathbb{Z}_{p}^{\times}$ such that their order is $d$. Note that $$\sum_{d|p-1}\varphi(d)=p-1.$$ So we have $$(\star)\sum_{d|p-1}f(d)=p-1=\sum_{d|p-1}\varphi(d).$$

Since either $f(d)=0$ or $f(d)=\varphi(d)$, it follows that $f(d)\le \varphi(d)$. Hence, from $(\star)$ we have that $f(d)=\varphi(d)$ for each $d$. Since $\varphi(n)>0$ for any $n\in\mathbb{Z}$, it follows that $\varphi (p-1)>0$. Hence, because $p-1|p-1$, we have that there exists at least one element of $\mathbb{Z}_{p}^{\times}$ such that it is a generator of $\mathbb{Z}_{p}^{\times}$.

Choose such a generator $a\in\mathbb{Z}_{p}^{\times}$. By Fermat's Little Theorem, we have that $a^{p-1}\equiv 1 \mod p$. Hence there exists $k\in\mathbb{Z}$ such that $a^{p-1}=1+kp$. Since $p$ odd prime, it follows that $p-1$ is even and hence there exists $m\in\mathbb{Z}$ such that $p-1=2m$. So we have $$kp=a^{p-1}-1=a^{2m}-1=(a^{m})^{2}-1=(a^{m}-1)(a^{m}+1).$$

Since $p$ odd prime, it follows that either $p|(a^{m}+1)$ or $p|(a^{m}-1)$. Suppose $p|(a^{m}-1)$, then $a^{m}\equiv 1 \mod p$. But $m<p-1$ and $ord(a)=p-1$, a contradiction. Hence $p\not{|}(a^{m}-1)$, and thus $p|(a^{m}+1)$. Suppose $\gcd(k,p)=p$, then $p^{2}|(a^{m}+1)$. Hence $a^{m}\equiv -1 \mod p^{2}$. Therefore $(a^{m})^{2}\equiv 1 \mod p^{2}$ and hence $a^{p-1} \equiv 1 \mod p^{2}$.This is where I get stuck to continue.

OOOOH wait! If we choose $a+p$, then it is also a generator of $\mathbb{Z}_{p}^{\times}$ but its also a generator of $\mathbb{Z}_{p^{2}}^{\times}$. Hence $(a+p)^{p-1}\not{\equiv} 1 \mod p^{2}$. Thus $(a+p)^{p-1}=1+kp$ and $p^{2}\not{|}(a^{m}+1)$, hence $\gcd (k,p)=1$, as required. WOOT

 

[Kindayr]

Again, thanks all! This helped so much!