Problems & Puzzles:
Get a simple proof of this
Joseph L. Pe poses the following nice puzzle:
Prove this assertion: "for
any positive integer n, there exist two primes whose difference is a
multiple of n."
(please don't use the big guns, just a simple proof)
The same solution came from Faride Firoozbakht, Mike Oakes, Sambit
Nayak, Bill Murphy, Andrew Rupinski, Phil Carmody and J. K. Andersen.
All of the solutions used the pigeonhole principle.
Here is the way Rupinski stated the solution and a little more
than that (this is why I choose it):
Fix n. Since there are infinitely many primes, by the pigeonhole
principle there are two primes which are congruent mod n (since there are
n residue classes), so their difference will be a multiple of n.
In fact two corollaries immediately follow from the pigeonhole principle:
Cor 1) Among the first n+1 primes there must be two whose difference is a
multiple of n.
This can be strengthened further by realizing that aside from primes
dividing n, there are only phi(n) residue classes in which primes actually
Cor 2) Among the first phi(n)+1 primes not dividing n, there are two
primes whose difference is a multiple of n.
The only other explanation given by many puzzlers, based
in a big gun, was one based in the Dirichlet's theorem
about the infinitude of primes in any arithmetic progression... and so on.
Well, the curious thing here is that Dirichlet also
was the man who stated the pigeonhole principle, according to
this entry of
the Eric Weisstein's well known Mathematics Encyclopedia.
On this aspect Carmody comments:
I wasn't aware of that. I thought that the pigeon hole
principle was just something that, after it had become well known, must
have been considered as something that must _always_ have been known, and
thus would have no real discoverer. I'm sure Euclid was capable of using
such a tool, but don't know if he ever did.