Back to the index. Or to the chambers

This article has 19 links. View as Cloud or List.

Prime Proof Order Group Divisibility Divisibility In Rings Number Infinite Polynomial Ring Integer Finite Equation Superset Property Even Number Contradiction Long Division Proof That There Are Infinitely Many Primes Fermats Little Theorem Cyclotomic Polynomial

No pages link here.

Planetmath Browser (2008—2009)

BSD licence | A django site

All articles taken from PlanetMath.org snapshot under CC-BY-SA licence.

→ The original article on PlanetMath.org

Other Formats: LaTeX

New! You can click on formulas to copy the LaTeX source to your clipboard. | Math Videos

There Are An Infinite Number Of Primes Equiv M

This article proves a special case of Dirichlet's theorem, namely that for any integer , there are an infinite number of primes $p\equiv 1\pmod m$ .

Let be an odd prime not dividing , let $\Phi_k(x)$ be the $k^{\mathrm{th}}$ cyclotomic polynomial, and note that

$\displaystyle x^m-1=\Phi_m(x)\cdot\prod_{\substack{d\mid m\\ d<m}} \Phi_d(x)$

If $a\in\mathbb{Z}$ with $p\mid\Phi_m(a)$ , then clearly $p\mid a^m-1$ and thus $\gcd(a,p)=1$ . In fact, the order of $a\mod p$ is precisely

, for if it were not, say $a^d\equiv 1\pmod p$ for

, then

would be a root $\mod p$ of $\Phi_d(x)$ and thus

would have multiple roots $\mod p$ , which is a contradiction. But then, by Fermat's little theorem, we have $a^{p-1}\equiv 1\pmod p$ , so since

is the least integer with this property, 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 \mathbb{Z}[x]$ is any polynomial of degree at least one, then the factorizations of

$\displaystyle f(1),f(2),f(3),\ldots$

contain infinitely many primes. The proof is similar to Euclid's proof of the infinitude of primes. Assume not, and let $p_1,\ldots,p_k$ be all of the primes. Since

is nonconstant, choose

with $f(n)=a\neq 0$ . Then $f(n+ap_1\cdot p_2\cdots p_kx)$ is clearly divisible by

, so $g(x)=a^{-1}f(n+ap_1\cdot p_2\cdots p_kx)\in\mathbb{Z}[x]$ , and $g(m)\equiv 1\pmod {p_1\cdots p_k}$ for each $m\in\mathbb{Z}$ .

is nonconstant, so choose

such that $g(m)\neq 1$ . Then

is clearly divisible by some prime other that the

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 finite number of which can divide . The remainder must be primes $p\equiv 1\pmod m$ .

1	Polynomial Ring
1	Property
1	Proof
1	Finite
1	Superset
1	Even Number
1	Infinite
1	Integer
1	Number
1	Divisibility
1	Prime
1	Divisibility In Rings
1	Order Group
1	Equation
2	Long Division
2	Contradiction
3	Proof That There Are Infinitely Many Primes
7	Fermats Little Theorem
12	Cyclotomic Polynomial