Number Theory: Prove there are infinitely many primes $p$ satisfying $n\mid (p-1)$

Question

I've been assigned the following problem for my homework:

For any $n\in N$ show there are infinitely many primes $p$ satisfying $n\mid (p-1)$.

I think I've proved it, but I'm uncertain since we were given a hint to use Dirichlet's Theorem and I never ended up using it. Am I missing something? Here's my proof:

Note that if a prime $p_0>2$, then $p_0$ must be odd since $p_0$ even would imply $2\mid p_0$.

Thus, $(p-1)$ is even for any prime $p>2\implies (p-1)\in 2\mathbb{N}$.

Let $n$ be even so that $n=2x_1$, some $x_1\in \mathbb{N}$.

So, if $n\mid (p_1-1)$, some arbitrary prime $p_1$, then $2x_1\mid (p_1-1)$

$\implies 2x_1c_1=p_1-1$, some $c_1\in \mathbb{N}$

$\implies (p_1-1)$ is even, which is true since we found that $(p-1)$ is even for any prime $p>2$.

Thus, $n\mid (p-1)$ for infinitely many primes for $n$ even.

Let $n$ be odd so that $n=2x_2+1$, some $x_2\in \mathbb{N}$.

So, if $n\mid (p_2-1)$, some arbitrary prime $p_2$, then $(2x_2+1)\mid (p_2-1)$.

$\implies (2x_2+1)c_2=p_2-1$

$\implies 2x_2c_2+c_2=p_2-1$

$\implies 2x_2c_2+c_2+1=p_2$, some $c_2\in \mathbb{N}$.

Note that $(c_2+1)$ must be odd, since $(c_2+1)$ even $\implies (c_2+1)=2x_3$, some $x_3\in \mathbb{N}$ $\implies p_2=2x_2+2x_3 \implies p_2$ even.

So, $p_2=2x_4+1$, some $x_4\in \mathbb{N}$, which is true since we showed that any prime $p>2$ is odd.

Thus, $n\mid (p-1)$ for infinitely many primes for $n$ odd $\implies n\mid (p-1)$ for any $n\in \mathbb{N}$. $\blacksquare$

Thanks in advance!

Answer 1

Your proof is not correct, because you started by assuming that $n$ divides $p-1$ in each of the cases. How do you know that there even is such an $n$? That is what you are trying to prove!

Here is a proof using Dirichlet's Theorem.

Dirichlet's Theorem: If $a$ and $b$ are relatively prime integers, then the arithmetic progression $$\{a,a+b,a+2b,a+3b,\cdots\}$$ contains infinitely many primes.

Let $a=1$ and $b=n$. Then $a$ and $b$ are coprime, so Dirichlet's Theorem tells us that there are infinitely many primes in the arithmetic progression $$ \{1,n+1,2n+1,3n+1,\cdots\}. $$ Let $p$ be the smallest prime (among the infinitely many) which appears. Then $p=kn+1$ for some $k$, so $n$ divides $p-1$ as desired.

Answer 2

For the proof with Dirichlet just consider the sequence:

$1,n+1,2n+,3n+1,4n+1\dots$. It contains an infinite number of primes since $1$ and $n$ are coprime. And any of these numbers satisfies $n|(kn+1)-1=kn$ as desired.