Carmichael number - Revision history

Vipul: /* Initial examples */

2012-01-15T22:01:56Z

Initial examples

← Older revision		Revision as of 22:01, 15 January 2012
Line 27:		Line 27:
	\| [[1729]] \|\| [[7]], [[13]], [[19]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 36		\| [[1729]] \|\| [[7]], [[13]], [[19]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 36
	\|-		\|-
	\| [[2465]] \|\| [[5]], [[17]], [[29]] \|\| No \|\| Yes \|\| No \|\| No \|\| ~~Yes~~ \|\| No \|\| No \|\| No \|\| Yes \|\| No \|\|112		\| [[2465]] \|\| [[5]], [[17]], [[29]] \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\|112
	\|-		\|-
	\| [[2821]] \|\| [[7]], [[13]], [[31]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| No \|\| Yes \|\| 60		\| [[2821]] \|\| [[7]], [[13]], [[31]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| No \|\| Yes \|\| 60

Vipul: /* Definition */

2012-01-15T21:16:32Z

Definition

← Older revision		Revision as of 21:16, 15 January 2012
Line 3:		Line 3:
	==Definition==		==Definition==

	A composite number <math>n > 1</math> is termed an '''Carmichael number''' or '''absolute pseudoprime''' if it satisfies the following ~~condition~~:		A composite number <math>n > 1</math> is termed an '''Carmichael number''' or '''absolute pseudoprime''' if it satisfies the following equivalent conditions:

	* The [[defining ingredient::universal exponent]] (also called the Carmichael function) <math>\lambda(n)</math> of <math>n</math> divides <math>n - 1</math>.		# The [[defining ingredient::universal exponent]] (also called the Carmichael function) <math>\lambda(n)</math> of <math>n</math> divides <math>n - 1</math>.
	* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.		# For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
	* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.		# <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.
	* <math>n</math> is a square-free odd number greater than 1 and <math>p - 1</math> divides <math>n - 1</math> for every prime divisor <math>p</math> of <math>n</math>.		# <math>n</math> is a square-free odd number greater than 1 and <math>p - 1</math> divides <math>n - 1</math> for every prime divisor <math>p</math> of <math>n</math>.

	==Occurrence==		==Occurrence==

Vipul: /* Definition */

2012-01-15T21:16:12Z

Definition

← Older revision		Revision as of 21:16, 15 January 2012
Line 8:		Line 8:
	* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.		* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
	* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.		* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.
			* <math>n</math> is a square-free odd number greater than 1 and <math>p - 1</math> divides <math>n - 1</math> for every prime divisor <math>p</math> of <math>n</math>.

	==Occurrence==		==Occurrence==

Vipul: /* Facts */

2012-01-15T21:15:15Z

Facts

← Older revision		Revision as of 21:15, 15 January 2012
Line 34:		Line 34:

	* [[There are infinitely many Carmichael numbers]]		* [[There are infinitely many Carmichael numbers]]
			* [[Carmichael number is odd]]
			* [[Carmichael number is square-free]]
			* [[Carmichael number is not semiprime]]

Vipul: /* Initial examples */

2012-01-15T21:09:22Z

Initial examples

← Older revision		Revision as of 21:09, 15 January 2012
Line 15:		Line 15:
	<section begin="list"/>[[561]], [[1105]], [[1729]], [[2465]], [[2821]], [[6601]], <toggledisplay>8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461</toggledisplay>[[Oeis:A002997\|View list on OEIS]]<section end="list"/>		<section begin="list"/>[[561]], [[1105]], [[1729]], [[2465]], [[2821]], [[6601]], <toggledisplay>8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461</toggledisplay>[[Oeis:A002997\|View list on OEIS]]<section end="list"/>

	Note that [[Carmichael number is square-free]] and [[Carmichael number is odd]], so each of these is the product of distinct odd primes. For the first few examples, we indicate the prime factors:		Note that [[Carmichael number is square-free]] and [[Carmichael number is odd]], so each of these is the product of distinct odd primes. Further, because [[Carmichael number is not semiprime]], there are at least three prime factors of each number. For the first few examples, we indicate the prime factors:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Carmichael number !! Prime factors as list !! [[3]]? !! [[5]]?!! [[7]]? !! [[11]]? !! [[13]]? !! [[17]]? !! [[19]]? !! [[23]]? !! [[29]]? !! [[Universal exponent]] (must divide number minus one)		! Carmichael number !! Prime factors as list !! [[3]]? !! [[5]]?!! [[7]]? !! [[11]]? !! [[13]]? !! [[17]]? !! [[19]]? !! [[23]]? !! [[29]]? !! [[31]]? !! [[Universal exponent]] (must divide number minus one)
	\|-		\|-
	\| [[561]] \|\| [[3]], [[11]], [[17]] \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 80		\| [[561]] \|\| [[3]], [[11]], [[17]] \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| No \|\| 80
	\|-		\|-
	\| [[1105]] \|\| [[5]], [[13]], [[17]] \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| Yes \|\| No \|\| No \|\| No \|\| 48		\| [[1105]] \|\| [[5]], [[13]], [[17]] \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| Yes \|\| No \|\| No \|\| No \|\| No \|\| 48
	\|-		\|-
	\| [[1729]] \|\| [[7]], [[13]], [[19]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| 36		\| [[1729]] \|\| [[7]], [[13]], [[19]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 36
	\|-		\|-
	\| [[2465]] \|\| [[5]], [[17]], [[29]] \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| Yes \|\| 112		\| [[2465]] \|\| [[5]], [[17]], [[29]] \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| Yes \|\| No \|\|112
			\|-
			\| [[2821]] \|\| [[7]], [[13]], [[31]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| No \|\| Yes \|\| 60
	\|}		\|}

Vipul: /* Initial examples */

2012-01-03T21:14:00Z

Initial examples

← Older revision		Revision as of 21:14, 3 January 2012
Line 18:		Line 18:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Carmichael number !! Prime factors as list !! [[3]]? !! [[5]]?!! [[7]]? !! [[11]]? !! [[13]]? !! [[17]]? !! [[19]]? !! [[23]]? !! [[29]]? [[Universal exponent]] (must divide number minus one)		! Carmichael number !! Prime factors as list !! [[3]]? !! [[5]]?!! [[7]]? !! [[11]]? !! [[13]]? !! [[17]]? !! [[19]]? !! [[23]]? !! [[29]]? !! [[Universal exponent]] (must divide number minus one)
	\|-		\|-
	\| [[561]] \|\| [[3]], [[11]], [[17]] \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 80		\| [[561]] \|\| [[3]], [[11]], [[17]] \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 80

Vipul: /* Occurrence */

2012-01-03T21:13:30Z

Occurrence

← Older revision		Revision as of 21:13, 3 January 2012
Line 13:		Line 13:
	===Initial examples===		===Initial examples===

	<section begin="list"/>[[561]], [[1105]], [[1729]], [[2465]], ~~<toggledisplay>~~2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461</toggledisplay>[[Oeis:A002997\|View list on OEIS]]<section end="list"/>		<section begin="list"/>[[561]], [[1105]], [[1729]], [[2465]], [[2821]], [[6601]], <toggledisplay>8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461</toggledisplay>[[Oeis:A002997\|View list on OEIS]]<section end="list"/>

			Note that [[Carmichael number is square-free]] and [[Carmichael number is odd]], so each of these is the product of distinct odd primes. For the first few examples, we indicate the prime factors:

			{\| class="sortable" border="1"
			! Carmichael number !! Prime factors as list !! [[3]]? !! [[5]]?!! [[7]]? !! [[11]]? !! [[13]]? !! [[17]]? !! [[19]]? !! [[23]]? !! [[29]]? [[Universal exponent]] (must divide number minus one)
			\|-
			\| [[561]] \|\| [[3]], [[11]], [[17]] \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| 80
			\|-
			\| [[1105]] \|\| [[5]], [[13]], [[17]] \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| Yes \|\| No \|\| No \|\| No \|\| 48
			\|-
			\| [[1729]] \|\| [[7]], [[13]], [[19]] \|\| No \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| Yes \|\| No \|\| No \|\| 36
			\|-
			\| [[2465]] \|\| [[5]], [[17]], [[29]] \|\| No \|\| Yes \|\| No \|\| No \|\| Yes \|\| No \|\| No \|\| No \|\| Yes \|\| 112
			\|}

	==Facts==		==Facts==

	* [[There are infinitely many Carmichael numbers]]		* [[There are infinitely many Carmichael numbers]]

Vipul at 21:15, 2 January 2012

2012-01-02T21:15:19Z

← Older revision		Revision as of 21:15, 2 January 2012
Line 8:		Line 8:
	* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.		* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
	* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.		* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.

			==Occurrence==

			===Initial examples===

			<section begin="list"/>[[561]], [[1105]], [[1729]], [[2465]], <toggledisplay>2821, 6601, 8911, 10585, 15841, 29341, 41041, 46657, 52633, 62745, 63973, 75361, 101101, 115921, 126217, 162401, 172081, 188461, 252601, 278545, 294409, 314821, 334153, 340561, 399001, 410041, 449065, 488881, 512461</toggledisplay>[[Oeis:A002997\|View list on OEIS]]<section end="list"/>

	==Facts==		==Facts==

	* [[There are infinitely many Carmichael numbers]]		* [[There are infinitely many Carmichael numbers]]

Vipul at 17:15, 22 April 2009

2009-04-22T17:15:48Z

← Older revision		Revision as of 17:15, 22 April 2009
Line 5:		Line 5:
	A composite number <math>n > 1</math> is termed an '''Carmichael number''' or '''absolute pseudoprime''' if it satisfies the following condition:		A composite number <math>n > 1</math> is termed an '''Carmichael number''' or '''absolute pseudoprime''' if it satisfies the following condition:

	* The [[defining ingredient::~~Liouville-lambda function~~]] of <math>n</math> divides <math>n - 1</math>.		* The [[defining ingredient::universal exponent]] (also called the Carmichael function) <math>\lambda(n)</math> of <math>n</math> divides <math>n - 1</math>.
	* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.		* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
	* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.		* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.

Vipul at 22:38, 6 April 2009

2009-04-06T22:38:46Z

← Older revision		Revision as of 22:38, 6 April 2009
Line 3:		Line 3:
	==Definition==		==Definition==

	A composite number <math>n > 1</math> is termed an '''~~absolute pseudoprime~~''' or ''~~Carmichael number~~''' if it satisfies the following condition:		A composite number <math>n > 1</math> is termed an '''Carmichael number''' or '''absolute pseudoprime''' if it satisfies the following condition:

	* The [[defining ingredient::Liouville-lambda function]] of <math>n</math> divides <math>n - 1</math>.		* The [[defining ingredient::Liouville-lambda function]] of <math>n</math> divides <math>n - 1</math>.
	* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.		* For any natural number <math>a</math> relatively prime to <math>n</math>, <math>n</math> divides <math>a^{n-1} - 1</math>.
	* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.		* <math>n</math> is a [[defining ingredient::Fermat pseudoprime]] to any base relatively prime to it.

			==Facts==

			* [[There are infinitely many Carmichael numbers]]