For any integer $n$ there exists a prime $p$ such that the group $Z_p^*$ contains an element of order $n$

Question

Prove that for any integer $n$ there exists a prime $p$ such that the group $\mathbb Z_p^*$ contains an element of order $n$. Show that this is possible only if $p \equiv 1\pmod{n}$. And how can I prove that for fixed $n$ there are infinitely many prime numbers $p$, $p \equiv 1\pmod{n}$? Thanks.

Answer 1

Big Hint: Consider the cyclotomic polynomial $\Phi_n(x)$ and take an integer $m$ big enough.

Let $p$ be a prime divisor of $\Phi_n(m)$. The condition: $$ \Phi_n(m) \equiv 0\pmod{p} $$ implies that the order of $m$ in $\mathbb{F}_p^*$ is $n$. The Lagrange's theorem for groups hence implies $n\mid(p-1)$, or $p\equiv 1\pmod{n}$.

If we manage to prove that there exists a sequence $m_1,m_2,\ldots$ such that: $$ \forall j\neq k,\qquad \gcd\left(\Phi_n(m_j),\Phi_n(m_k)\right)=1 $$ then we have the existence of an infinite number of primes $\equiv 1\pmod{n}$.

Answer 2

Dirichlet's Theorem states that if a and b are relatively prime then the progression a,a+b,a+2b,... contains infinitely many primes. a=1 b=n. Thus the progression 1,1+n,1+2n,1+3n,... contains infinitely many primes. Take one such prime p=1+bn. Then Z_p* is a cyclic multiplicative group and n is a divisor of its order. Thus we have an element of order n in it.