Encuentra un primo $p = kn + r$ donde $\gcd(r, n) = 1$

Question

Si $r$ y $n$ son dos enteros tales que $\gcd(r, n) = 1$ y $r < n$ ¿Cómo puedo demostrar la existencia de un primo $p$ tal que $p \equiv r \bmod n$ ?

He descubierto que Teorema de Dirichlet sobre las progresiones aritméticas asegura que existe una infinidad de estos primos. Sin embargo, no puedo usarlo exactamente ni tengo las herramientas para demostrarlo.

Entonces, ¿hay alguna forma de demostrar la existencia de dicho primo con matemáticas más sencillas?

Answer 1

Lo que pides es lógicamente imposible a menos que sepas que $r$ es primo.

Supongamos que tienes un teorema que establece la existencia de "sólo un" primo $p = kn+r$ . Desde $r$ no es primo, seguramente $k \ge 1$ . Ahora aplica tu teorema al par $(r,mn)$ donde $m$ es cualquier número entero mayor que $k$ y relativamente primo a $r$ . Este nuevo primo será estrictamente mayor que $p$ y sigue siendo congruente con $r$ mod $n$ . Continuando de esta manera se obtendrá un número infinito de primos a partir de "sólo uno".