Dirichlet's theorem for modulus eight - Revision history

Vipul at 22:00, 9 May 2009

2009-05-09T22:00:13Z

← 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 at 20:56, 7 May 2009

2009-05-07T20:56:51Z

← Older revision		Revision as of 20:56, 7 May 2009
Line 17:		Line 17:
	===Congruence class of <math>-1</math> modulo <math>8</math>===		===Congruence class of <math>-1</math> modulo <math>8</math>===

	By fact (2), <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>.		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>.		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>.

Vipul: /* Proof */

2009-05-07T18:20:05Z

Proof

← Older revision		Revision as of 18:20, 7 May 2009
Line 13:		Line 13:
	==Proof==		==Proof==

	We need to consider four congruence classes modulo <math>8</math>: <math>1,3~~,5,7~~</math>. We do these case by case.		We need to consider four congruence classes modulo <math>8</math>: <math>-3,-1,1,3</math>. We do these case by case.

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

Vipul: /* Facts used */

2009-05-07T18:18:18Z

Facts used

← Older revision		Revision as of 18:18, 7 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 ~~has~~ infinitely many pairwise relatively prime values]]		# [[uses::Nonconstant polynomial with integer coefficients and nonzero constant term takes infinitely many pairwise relatively prime values]]

	==Proof==		==Proof==

Vipul: Created page with '==Statement== For any odd natural number $a$ , there are infinitely many primes $p$ such that: $p \equiv a \pmod 8$ . ==Facts used== # [[uses::...'

2009-05-07T18:17:51Z

Created page with '==Statement== For any odd natural number <math>a</math>, there are infinitely many primes <math>p</math> such that: <math>p \equiv a \pmod 8</math>. ==Facts used== # [[uses::...'

New page

==Statement==

For any odd natural number <math>a</math>, there are infinitely many primes <math>p</math> such that:

<math>p \equiv a \pmod 8</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 has infinitely many pairwise relatively prime values]]

==Proof==

We need to consider four congruence classes modulo <math>8</math>: <math>1,3,5,7</math>. We do these case by case.

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

By fact (2), <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>.

===Congruence class of <math>3</math> modulo <math>8</math>===

By facts (1) and (2), we can deduce that <math>-2</math> is a quadratic residue modulo <math>p</math> if and only if <math>p \equiv 1,3 \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>1, 3 \pmod 8</math>. However, <math>f(n)</math> itself is <math>3</math> modulo <math>8</math>, so <math>f(n)</math> must have at least one prime divisor that is <math>3</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>3</math> modulo <math>8</math>.

Dirichlet's theorem for modulus eight - Revision history

Vipul at 22:00, 9 May 2009

Vipul at 20:56, 7 May 2009

Vipul: /* Proof */

Vipul: /* Facts used */

Vipul: Created page with '==Statement== For any odd natural number a, there are infinitely many primes p such that: p \equiv a \pmod 8. ==Facts used== # [[uses::...'

Vipul: Created page with '==Statement== For any odd natural number $a$ , there are infinitely many primes $p$ such that: $p \equiv a \pmod 8$ . ==Facts used== # [[uses::...'