I was wondering whether someone could tell me if the following proof is correct or help me out.
Claim: $\forall n \in \mathbb{N}\colon$ there exists infinitely many primes which are congruent to $1$ modulo $n$.
My strategy is using the following lemma:
$\forall x,n \in \mathbb{N}, n \mid a \colon$ there exists a prime $p$ such that the order of $x$ modulo $p$ is $n$.
I would then construct the following series: $a_1=n^n-1$, $a_i=(a_{i-1}+1)(a_{i_1})^n-1$. Each of these terms, by the lemma, would have a prime divisor $p_i$ such that the order of $a_i$ modulo $p_i$ is $n$. As a consequence, $n \mid p_i-1$. As $\gcd(p_i,p_j)=1$ if $i\neq j$ there are infinitely many such primes and we are done!
Now the issue is proving the lemma. (Assuming $n$ is composite because it is much easier otherwise) These are my ideas: Consider the smallest prime divisor $p$ of $n$. Let $n_0*p=n$.
1) Consider a prime divisor $q$ of $x^{n_0}-1$. Now $x^n-1=(x^{n_0}-1)(x^{n_0(p-1)}+\cdots+x^{n_0}+1)$. I claim $q$ does not divide the right term. This is true because it is equivalent to $p \mod q$, but $p\neq q$, since $p \mid x$.
2) So, we now must show there is a prime dividing $x^{n_0(p-1)}+\cdots+x^{n_0}+1$ which does not divide $x^p-1$, nor $x^{n_0}-1$. So it may not divide $x-1$. Note that $x^{p-1}+\cdots+x+1$ must divide $x^{n_0(p-1)}+\cdots+x^{n_0}+1$ (I think?), since $\gcd(x^{n_0}-1,x^{p-1}+\cdots+x+1)=1$. So I had the following idea: let $q$ be a divisor of $x^{p-1}+\cdots+x+1$, and let $v_q(x^{p-1}+\cdots+x+1)=l$. If I can show $v_q(x^n-1)=l$, I am done! Because clearly $x^{n_0(p-1)}+\cdots+x^{n_0}+1>x^{p-1}+\cdots+x+1$, so $x^{n_0(p-1)}+\cdots+x^{n_0}+1$ has a divisor $r$ which does not divide $x^p-1$ nor $x^{n_0}-1$, so the order of $x$ mod $r$ is $n$. <- i feel like this is a mistake
Now for the sake of contradiction, suppose $q^{l+1} \mid x^n-1=(x^p-1)(x^{p(n_0-1)}+\cdots+x^{p}+1)$. Then $q \mid (x^{p(n_0-1)}+\cdots+x^{p}+1)$. But this is congruent to $n_0 \mod q$, and $n_0 \mid x$ so clearly $\gcd(n_0,q)=1$. Thus $v_q(x^n-1)=l$ and the proof is complete. However the above only works if $\gcd(p,n_0)$ is $1$ which is not always the case?
