Problems & Puzzles: Puzzles

Puzzle 286.  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 fall, so

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.

***



Records   |  Conjectures  |  Problems  |  Puzzles