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!


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.

  • $\begingroup$ I don't know whether there is an elementary proof of this special case of Dirichlet's theorem, but I'd be very surprised to see it. $\endgroup$ Sep 22 '15 at 4:17
  • $\begingroup$ The question specifically asked to use Dirichlet's Theorem. Also "elementary" is not a well-defined concept. $\endgroup$
    – pre-kidney
    Sep 22 '15 at 4:19
  • $\begingroup$ Thank you so much! That was much simpler and cleaner. $\endgroup$ Sep 22 '15 at 4:43
  • $\begingroup$ "Elementary" i a matter of opinion ,but it's still a word you will see in published reearch. $\endgroup$ Sep 22 '15 at 15:18

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.