如何用简易方法证明存在素数p≡r mod n（gcd(r,n)=1且r<n）

Great question! Let's tackle this problem without invoking Dirichlet's Theorem, which relies on advanced analytic tools we want to avoid.

First, let's split the problem into two cases based on whether r is prime or composite:

Case 1: r is a prime number #

This is straightforward. Since gcd(r, n) = 1 and r < n, r itself is a prime number satisfying r ≡ r mod n. Done!

Case 2: r is a composite number #

Here, we'll use a proof by contradiction combined with the pigeonhole principle.

Assume for contradiction that there are no prime numbers p ≡ r mod n. That means every number of the form r + kn (for k ≥ 0) is composite. Note that every such number is coprime to n (since gcd(r, n) = 1, adding multiples of n preserves this coprimality).

Now, consider the infinite sequence:

• a₀ = r, a₁ = r + n, a₂ = r + 2n, ..., aₖ = r + kn, ...

Each aₖ is composite, so each has at least one prime factor. These prime factors must lie in the φ(n)-1 reduced residue classes modulo n excluding the class of r (by our contradiction assumption). Since there are only finitely many such residue classes, the pigeonhole principle tells us at least one residue class s ≠ r (with gcd(s, n) = 1) contains infinitely many prime factors of the aₖs.

Let q be a prime in this residue class (q ≡ s mod n). Then q divides infinitely many terms of the sequence aₖ. This means there are infinitely many k such that:

r + kn ≡ 0 mod q

Rearranged, this gives kn ≡ -r mod q. Since gcd(q, n) = 1 (because q ≡ s mod n and gcd(s, n) = 1), n has an inverse modulo q. Thus, there's a unique solution k ≡ c mod q (where c = -r · n⁻¹ mod q) for which q divides aₖ.

For these k values (k = c + tq for t ≥ 0), we can write:

a_{c+tq} = r + (c + tq)n = (r + cn) + tqn = q · m_t + tqn = q(m_t + tn)

where m_t = (r + cn)/q (an integer, since q divides r + cn). Now consider the sequence:

• b₀ = m₀, b₁ = m₀ + n, b₂ = m₀ + 2n, ..., b_t = m_t + tn, ...

Each b_t is coprime to n (since gcd(r + cn, n) = gcd(r, n) = 1 and gcd(q, n) = 1), and each b_t > 1 (if b_t = 1, then a_{c+tq} = q, which would mean r + cn + tqn = q—but r + cn ≡ r mod n and q ≡ s mod n, r ≠ s, so this is impossible).

This gives us an infinite sequence of composite numbers b_t, all coprime to n, whose prime factors also lie in the same φ(n)-1 residue classes as before. We could repeat this process indefinitely, constructing smaller and smaller sequences of composite numbers with the same property—but this leads to a contradiction: we can't keep decomposing composite numbers into primes from a finite set of residue classes forever without eventually hitting a prime in the r residue class (since primes are infinite, and we're excluding only one residue class from the reduced system).

Thus, our initial assumption is false: there must exist at least one prime p ≡ r mod n.

A Note on Special Cases #

For some specific n (like prime powers), we can use even simpler arguments. For example, if n = pᵏ (prime power), we can use Euler's theorem to construct numbers of the form r + mpᵏ whose prime factors either divide r (and are coprime to p) or are congruent to r modulo pᵏ.

内容的提问来源于stack exchange，提问作者liteplane