%%% This file is part of PlanetMath snapshot of 2009-01-12
%%% Primary Title: there are an infinite number of primes $\equiv 1\mod m$
%%% Primary Category Code: 11N13
%%% Filename: ThereAreAnInfiniteNumberOfPrimesEquiv1modM.tex
%%% Version: 4
%%% Owner: rm50
%%% Author(s): CWoo, rm50
%%% PlanetMath is released under the GNU Free Documentation License.
%%% You should have received a file called fdl.txt along with this file.        
%%% If not, please write to gnu@gnu.org.
\documentclass[12pt]{article}
\pagestyle{empty}
\setlength{\paperwidth}{8.5in}
\setlength{\paperheight}{11in}

\setlength{\topmargin}{0.00in}
\setlength{\headsep}{0.00in}
\setlength{\headheight}{0.00in}
\setlength{\evensidemargin}{0.00in}
\setlength{\oddsidemargin}{0.00in}
\setlength{\textwidth}{6.5in}
\setlength{\textheight}{9.00in}
\setlength{\voffset}{0.00in}
\setlength{\hoffset}{0.00in}
\setlength{\marginparwidth}{0.00in}
\setlength{\marginparsep}{0.00in}
\setlength{\parindent}{0.00in}
\setlength{\parskip}{0.15in}

\usepackage{html}

% this is the default PlanetMath preamble.  as your knowledge
% of TeX increases, you will probably want to edit this, but
% it should be fine as is for beginners.

% almost certainly you want these
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}

% used for TeXing text within eps files
%\usepackage{psfrag}
% need this for including graphics (\includegraphics)
%\usepackage{graphicx}
% for neatly defining theorems and propositions
%\usepackage{amsthm}
% making logically defined graphics
%\usepackage{xypic}

% there are many more packages, add them here as you need them

% define commands here
\newcommand{\Ints}{\mathbb{Z}}

\begin{document}

 This article proves a special case of Dirichlet's theorem, namely that for any \htmladdnormallink{integer}{http://planetmath.org/encyclopedia/RationalInteger.html} $m>1$, there are an \htmladdnormallink{infinite}{http://planetmath.org/encyclopedia/InfiniteSubset.html} \htmladdnormallink{number}{http://planetmath.org/encyclopedia/Number.html} of \htmladdnormallink{primes}{http://planetmath.org/encyclopedia/RationalPrime.html} $p\equiv 1\pmod m$.

Let $p$ be an \htmladdnormallink{odd}{http://planetmath.org/encyclopedia/OddInteger.html} prime not dividing $m$, let $\Phi_k(x)$ be the $k^{\mathrm{th}}$ \htmladdnormallink{cyclotomic polynomial}{http://planetmath.org/encyclopedia/CyclotomicPolynomial.html}, and note that
\[x^m-1=\Phi_m(x)\cdot\prod_{\substack{d\mid m\\d<m}} \Phi_d(x)\]
If $a\in\Ints$ with $p\mid\Phi_m(a)$, then clearly $p\mid a^m-1$ and thus $\gcd(a,p)=1$. In fact, the \htmladdnormallink{order}{http://planetmath.org/encyclopedia/OrderGroup.html} of $a\mod p$ is precisely $m$, for if it were not, say $a^d\equiv 1\pmod p$ for $d<m$, then $a$ would be a \htmladdnormallink{root}{http://planetmath.org/encyclopedia/MultipleRoot.html} $\mod p$ of $\Phi_d(x)$ and thus $x^m-1$ would have \htmladdnormallink{multiple roots}{http://planetmath.org/encyclopedia/MultipleRoot.html} $\mod p$, which is a \htmladdnormallink{contradiction}{http://planetmath.org/encyclopedia/Contradiction.html}. But then, by \htmladdnormallink{Fermat's little theorem}{http://planetmath.org/encyclopedia/FermatsTheorem.html}, we have $a^{p-1}\equiv 1\pmod p$, so since $m$ is the least integer with this \htmladdnormallink{property}{http://planetmath.org/encyclopedia/Predicate.html}, we have $m\mid p-1$ so that $p\equiv 1\pmod m$.

We have thus shown that if $p\nmid m$ and $p\mid \Phi_m(a)$, then $p\equiv 1\pmod m$. The result then follows from the following claim: if $f(x)\in \Ints[x]$ is any \htmladdnormallink{polynomial}{http://planetmath.org/encyclopedia/Monomial2.html} of \htmladdnormallink{degree}{http://planetmath.org/encyclopedia/Monomial2.html} at least one, then the factorizations of
\[f(1),f(2),f(3),\ldots\]
\htmladdnormallink{contain}{http://planetmath.org/encyclopedia/ProperSuperset.html} infinitely many primes. The \htmladdnormallink{proof}{http://planetmath.org/encyclopedia/Proof.html} is similar to \htmladdnormallink{Euclid's proof of the infinitude of primes}{http://planetmath.org/encyclopedia/ProofThatThereAreInfinitelyManyPrimes.html}. Assume not, and let $p_1,\ldots,p_k$ be all of the primes. Since $f$ is nonconstant, choose $n$ with $f(n)=a\neq 0$. Then $f(n+ap_1\cdot p_2\cdots p_kx)$ is clearly \htmladdnormallink{divisible}{http://planetmath.org/encyclopedia/DivisibilityOfIdeals.html} by $a$, so $g(x)=a^{-1}f(n+ap_1\cdot p_2\cdots p_kx)\in\Ints[x]$, and $g(m)\equiv 1\pmod {p_1\cdots p_k}$ for each $m\in\Ints$. $g$ is nonconstant, so choose $m$ such that $g(m)\neq 1$. Then $g(m)$ is clearly divisible by some prime other that the $p_i$ and thus $f(n+ap_1\cdot p_2\cdots p_kx)$ is as well. Contradiction.

Thus the set $\Phi_m(1),\Phi_m(2),\ldots$ contains an infinite number of primes in their factorizations, only a \htmladdnormallink{finite}{http://planetmath.org/encyclopedia/Finite.html} number of which can \htmladdnormallink{divide}{http://planetmath.org/encyclopedia/Multiple2.html} $m$. The \htmladdnormallink{remainder}{http://planetmath.org/encyclopedia/DivisionAlgorithm2.html} must be primes $p\equiv 1\pmod m$.

\end{document}