# document.write (document.title)

 Math Help > Number Theory > Prime > Infinitude of Primes

There are infinitely many primes.  There are also infinitely many primes of various forms, including the form 5k+1, where k is an integer.  It is not known whether there are infinitely many "twin primes" (prime pairs, p and p+2, where both p and p+2 are prime).

. . . . . .

### Infinitude of primes of the form 5k+1

. . . . . .

Notes on this subject...

I've been trying to prove that there are an infinite number of primes of the form 10K+1 - ideally without quadratic residues, which I hate!, and without using the fact that it is a corollary of Dirichlet's theorem.
Just trying for fun to see if there's a slick way, and I've not come up with anything. Anyone got any good ideas please?

Hint (Jack Shotton): Your problem is equivalent to finding infinitely many primes of the form 5K+1, easily. Now, what can you say about a prime which divides x^5-1 for some integer x?

Hint (Tom Lovering): If p does not divide a, we can define the order of a modulo p as the least positive integer d such that p|a^d-1.
It is clear that if r is any positive integer such that p|a^r-1, d must divide r (if this is completely new to you, prove it!).
Now, since 5 is prime, for any a not of the form pk+1, it follows that 5 is the order of a modulo p for any prime dividing a^5-1.
Using some of this machinery, can you find a way into why Jack's solution will work?

Graeme:
From Jack's hint, what can you say about a prime, p, for which x^5 = 1 (mod p) ?
From Tom's hint,
If a <> 1 (mod p) then the order of a (mod p) is the least positive integer d such that a^d = 1 (mod p)
If a^r = 1 (mod p) then d|r (suppose it doesn't, that r=dq+s with s smaller than r; then a^(dq+s) = a^(dq) a^s = 1 (mod p), so a^s = 1 (mod p) a contradiction to the minimality of d)
Missing from Tom's hint is this: if the order of a (mod p) is q, then q|p-1
Now, let x <> 1 (mod p) and x^5 = 1 (mod p), then the order of x (mod p) divides 5 and thus is 5, so p-1 must be a multiple of 5; in other words 5k+1=p, for some k

Graeme continues:
Tom's last statement means if x^5 = 1 (mod p), then either x=1 (mod p) or p=1 (mod 5)
Or, if x^5-1 is a multiple of p, then either x-1 is a multiple of p, or else p-1 is a multiple of 5.
(Experimentally, I see x^5-1 is divisible by (x-1) and by one more factor of 5, but x^5-1 is not divisible by any other prime except those of the form 5k+1.)

So suppose there is a finite number of primes of the form 5k+1. Let x be the product of all of these.
If p is a prime factor of x^5-1, then either p is a factor of x-1 or p=1 (mod 5)

Rambling...
(x^5-1) = (x-1)(x^4+x^3+x^2+x+1) . . . . are (x-1) and (x^4+x^3+x^2+x+1) coprime?

Like David, I have been out of college for a number of years, and I don't have a lot of experience with number theory, so I'm following this discussion with interest.
I suppose the next thing we have to know in order to move forward is that if the order of a (mod p) is q then q is a factor of p-1. If that's true, then it follows from Tom's hints that if x^5 = 1 (mod p), then either p is a factor of x-1 or p=1 (mod 5).
From here, I suppose the proof would use the same trick as the "infinitude of primes" proof, which is to suppose there are finitely many primes equivalent to 1 (mod 5), and take x to be the product of all of them. Then consider the prime factors of x^5-1. At this point I'm troubled by the need to show that x^5-1 has a prime factor, p, such that p is not a factor of x-1. I addressed this by factoring (x^5-1) as (x-1)(x^4+x^3+x^2+x+1), and then showing by polynomial division that the GCD of these two factors is 5, i.e. (x-1)(x^3+2x^2+3x+4)+5=x^4+x^3+x^2+x+1. So you can take p to be any prime factor other than 5 of x^4+x^3+x^2+x+1, and then you see p does not divide x-1, and p does divide x^5-1, so p=1 (mod 5), which gives us the contradiction we were looking for.
Is it necessary to go to all this trouble? Or did I miss a key insight along the way? Thanks.
. . . . . .

Graeme,
You can make your argument a little more smooth. There is no need for
polynomial division (though you could use the remainder theorem). However,
one can simply say that if a prime number p divides both x-1 and
x^4+x^3+x^2+x+1, then x=1 mod p so substituting into the quartic p divides 5.
Geoff

### Related pages in this website

The webmaster and author of this Math Help site is Graeme McRae.