# Homework Help: Number Theory Help

1. Feb 16, 2012

### Kindayr

1. The problem statement, all variables and given/known data

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$.

2. Relevant equations

3. 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!

2. Feb 16, 2012

### Dick

3. Feb 16, 2012

### Kindayr

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$?

4. Feb 16, 2012

### Dick

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.

5. Feb 16, 2012

### Deveno

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

ak ≡ 1 (mod p)

i suggest asking yourself a similar, but related question:

suppose d|(p-1). how many elements of Zpx 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)

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?

Last edited: Feb 16, 2012
6. Feb 16, 2012

### Kindayr

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

7. Feb 16, 2012

### Deveno

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

8. Feb 16, 2012

### Kindayr

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

9. Feb 16, 2012

### Kindayr

$\phi (d)$ many.

10. Feb 16, 2012

### Deveno

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

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)?

11. Feb 16, 2012

### Kindayr

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

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)$.

12. Feb 16, 2012

### Deveno

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 Zpx 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 = d1,d2,...,dk = p-1

p -1 = f(d1) + f(d2) +...+ f(dk)

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

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

Last edited: Feb 16, 2012
13. Feb 16, 2012

### Kindayr

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$.

14. Feb 16, 2012

### Deveno

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) = ?$$

15. Feb 16, 2012

### Kindayr

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

16. Feb 16, 2012

### Deveno

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

f(d) ≤ φ(d)?

17. Feb 16, 2012

### Kindayr

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$.

18. Feb 16, 2012

### Deveno

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

19. Feb 16, 2012

### Kindayr

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$.

20. Feb 16, 2012

### Deveno

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 ap-1 = 1 + kp.

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

21. Feb 16, 2012

### Kindayr

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

22. Feb 16, 2012

### Deveno

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:

ap-1 = 1 + kp

but p-1 = 2m, so:

(am)2 - 1 = kp

can you do anything with that?

23. Feb 16, 2012

### Kindayr

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

24. Feb 17, 2012

### Deveno

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

25. Feb 17, 2012

### Kindayr

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$.