Number Theory Help: Homework Equation on Prime Generator

[Kindayr]

Yep that's the question exactly.

What is it exactly that you're trying to show that makes the claim untrue? I'll take it up with my prof if it indeed isn't a true claim.

 

[Deveno]

Yep that's the question exactly.

What is it exactly that you're trying to show that makes the claim untrue? I'll take it up with my prof if it indeed isn't a true claim.

well, the problem is, that just because we found a counter-example for ONE generator for ONE prime, doesn't mean that some OTHER generator might still have the desired property. in fact, since we have φ(p-1) generators, there is (on average) around a 1 in 3 chance that any given element of Z_p^x is a generator (it depends on "how composite" p-1 is).

and i think that the chances of every generator a having a^p-1 ≡ 1 (mod p) AND a^p-1 ≡ 1 (mod p²) are pretty low, indeed. but even for small p, the actual integers we are talking about are fairly large (looking at p = 29, the calculations are already in the millions, for the generator 2).

the only thing that occurs to me off the top of my head, is that if p is not 3, then p-1 is not 2, so a^-1 = a^p-2 is another generator, and perhaps it might be that if
a^p-1≡ 1 mod p², that maybe (a^p-2)^p-1 isn't. but i have not looked into this in any detail.

 

[Dick]

Ooo. Ooo. I was checking your numbers and scratching my head and I found a big hint carefully reading a Wikipedia article. If a^(p-1) ≡ 1 (mod p^2) and a is a generator, what about (a+p)? It's simpler than I thought.

 

[Deveno]

Ooo. Ooo. I was checking your numbers and scratching my head and I found a big hint carefully reading a Wikipedia article. If a^(p-1) ≡ 1 (mod p^2) and a is a generator, what about (a+p)? It's simpler than I thought.

you have no idea what a mental laxative this is.

certainly [a] = [a+p], and (a+p)^p-1 = a^p-1+ p((p-1)a^p-2 + p(...other stuff))

and p is co-prime to a, and certainly to p-1, so even if a^p-1 = 1 + kp²,

(a+p)^p-1 = 1 + kp² + p((p-1)a^p-2 + p(...other stuff))

= 1 + p²(k + (other stuff)) + p(p-1)a^p-2

and although p divides p(p-1)a^p-2, p² does not.

i feel much better, now.

 

[Dick]

you have no idea what a mental laxative this is.

certainly [a] = [a+p], and (a+p)^p-1 = a^p-1+ p((p-1)a^p-2 + p(...other stuff))

and p is co-prime to a, and certainly to p-1, so even if a^p-1 = 1 + kp²,

(a+p)^p-1 = 1 + kp² + p((p-1)a^p-2 + p(...other stuff))

= 1 + p²(k + (other stuff)) + p(p-1)a^p-2

and although p divides p(p-1)a^p-2, p² does not.

i feel much better, now.

What YOU don't know is how good I felt after you took over the thread. I don't consider myself much of a number theory guy. I was trying to figure out how to determine a number was a primitive root and reading http://en.wikipedia.org/wiki/Primitive_root_modulo_n when the stuff in the Cohen reference jumped out at me. Thanks for your efforts on this. I was clueless.

 

[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<br /> \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!