|
|
|
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).
. . . . . .
. . . . . .
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
From the Prime Pages: There are Infinitely Many Primes, but How Big of an Infinity?
The webmaster and author of this Math Help site is Graeme McRae.