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)&gt;0 for any n\in\mathbb{Z}, it follows that \varphi (p-1)&gt;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&lt;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!