Return to Answer

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for all $b\leq 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b\leq 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.

There is a simple non-analytic proof for $p\equiv 1 \bmod n$; see e.g. Proposition $3$ in this note. The proof gives a (Euclidean) argument that infinitely many primes divide the values of an integer-coefficient polynomial on the integers, and then notes that the prime divisors of the values of the $n$-th cyclotomic polynomial either divide $n$ or have remainder $1$ upon division by $n$. (The proof is well-known; I don't know the originator.) By the way, the note also contains a cute analytic argument for $p\equiv 1 \bmod 4$ giving bounds on the partial sums of the reciprocals of such primes; the argument uses representations via sums of two squares.

Edit: This paper by Murty and Thain discusses obstructions to Euclid-style proofs for various congruence classes. I believe that a proof has been carried out for $p\equiv a\bmod b$ for $(a, b)=1$ for $b= 24$ in the style of Euclid, however.

Here is an open-access paper by Keith Conrad expositing this impossibility theorem and giving some background.

Edit 2: Here is the paper I recalled with the Euclidean proof for $b= 24$; unfortunately it is not open-access. It is JSTOR however so many of you likely have institutional access.