5 - Revision history

Vipul: /* Properties and families */

2012-07-03T18:34:39Z

Properties and families

← Older revision		Revision as of 18:34, 3 July 2012
Line 17:		Line 17:
	\|-		\|-
	\| [[satisfies property::Fermat prime]] ([[Fermat number]] that is also a [[prime number]]) \|\| \|\| {{#lst:Fermat prime\|list}} \|\| combine above		\| [[satisfies property::Fermat prime]] ([[Fermat number]] that is also a [[prime number]]) \|\| \|\| {{#lst:Fermat prime\|list}} \|\| combine above
			\|-
			\| [[satisfies property::Proth prime]]: prime of the form <math>k \cdot 2^n + 1</math> with <math>2^n > k</math> \|\| <math>n = 2, k = 1</math> \|\| {{#lst:Proth prime\|list}} \|\|
	\|-		\|-
	\| [[satisfies property::safe prime]] (prime of the form <math>2q + 1</math>, <math>q</math> prime) \|\| first safe prime \|\| {{#lst:safe prime\|list}} \|\| <math>5 = 2 \cdot 2 + 1</math>, [[2]] is prime		\| [[satisfies property::safe prime]] (prime of the form <math>2q + 1</math>, <math>q</math> prime) \|\| first safe prime \|\| {{#lst:safe prime\|list}} \|\| <math>5 = 2 \cdot 2 + 1</math>, [[2]] is prime

Vipul: /* Properties and families */

2012-07-03T18:33:44Z

Properties and families

← Older revision		Revision as of 18:33, 3 July 2012
Line 27:		Line 27:
	\|-		\|-
	\| [[satisfies property::twin primes]] (lesser member of pair) \|\| second lesser member of twin prime pair \|\| {{#lst:twin primes\|list-lesser}} \|\| 5 + 2 = [[7]] is a prime		\| [[satisfies property::twin primes]] (lesser member of pair) \|\| second lesser member of twin prime pair \|\| {{#lst:twin primes\|list-lesser}} \|\| 5 + 2 = [[7]] is a prime
			\|-
			\| [[satisfies property::near-square prime]] of the form <math>n^2 + 1</math> \|\| <math>n = 2</math> (second prime of this form) \|\| {{#lst:near-square prime\|plus-one-list}} \|\|
			\|-
	\|}		\|}

Vipul: /* Properties and families */

2012-06-23T00:54:37Z

Properties and families

← Older revision		Revision as of 00:54, 23 June 2012
Line 22:		Line 22:
	\| [[satisfies property::Sophie Germain prime]] (prime <math>p</math> such that <math>2p + 1</math> is prime \|\| third Sophie Germain prime \|\| {{#lst:Sophie Germain prime\|list}} \|\| <math>2 \cdot 5 + 1 = 11</math>, [[11]] is prime		\| [[satisfies property::Sophie Germain prime]] (prime <math>p</math> such that <math>2p + 1</math> is prime \|\| third Sophie Germain prime \|\| {{#lst:Sophie Germain prime\|list}} \|\| <math>2 \cdot 5 + 1 = 11</math>, [[11]] is prime
	\|-		\|-
	\| [[satisfies property::regular prime]] \|\| second regular prime (2 is neither regular nor irregular) \|\| {{#lst:regular prime\|list}} \|\|		\| [[satisfies property::regular prime]] \|\| second regular prime (2 is neither regular nor irregular) \|\| {{#lst:regular prime\|list}} \|\|
			\|-
			\| [[satisfies property::twin primes]] (greater member of pair) \|\| first greater member of twin prime pair \|\| {{#lst:twin primes\|list-greater}} \|\| 5 - 2 = [[3]] is a prime
			\|-
			\| [[satisfies property::twin primes]] (lesser member of pair) \|\| second lesser member of twin prime pair \|\| {{#lst:twin primes\|list-lesser}} \|\| 5 + 2 = [[7]] is a prime
	\|}		\|}

Vipul: /* Primitive roots */

2012-01-03T19:16:21Z

Primitive roots

← Older revision		Revision as of 19:16, 3 January 2012
Line 67:		Line 67:
	We note the following:		We note the following:

	* The fact that 2 is a primitive root can be deduced from the fact that [[safe prime has plus or minus two as a primitive root]], along with the fact that 5 is congruent to 5 mod 8.		* The fact that 2 is a primitive root can be deduced from the fact that [[safe prime has plus or minus two as a primitive root]], along with the fact that 5 is congruent to 5 mod 8.
			* The fact that 3 is a primitive root follows from the fact that [[Fermat prime greater than three implies three is primitive root]].

	===Quadratic residues and nonresidues===		===Quadratic residues and nonresidues===

Vipul: /* Structure of integers mod 5 */

2012-01-03T19:04:13Z

Structure of integers mod 5

← Older revision		Revision as of 19:04, 3 January 2012
Line 58:		Line 58:
	\| 4 \|\| -1 \|\| 2 \|\| No \|\| [[quadratic residue]]		\| 4 \|\| -1 \|\| 2 \|\| No \|\| [[quadratic residue]]
	\|}		\|}

			===Primitive roots===

			The ''number'' of primitive roots equals the number of generators of the additive group of integers modulo 4, which is the [[Euler totient function]] of 4, namely 2. Given any primitive root <math>a</math>, the primitive roots are precisely <math>a</math> and <math>a^3 = a^{-1}</math>.

			The explicit list of primitive roots is 2 and 3.

			We note the following:

			* The fact that 2 is a primitive root can be deduced from the fact that [[safe prime has plus or minus two as a primitive root]], along with the fact that 5 is congruent to 5 mod 8.

			===Quadratic residues and nonresidues===

			Of the four congruence classes of invertible elements, there are two classes of quadratic residues and two classes of quadratic nonresidues. Given an primitive root <math>a</math>, the quadratic residues are 1 and <math>a^2</math> and the quadratic nonresidues are <math>a</math> and <math>a^3</math>. Note that it's on account of 5 being a [[Fermat prime]] that every quadratic nonresidue is a primitive root. See [[quadratic nonresidue equals primitive root for Fermat prime]].

			Explicitly, the quadratic residues are 1 and 4. The quadratic nonresidues are 2 and 3.

Vipul: /* Structure of integers mod 5 */

2012-01-02T22:35:05Z

Structure of integers mod 5

← Older revision		Revision as of 22:35, 2 January 2012
Line 29:		Line 29:
	===Discrete logarithm===		===Discrete logarithm===

	{{~~Fermat prime~~ discrete log facts to check against}}		{{discrete log facts to check against}}

	2 is a [[primitive root]] mod 5, so we can take it as the base of the discrete logarithm. We thus get an explicit bijection from the additive group of integers mod 4 to the multiplicative group of nonzero congruence classes mod 5, given by <math>m \mapsto 2^m</math>. The inverse of that mapping is the discrete logarithm, i.e., the discrete logarithm of <math>n</math> is <math>m</math> means <math>n \equiv 2^m \pmod 5</math>:		2 is a [[primitive root]] mod 5, so we can take it as the base of the discrete logarithm. We thus get an explicit bijection from the additive group of integers mod 4 to the multiplicative group of nonzero congruence classes mod 5, given by <math>m \mapsto 2^m</math>. The inverse of that mapping is the discrete logarithm, i.e., the discrete logarithm of <math>n</math> is <math>m</math> means <math>n \equiv 2^m \pmod 5</math>:

Vipul: /* Discrete logarithm */

2012-01-02T22:25:12Z

Discrete logarithm

← Older revision		Revision as of 22:25, 2 January 2012
Line 34:		Line 34:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Congruence class mod 5 (written as smallest positive integer) !! Congruence class mod 5 (written as smallest magnitude integer) !! Discrete logarithm mod 4 !! Is it a [[primitive root]] mod 5 (if and only if the discrete log is relatively prime to 4)? !! Is it s quadratic residue or nonresidue mod 5 (residue if discrete log is even, nonresidue if odd)		! Congruence class mod 5 (written as smallest positive integer) !! Congruence class mod 5 (written as smallest magnitude integer) !! Discrete logarithm to base 2, written as integer mod 4 !! Is it a [[primitive root]] mod 5 (if and only if the discrete log is relatively prime to 4)? !! Is it s quadratic residue or nonresidue mod 5 (residue if discrete log is even, nonresidue if odd)
	\|-		\|-
	\| 1 \|\| 1 \|\| 0 \|\| No \|\| [[quadratic residue]]		\| 1 \|\| 1 \|\| 0 \|\| No \|\| [[quadratic residue]]
Line 41:		Line 41:
	\|-		\|-
	\| 3 \|\| -2 \|\| 3 \|\| Yes \|\| [[quadratic nonresidue]]		\| 3 \|\| -2 \|\| 3 \|\| Yes \|\| [[quadratic nonresidue]]
			\|-
			\| 4 \|\| -1 \|\| 2 \|\| No \|\| [[quadratic residue]]
			\|}

			We could choose an alternative discrete logarithm, where we use 3 as the base. This is simply the negative of the original discrete logarithm:

			{\| class="sortable" border="1"
			! Congruence class mod 5 (written as smallest positive integer) !! Congruence class mod 5 (written as smallest magnitude integer) !! Discrete logarithm to base 3, written as integer mod 4 !! Is it a [[primitive root]] mod 5 (if and only if the discrete log is relatively prime to 4)? !! Is it s quadratic residue or nonresidue mod 5 (residue if discrete log is even, nonresidue if odd)
			\|-
			\| 1 \|\| 1 \|\| 0 \|\| No \|\| [[quadratic residue]]
			\|-
			\| 2 \|\| 2 \|\| 3 \|\| Yes \|\| [[quadratic nonresidue]]
			\|-
			\| 3 \|\| -2 \|\| 1 \|\| Yes \|\| [[quadratic nonresidue]]
	\|-		\|-
	\| 4 \|\| -1 \|\| 2 \|\| No \|\| [[quadratic residue]]		\| 4 \|\| -1 \|\| 2 \|\| No \|\| [[quadratic residue]]
	\|}		\|}

Vipul: /* Summary */

2012-01-02T22:24:04Z

Summary

@@ Line 23: / Line 23: @@
 |-
 | [[satisfies property::regular prime]] || second regular prime (2 is neither regular nor irregular) || {{#lst:regular prime|list}} ||
 |}

Vipul: /* Properties and families */

2012-01-02T22:19:00Z

Properties and families

← Older revision		Revision as of 22:19, 2 January 2012
Line 21:		Line 21:
	\|-		\|-
	\| [[satisfies property::Sophie Germain prime]] (prime <math>p</math> such that <math>2p + 1</math> is prime \|\| third Sophie Germain prime \|\| {{#lst:Sophie Germain prime\|list}} \|\| <math>2 \cdot 5 + 1 = 11</math>, [[11]] is prime		\| [[satisfies property::Sophie Germain prime]] (prime <math>p</math> such that <math>2p + 1</math> is prime \|\| third Sophie Germain prime \|\| {{#lst:Sophie Germain prime\|list}} \|\| <math>2 \cdot 5 + 1 = 11</math>, [[11]] is prime
			\|-
			\| [[satisfies property::regular prime]] \|\| second regular prime (2 is neither regular nor irregular) \|\| {{#lst:regular prime\|list}} \|\|
	\|}		\|}

Vipul: Created page with "{{particular natural number}} ==Summary== ===Factorization=== The number 5 is a prime number. ===Properties and families=== {| class="sortable" border="1" ! Property ..."

2012-01-02T22:18:10Z

Created page with "{{particular natural number}} ==Summary== ===Factorization=== The number 5 is a prime number. ===Properties and families=== {| class="sortable" border="1" ! Property ..."

New page

{{particular natural number}}

==Summary==

===Factorization===

The number 5 is a [[prime number]].

===Properties and families===

{| class="sortable" border="1"
! Property or family !! Parameter values !! First few numbers !! Proof of satisfaction/membership/containment
|-
| [[satisfies property::prime number]] || it is the third prime number || {{#lst:prime number|list}} || divide and check
|-
| [[satisfies property::Fermat number]] <math>F_n = 2^{2^n} + 1</math> || <math>n = 1</math>, i.e., <math>F_1 = 2^{2^1} + 1</math> || {{#lst:Fermat number|list}} || plug and check
|-
| [[satisfies property::Fermat prime]] ([[Fermat number]] that is also a [[prime number]]) || || {{#lst:Fermat prime|list}} || combine above
|-
| [[satisfies property::safe prime]] (prime of the form <math>2q + 1</math>, <math>q</math> prime) || first safe prime || {{#lst:safe prime|list}} || <math>5 = 2 \cdot 2 + 1</math>, [[2]] is prime
|-
| [[satisfies property::Sophie Germain prime]] (prime <math>p</math> such that <math>2p + 1</math> is prime || third Sophie Germain prime || {{#lst:Sophie Germain prime|list}} || <math>2 \cdot 5 + 1 = 11</math>, [[11]] is prime
|}