Site map 

 Contact Graeme 

 Skip Navigation LinksMath 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

 . . . . . . 

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?

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)

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

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. 

Internet references

From the Prime PagesThere are Infinitely Many Primes, but How Big of an Infinity?

Related pages in this website

The set of primes is "Large" 


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