Primitive root - Revision history

Vipul: /* Known facts */

2012-01-15T21:17:56Z

Known facts

← Older revision		Revision as of 21:17, 15 January 2012
Line 81:		Line 81:
	\|-		\|-
	\| [[Quadratic nonresidue equals primitive root for Fermat prime]] \|\| [[Fermat prime]] \|\| power of 2. In fact, it is a power of a power of 2		\| [[Quadratic nonresidue equals primitive root for Fermat prime]] \|\| [[Fermat prime]] \|\| power of 2. In fact, it is a power of a power of 2
			\|-
			\| [[Fermat prime greater than three implies three is primitive root]] \|\| [[Fermat prime]] \|\| power of 2. In fact, it is a power of a power of 2, and from the given condition, it is also 1 mod 4.
	\|}		\|}

2012-01-04T23:51:12Z

← Older revision		Revision as of 23:51, 4 January 2012
Line 7:		Line 7:
	The number of primitive roots modulo <math>n</math>, if the multiplicative group is cyclic, is <math>\varphi(\varphi(n))</math> where <math>\varphi</math> is the [[Euler totient function]]. This is because the order of the multiplicative group is <math>\varphi(n)</math>, and the number of generators of a cyclic group equals the Euler phi-function of its order.		The number of primitive roots modulo <math>n</math>, if the multiplicative group is cyclic, is <math>\varphi(\varphi(n))</math> where <math>\varphi</math> is the [[Euler totient function]]. This is because the order of the multiplicative group is <math>\varphi(n)</math>, and the number of generators of a cyclic group equals the Euler phi-function of its order.

	For a proof of the characterization of natural numbers for which the multiplicative group is cyclic, see [[~~Groupprops:~~Classification of natural numbers for which the multiplicative group is cyclic]].		For a proof of the characterization of natural numbers for which the multiplicative group is cyclic, see [[Classification of natural numbers for which the multiplicative group is cyclic]].
	==Particular cases==		==Particular cases==

2012-01-04T23:50:45Z

← Older revision		Revision as of 23:50, 4 January 2012
Line 5:		Line 5:
	We often use the term '''primitive root''' for an integer representative of such a residue class.		We often use the term '''primitive root''' for an integer representative of such a residue class.

	The number of primitive roots modulo <math>n</math>, if the multiplicative group is cyclic, is <math>\varphi(\varphi(n))</math> where <math>\varphi</math> is the [[Euler ~~phi-~~function]]. This is because the order of the multiplicative group is <math>\varphi(n)</math>, and the number of generators of a cyclic group equals the Euler phi-function of its order.		The number of primitive roots modulo <math>n</math>, if the multiplicative group is cyclic, is <math>\varphi(\varphi(n))</math> where <math>\varphi</math> is the [[Euler totient function]]. This is because the order of the multiplicative group is <math>\varphi(n)</math>, and the number of generators of a cyclic group equals the Euler phi-function of its order.

			For a proof of the characterization of natural numbers for which the multiplicative group is cyclic, see [[Groupprops:Classification of natural numbers for which the multiplicative group is cyclic]].
	==Particular cases==		==Particular cases==

2012-01-02T04:25:54Z

Conjectures and conditionally known facts

← Older revision		Revision as of 04:25, 2 January 2012
Line 86:		Line 86:
	[[Artin's conjecture on primitive roots]] states that any integer that is not a [[perfect square]] and that is not equal to -1 occurs as a primitive root for infinitely many primes. The conjecture is open, but partial results are known:		[[Artin's conjecture on primitive roots]] states that any integer that is not a [[perfect square]] and that is not equal to -1 occurs as a primitive root for infinitely many primes. The conjecture is open, but partial results are known:

	{{#lst\|Artin's conjecture on primitive roots\|related}}		{{#lst:Artin's conjecture on primitive roots\|related}}

2012-01-02T04:25:29Z

Facts

← Older revision		Revision as of 04:25, 2 January 2012
Line 81:		Line 81:
	\| [[Quadratic nonresidue equals primitive root for Fermat prime]] \|\| [[Fermat prime]] \|\| power of 2. In fact, it is a power of a power of 2		\| [[Quadratic nonresidue equals primitive root for Fermat prime]] \|\| [[Fermat prime]] \|\| power of 2. In fact, it is a power of a power of 2
	\|}		\|}

			===Conjectures and conditionally known facts===

			[[Artin's conjecture on primitive roots]] states that any integer that is not a [[perfect square]] and that is not equal to -1 occurs as a primitive root for infinitely many primes. The conjecture is open, but partial results are known:

			{{#lst\|Artin's conjecture on primitive roots\|related}}

2012-01-02T04:22:58Z

Facts

← Older revision		Revision as of 04:22, 2 January 2012
Line 68:		Line 68:
	==Facts==		==Facts==

	* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]		===Known facts===
	* [[Safe prime has plus or minus two as a primitive root]]
	* [[Quadratic nonresidue equals primitive root for Fermat prime]]		For most primes, finding a primitive root is hard work. However, for those primes <math>p</math> where <math>p - 1</math> has a very small list of prime factors, it is relatively easy to find a primitive root. Some cases are below:

			{\| class="sortable" border="1"
			! Statement !! Applicable prime type !! Description in terms of factorization of <math>p - 1</math>
			\|-
			\| [[Quadratic nonresidue that is not minus one is primitive root for safe prime]] \|\| [[safe prime]] \|\| <math>p - 1</math> is twice of a prime. The prime <math>(p-1)/2</math> is called a [[Sophie Germain prime]].
			\|-
			\| [[Safe prime has plus or minus two as a primitive root]] \|\| [[safe prime]] \|\| <math>p - 1</math> is twice of a prime. The prime <math>(p-1)/2</math> is called a [[Sophie Germain prime]].
			\|-
			\| [[Quadratic nonresidue equals primitive root for Fermat prime]] \|\| [[Fermat prime]] \|\| power of 2. In fact, it is a power of a power of 2
			\|}

2012-01-02T04:18:15Z

Facts

← Older revision		Revision as of 04:18, 2 January 2012
Line 70:		Line 70:
	* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]		* [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]
	* [[Safe prime has plus or minus two as a primitive root]]		* [[Safe prime has plus or minus two as a primitive root]]
	* [[~~Fermat prime implies every quadratic~~ nonresidue ~~is a~~ primitive root]]		* [[Quadratic nonresidue equals primitive root for Fermat prime]]

2010-05-29T22:44:49Z

Relation with other properties

← Older revision		Revision as of 22:44, 29 May 2010
Line 59:		Line 59:
	===Smallests===		===Smallests===

	* [[Smallest ~~positive~~ primitive root]] is the smallest positive number that is a primitive root modulo a given number.		* [[Smallest primitive root]] is the smallest positive number that is a primitive root modulo a given number.
	* [[Smallest magnitude primitive root]] is the primitive root with the smallest absolute value.		* [[Smallest magnitude primitive root]] is the primitive root with the smallest absolute value.

2010-05-29T21:50:02Z

@@ Line 54: / Line 54: @@
 | 17 || 8 || 3,-3 || 3 || 3,5,6,7,10,11,12,14
 |}
 ==Facts==
@@ Line 59: / Line 70: @@
 * [[Quadratic nonresidue that is not minus one is primitive root for safe prime]]
 * [[Safe prime has plus or minus two as a primitive root]]

2010-05-29T21:46:46Z

Values of primitive roots