Skip to main content
Made more bulletproof.
Source Link

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its length has to be less than p to avoid one of the terms being a multiple of p, which means the original progression also has to have fewer than p terms. So the collection of primes dividing a set of arbitrarily long arithmetic progressions must be infinite.

It has been noted by GH from MO that the above overlooks some subtleties; the following is more inspired by Euclid, and should leave no doubt remaining.

Let A be a set of arbitrarily long nonconstant arithmetic progressions. Thus for any integer m, we can find a member of A and extract from that (wlog) a positive increasing arithmetic progression of the form a +kd where a and d are coprime and k goes from 0 to m. Pick a finite set of primes M, set m equal to a large multiple of their product (so at least twice the product of primes of M) and then choose from A a progression and derive the progression a +kd with the properties above. I will show the existence of a prime divisor which is not in M and divides a member of the progression.

Now d may share some factors with the product of M, but as (a,d)=1, none of the factors of d will divide any of a +kd. To be safe, let us call M' that set of numbers in M which are coprime to d, and set their product to m'. So (m',d)=1, d is a unit mod m', and we can look at ta +tkd as k runs from 1 to m which is bigger than m'. As above, td=1 mod m'.

Modulo m', ta+tkd is ta+k, so ta+k is divisible by a factor of m' precisely when a+kd is. As a result, there are k bigger than m' and at most m such that a+kd is coprime with m'. But a+kd is bigger than m' and is coprime not just to m' but to the product of all primes in M. So it must have a prime factor outside of M. So A "contains" more primes than found in any finite set of prime factors.

Clear enough?

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its length has to be less than p to avoid one of the terms being a multiple of p, which means the original progression also has to have fewer than p terms. So the collection of primes dividing a set of arbitrarily long arithmetic progressions must be infinite.

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its length has to be less than p to avoid one of the terms being a multiple of p, which means the original progression also has to have fewer than p terms. So the collection of primes dividing a set of arbitrarily long arithmetic progressions must be infinite.

It has been noted by GH from MO that the above overlooks some subtleties; the following is more inspired by Euclid, and should leave no doubt remaining.

Let A be a set of arbitrarily long nonconstant arithmetic progressions. Thus for any integer m, we can find a member of A and extract from that (wlog) a positive increasing arithmetic progression of the form a +kd where a and d are coprime and k goes from 0 to m. Pick a finite set of primes M, set m equal to a large multiple of their product (so at least twice the product of primes of M) and then choose from A a progression and derive the progression a +kd with the properties above. I will show the existence of a prime divisor which is not in M and divides a member of the progression.

Now d may share some factors with the product of M, but as (a,d)=1, none of the factors of d will divide any of a +kd. To be safe, let us call M' that set of numbers in M which are coprime to d, and set their product to m'. So (m',d)=1, d is a unit mod m', and we can look at ta +tkd as k runs from 1 to m which is bigger than m'. As above, td=1 mod m'.

Modulo m', ta+tkd is ta+k, so ta+k is divisible by a factor of m' precisely when a+kd is. As a result, there are k bigger than m' and at most m such that a+kd is coprime with m'. But a+kd is bigger than m' and is coprime not just to m' but to the product of all primes in M. So it must have a prime factor outside of M. So A "contains" more primes than found in any finite set of prime factors.

Clear enough?

Source Link

A simple proof is available as well. Pick p coprime to d and let t be such that td=1 mod p. Then, mod p, t times the arithmetic progression looks like a sequence of consecutive integers. Thus its length has to be less than p to avoid one of the terms being a multiple of p, which means the original progression also has to have fewer than p terms. So the collection of primes dividing a set of arbitrarily long arithmetic progressions must be infinite.