Number Theory Help: Homework Equation on Prime Generator

[Kindayr]

Homework Statement

Let p be an odd prime. Show that there exists a\in\mathbb{Z} such that [a]\in\mathbb{Z}^{\times}_{p} is a generator and a^{p-1}=1+cp for some c coprime to p.

Homework Equations

The Attempt at a Solution

I honestly have no idea where to even start with this. Any help will be much appreciated, no full solutions though!

 

[Dick]

You could start with Fermat's Little Theorem.

 

[Kindayr]

You could start with Fermat's Little Theorem.

Well I know its obvious that a^{p-1}\equiv 1 (\mod p) since [a]\in\mathbb{Z}_{p}^{\times}. Hence there exists k\in\mathbb{Z} such that a^{p-1}=1+kp. How do I show that \gcd (k,p)=1?

 

[Dick]

Well I know its obvious that a^{p-1}\equiv 1 (\mod p) since [a]\in\mathbb{Z}_{p}^{\times}. Hence there exists k\in\mathbb{Z} such that a^{p-1}=1+kp. How do I show that \gcd (k,p)=1?

Offhand, I don't know. You were asking for a hint to start and no full solutions. I'll think about it though, if you don't find the solution first.

 

[Deveno]

for [a] to be a generator, we also need to know that p-1 is the smallest positive integer k for which:

a^k ≡ 1 (mod p)

i suggest asking yourself a similar, but related question:

suppose d|(p-1). how many elements of Z_p^x are of order d?

hint: suppose a is of order d.

(i suppose i "should write" [a] instead of a. i mean the modulo class, NOT the integer)

look at the set {1,a,a²,...,a^d-1}.

this is a cyclic group, how many generators does it have?

hint #2: eventually, you'll have to drag in the totient function into this. why did i suggest looking at those d that divide p-1?

 

[Kindayr]

hint: suppose a is of order d.

(i suppose i "should write" [a] instead of a. i mean the modulo class, NOT the integer)

look at the set {1,a,a²,...,a^d-1}.

this is a cyclic group, how many generators does it have?

Any element a^{r} such that \gcd(r,d)=1 is a generator.

 

[Deveno]

Any element a^{r} such that \gcd(r,d)=1 is a generator.

yes, that is true. and how many of those "r's" are there?

 

[Kindayr]

hint #2: eventually, you'll have to drag in the totient function into this. why did i suggest looking at those d that divide p-1?

The size of \mathbb{Z}_{p}^{\times} is \phi (p)=p-1

 

[Kindayr]

yes, that is true. and how many of those "r's" are there?

\phi (d) many.

 

[Deveno]

The size of \mathbb{Z}_{p}^{\times} is \phi (p)=p-1

yes, that is also true, and you'll want to use that fact later on. how does "d" enter into this?

\phi (d) many.

exactly! now...given any a of order d, how many "other elements" of order d, do we get "for free" along with it?

and...do you know of any way to relate φ(d) and φ(p-1)?

 

[Kindayr]

yes, that is also true, and you'll want to use that fact later on. how does "d" enter into this?

If we take d=p-1, then there are only \phi (p-1) many generators of \mathbb{Z}_{p}^{\times}. Is this right?

do you know of any way to relate φ(d) and φ(p-1)

Since d|p-1, it follows that \phi(d)|\phi(p-1). Hence there exists k\in\mathbb{Z} such that \phi(p-1)=k\phi(d).

 

[Deveno]

If we take d=p-1, then there are only \phi (p-1) many generators of \mathbb{Z}_{p}^{\times}. Is this right?

we only know that if we already know that there is in fact an element a of order p-1, which is what we're trying to prove!

we don't even know if there are any elements of order d, but if there are, how many must we have (at least)?

ok, let's step back for a minute, and see if you can glimpse where we're going:

every element of Z_p^x has SOME order, and we know that the order of any element has to divide p-1, by a theorem of Lagrange.

let's call the number of elements of order d, f(d).

so if the divisor list of p-1 is 1 = d₁,d₂,...,d_k = p-1

p -1 = f(d₁) + f(d₂) +...+ f(d_k)

= \sum_{d|p-1} f(d)

for every d that divides p-1, f(d) is either ___ or _____ ?

 

[Kindayr]

for every d that divides n, f(d) is either ___ or _____ ?

For every d|p-1, it follows that every f(d) is either \phi(d) or 0, because we haven't verified the fact that there exists an element of order d for each d|p-1.

 

[Deveno]

For every d|p-1, it follows that every f(d) is either \phi(d) or 0, because we haven't verified the fact that there exists an element of order d for each d|p-1.

great! glad to see you're still with me on this.

now, do you know the answer to this question?

\sum_{d|p-1} \varphi(d) = ?

 

[Kindayr]

great! glad to see you're still with me on this.

now, do you know the answer to this question?

\sum_{d|p-1} \varphi(d) = ?

Yep :)
\sum_{d|p-1}\phi(d)=p-1

 

[Deveno]

and is it not true that for every d that divides p-1:

f(d) ≤ φ(d)?

 

[Kindayr]

and is it not true that for every d that divides p-1:

f(d) ≤ φ(d)?

Yep since f(d) is either \phi(d) or 0; both of which are less than or equal to \phi(d). And since \sum_{d|p-1}f(d)=\sum_{d|p-1}\phi(d), it follows from the previous sentence that f(d)=\phi(d). So now we know that \phi(d) is exactly the number of elements in \mathbb{Z}_{p}^{\times} that have order d. Hence, for each d|p-1, there exists exactly \phi(d) many (which is non-zero) elements in \mathbb{Z}_{p}^{\times} whose order is d.

 

