Vipul at 22:00, 9 May 2009

2009-05-09T22:00:47Z

← Older revision		Revision as of 22:00, 9 May 2009
Line 9:		Line 9:
	# [[uses::Congruence condition for two to be a quadratic residue]]		# [[uses::Congruence condition for two to be a quadratic residue]]
	# [[uses::Congruence condition for minus one to be a quadratic residue]]		# [[uses::Congruence condition for minus one to be a quadratic residue]]
	# [[uses::Nonconstant polynomial with integer coefficients and ~~nonzero~~ constant term takes infinitely many pairwise relatively prime values]]		# [[uses::Nonconstant polynomial with integer coefficients and constant term of absolute value one takes infinitely many pairwise relatively prime values]]

	==Proof==		==Proof==

Vipul: Created page with '==Statement== Suppose $a$ is an odd natural number. Then, there exist infinitely many prime numbers $p$ such that: $p \equiv a \pmod 4$ . ==Fac...'

2009-05-07T20:59:06Z

Created page with '==Statement== Suppose <math>a</math> is an odd natural number. Then, there exist infinitely many prime numbers <math>p</math> such that: <math>p \equiv a \pmod 4</math>. ==Fac...'

New page

==Statement==

Suppose <math>a</math> is an odd natural number. Then, there exist infinitely many prime numbers <math>p</math> such that:

<math>p \equiv a \pmod 4</math>.

==Facts used==

# [[uses::Congruence condition for two to be a quadratic residue]]
# [[uses::Congruence condition for minus one to be a quadratic residue]]
# [[uses::Nonconstant polynomial with integer coefficients and nonzero constant term takes infinitely many pairwise relatively prime values]]

==Proof==

We need to check two congruence classes modulo <math>4</math>: the congruence class of <math>1</math> and the congruence class of <math>-1</math>.

===The congruence class of <math>1</math> modulo <math>4</math>===

By fact (2), <math>-1</math> is a quadratic residue modulo <math>p</math> if and only if <math>p \equiv 1 \pmod 4</math>. In particular, a prime <math>p</math> can divide <math>n^2 + 1</math> for some natural number <math>n</math> if and only if <math>p \equiv 1 \pmod 4</math>.

Consider now the polynomial <math>f(x) = x^2 + 1</math>. For any natural number <math>n</math>, all prime divisors of <math>f(n)</math> are congruent to <math>1</math> modulo <math>4</math>. By fact (3), there are infinitely many pairwise relatively prime values of <math>f(n)</math>, so we get infinitely many primes that are congruent to <math>1</math> modulo <math>4</math>.

===Congruence class of <math>-1</math> modulo <math>4</math>===

By fact (1), <math>2</math> is a quadratic residue modulo <math>p</math> if and only if <math>p \equiv \pm 1 \pmod 8</math>. In particular, a prime <math>p</math> can divide <math>n^2 - 2</math> for some natural number <math>n</math> if and only if <math>p \equiv \pm 1 \pmod 8</math>.

Consider now the polynomial <math>f(x) = (2x + 1)^2 - 2 = 4x^2 + 4x - 1</math>. For any natural number <math>n</math>, all prime divisors of <math>f(n)</math> are congruent to <math>\pm 1 \pmod 8</math>. However, <math>f(n)</math> itself is <math>-1</math> modulo <math>8</math>, so <math>f(n)</math> must have at least one prime divisor that is <math>-1</math> modulo <math>8</math>. By fact (3), there are infinitely many pairwise relatively prime values of <math>f(n)</math>, yielding infinitely many distinct primes that are <math>-1</math> modulo <math>8</math>. In particular, all these primes are <math>-1</math> modulo <math>4</math>.

Dirichlet's theorem for modulus four - Revision history

Vipul at 22:00, 9 May 2009

Vipul: Created page with '==Statement== Suppose a is an odd natural number. Then, there exist infinitely many prime numbers p such that: p \equiv a \pmod 4. ==Fac...'

Vipul: Created page with '==Statement== Suppose $a$ is an odd natural number. Then, there exist infinitely many prime numbers $p$ such that: $p \equiv a \pmod 4$ . ==Fac...'