There are lot’s of prime conjectures that are unsolved. - Are there infinitely many primes of the form \(n^{2}+1\)? - Are there infinitely many primes of the form \(2^{n}-1\)? (Mersenne primes) - Are there infinitely many primes \(p\) where \(2p+1\) is also prime? (Sophie Germaine primes)
All of these are open questions. But here’s a solved question:
Theorem. Let \(p\) be prime. There are infinitely many primes \(q\) for which \(p\mid q-1\).
Proof. Oh actually the proof is kind of tricky. here goes.
Define the cylotomic polynomial \[f_p(x) = 1+x+x^{2}+\cdots + x^{p-1}.\]
Observation 1: \[f_p(pk) \perp pk(pk-1)\] this is pretty clear.
Observation 2: Say that prime \(q\mid f_p(pk)\). Well, we know that \[q \mid (pk)^{p}-1.\] Therefore the order \(\mod q\) of \(pk\) satisfies \(o_q(pk) \mid p\). But the divisors of \(p\) are \(\left\{ 1,p\right\}\), and the order is not \(1\). Hence, \[o_q(pk) = p.\] On the other hand, FLT says \(o_q(pk) \mid \phi(q)=q-1\).
Putting it all together gives \(q\equiv 1 \mod p\).
Ok, so we’re almost done. It will suffice to find an infinite set \(k_1,k_2,k_3,\ldots\) such that \(f_p(pk_i)\) are all pairwise coprime.
One way of doing that is the following: \[m_1=p, m_k=pf(m_1)f(m_2)f(m_3)\cdots f(m_{k-1}).\] Then, \(f(m_i)\) and \(f(m_j)\) have completely disjoint sets of prime factors, and at least one of each of their prime factors is one more than a multiple of \(p\) as desired.