[Deveno]

Yep since f(d) is either \phi(d) or 0; both of which are less than or equal to \phi(d). And since \sum_{d|p-1}f(d)=\sum_{d|p-1}\phi(d), it follows from the previous sentence that f(d)=\phi(d). So now we know that \phi(d) is exactly the number of elements in \mathbb{Z}_{p}^{\times} that have order d. Hence, for each d|p-1, there exists exactly \phi(d) many (which is non-zero) elements in \mathbb{Z}_{p}^{\times} whose order is d.

so now we've established existence for EVERY d that divides p-1. and one of those divisors is...?

 

[Kindayr]

so now we've established existence for EVERY d that divides p-1. and one of those divisors is...?

We can take d=p-1 and hence there exists \phi(p-1) many elements of \mathbb{Z}_{p}^{\times} whose order is p-1. But since the order of \mathbb{Z}_{p}^{\times} is p-1, it follows that these elements are exactly the generators of \mathbb{Z}_{p}^{\times}. Hence, we've show that there exists at least a single generator of \mathbb{Z}_{p}^{\times}.

So let a\in\mathbb{Z}_{p}^{\times} be one of these generators. By Fermat's Little Theorem we have a^{p-1}\equiv 1 \mod {p}. Hence there exists k\in\mathbb{Z} such that a^{p-1}=1+kp.

 

[Deveno]

We can take d=p-1 and hence there exists \phi(p-1) many elements of \mathbb{Z}_{p}^{\times} whose order is p-1. But since the order of \mathbb{Z}_{p}^{\times} is p-1, it follows that these elements are exactly the generators of \mathbb{Z}_{p}^{\times}. Hence, we've show that there exists at least a single generator of \mathbb{Z}_{p}^{\times}.

indeed, we've shown that there's usually a lot of generators.

there's just one more matter to clear up.

we know that there is some a with order p-1, so of course a^p-1 = 1 + kp.

but...we haven't yet shown gcd(k,p) = 1. any thoughts?

 

[Kindayr]

but...we haven't yet shown gcd(k,p) = 1. any thoughts?

Well if 1\le k<p, then clearly \gcd(k,n)=1. But if p<k, then its not so clear.

 

[Deveno]

Well if 1\le k<p, then clearly \gcd(k,n)=1. But if p<k, then its not so clear.

true enough. but we haven't used all of the help we were given by the problem at the start.

p is an ODD prime. maybe that is important somehow...hmm, if p is odd, then p-1 is even, so:

a^p-1 = 1 + kp

but p-1 = 2m, so:

(a^m)² - 1 = kp

can you do anything with that?

 

[Kindayr]

true enough. but we haven't used all of the help we were given by the problem at the start.

p is an ODD prime. maybe that is important somehow...hmm, if p is odd, then p-1 is even, so:

a^p-1 = 1 + kp

but p-1 = 2m, so:

(a^m)² - 1 = kp

can you do anything with that?

Well we can say kp=(a^{m})^2-1=(a^{m}-1)(a^{m}+1), or is there something that I'm missing?

 

[Deveno]

Well we can say kp=(a^{m})^2-1=(a^{m}-1)(a^{m}+1), or is there something that I'm missing?

that's a good start. now what can we say about divisibility of the factors on the right by p, because p is prime?

 

[Kindayr]

that's a good start. now what can we say about divisibility of the factors on the right by p, because p is prime?

Either p|(a^{m}+1) or p|(a^{m}-1). If it is the latter, then p|(a^{m}-1) implies that a^{m}\equiv 1\mod p, but that would mean that the order of a is m, which contradicts the fact that a is a generator of \mathbb{Z}_{p}^{\times}. Hence, it must be that a^{m}\equiv -1\mod p.

 

[Deveno]

Either p|(a^{m}+1) or p|(a^{m}-1). If it is the latter, then p|(a^{m}-1) implies that a^{m}\equiv 1\mod p, but that would mean that the order of a is m, which contradicts the fact that a is a generator of \mathbb{Z}_{p}^{\times}. Hence, it must be that a^{m}\equiv -1\mod p.

well, you know, that's ok, but the thing is, we don't really care which factor p divides, so long as we know that p divides one of them. the point is:

k = (a^m - 1)(a^m + 1)/p

we're trying to prove something about k, here: gcd(k,p) = 1.

could k be 0? well, that would mean one of our factors is 0, but surely a > 1.

and if 1 ≤ k < p, as you yourself already noted, gcd(k,p) = 1.

so if k ≥ p, the only way gcd(k,p) ≠ 1, is if p|k.

and that's what we want to show "can't happen".

now, for ANY positive integer n, and any ODD prime, can p divide both n and n+2?

 

[Kindayr]

No, for any odd prime p it is not the case for both p|n and p|n+2, for any n\in\mathbb{Z}.

 

[Kindayr]

I'm still stuck on your last hint :(

 

[Kindayr]

OOOOOH

Since p odd prime it follows that it cannot be that both p|a^{m}-1 and p|a^{m}+1. I understand why we want to do this, but what if p^2|a^{m}+1?

 

[Deveno]

last night, i started thinking about this some more, and i am wondering whether it is even true (that k is co-prime to p).

in particular i turned up this:

5 is a primitive root (generator) mod 40487 but:

5⁴⁰⁴⁸⁶ ≡ 1 (mod 40487²)

(http://mathoverflow.net/questions/2...tive-root-modulo-p-a-primitive-root-modulo-p2)

is that exactly what the problem you were given says?

 

[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!