561 - Revision history

Vipul: /* Structure of integers mod 561 */

2012-01-05T00:17:21Z

Structure of integers mod 561

← Older revision		Revision as of 00:17, 5 January 2012
Line 41:		Line 41:
	===Abstract structure===		===Abstract structure===

	{{~~square-free number~~ multiplicative group facts to check against}}		{{multiplicative group facts to check against}}

	By the [[Chinese remainder theorem]], we have the ring decomposition:		By the [[Chinese remainder theorem]], we have the ring decomposition:

Vipul: /* Summary */

2012-01-04T23:47:07Z

Summary

← Older revision		Revision as of 23:47, 4 January 2012
Line 62:		Line 62:

	===Summary===		===Summary===

			{\| class="sortable" border="1"
			! Primality test !! Relies on ... !! Total number of candidate bases !! Number of bases wih gcd more than 1 !! Number of witnesses that are relatively prime !! Number of liars that are relatively prime !! Total number of witnesses !! Probability of picking witness !! Probability of picking liar !! Conditional probability of picking witness for relatively prime !! Conditional probability of picking liar for relatively prime
			\|-
			\| [[Fermat primality test]] \|\| [[Fermat's little theorem]] \|\| 560 \|\| 240 \|\| 0 \|\| 320 \|\| 240 \|\| 240/560 = 3/7 \|\| 4/7 \|\| 0 \|\| 1
			\|-
			\| [[Solovay-Strassen primality test]] \|\| [[Euler's criterion]] \|\| 560 \|\| 240 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?
			\|-
			\| [[Miller-Rabin primality test]] \|\| \|\| 560 \|\| 240 \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ? \|\| ?
			\|}

	===Fermat primality test===		===Fermat primality test===

Vipul: /* Primality testing */

2012-01-04T23:27:30Z

Primality testing

← Older revision		Revision as of 23:27, 4 January 2012
Line 63:		Line 63:
	===Summary===		===Summary===

	===Fermat test===		===Fermat primality test===

	~~561 is a~~ [[Fermat ~~pseudoprime~~]] to base <math>a</math> if the order of <math>a</math> mod 3 divides 560, the order of <math>a</math> mod 11 divides 560, and the order of <math>a</math> mod 17 divides 560. Each of these conditions holds for all <math>a</math> relatively prime to 561, because each of the numbers 3-1,11-1, 17-1 divides 560. Another way of putting this is that the lcm of these, which is the [[universal exponent]], divides 560.		{{further\|[[Fermat primality test]]}}

	Thus, 561 is a Fermat pseudoprime to every base relatively prime to it. Numbers with this property are termed [[Carmichael number]]s or absolute pseudoprimes. Thus, 561 is a Carmichael number. In fact, it is the smallest Carmichael number.		561 is a [[Fermat pseudoprime]] to base <math>a</math> (or equivalently, <math>a</math> is a [[Fermat liar]] for <math>n</math>) if the order of <math>a</math> mod 3 divides 560, the order of <math>a</math> mod 11 divides 560, and the order of <math>a</math> mod 17 divides 560. Each of these conditions holds for all <math>a</math> relatively prime to 561, because each of the numbers 3-1,11-1, 17-1 divides 560. Another way of putting this is that the lcm of these, which is the [[universal exponent]], divides 560.

			Thus, 561 is a Fermat pseudoprime to every base relatively prime to it (or equivalently, every number relatively prime to 561 is a [[Fermat liar]] for 561). Numbers with this property are termed [[Carmichael number]]s or absolute pseudoprimes. Thus, 561 is a Carmichael number. In fact, it is the smallest Carmichael number.

			This means that the probability of success for a single iteration of the Fermat primality test is the probability that a randomly chosen element from 1 to 560 has a common factor with 561. This is given by:

			<math>\frac{561 - \varphi(561) - 1}{561 - 1} = \frac{240}{560} = \frac{3}{7}</math>

Vipul: /* Structure of integers mod 561 */

2012-01-04T23:02:22Z

Structure of integers mod 561

← Older revision		Revision as of 23:02, 4 January 2012
Line 58:		Line 58:

	The exponents of the factor groups are 2, 10, and 16 respectively, hence the exponent of the whole group is the lcm of these, which is 80. The exponent of the multiplicative group is termed the [[universal exponent]] and denoted <math>\lambda</math>, so this is saying that <math>\lambda(561) = 80</math>).		The exponents of the factor groups are 2, 10, and 16 respectively, hence the exponent of the whole group is the lcm of these, which is 80. The exponent of the multiplicative group is termed the [[universal exponent]] and denoted <math>\lambda</math>, so this is saying that <math>\lambda(561) = 80</math>).

			==Primality testing==

			===Summary===

			===Fermat test===

			561 is a [[Fermat pseudoprime]] to base <math>a</math> if the order of <math>a</math> mod 3 divides 560, the order of <math>a</math> mod 11 divides 560, and the order of <math>a</math> mod 17 divides 560. Each of these conditions holds for all <math>a</math> relatively prime to 561, because each of the numbers 3-1,11-1, 17-1 divides 560. Another way of putting this is that the lcm of these, which is the [[universal exponent]], divides 560.

			Thus, 561 is a Fermat pseudoprime to every base relatively prime to it. Numbers with this property are termed [[Carmichael number]]s or absolute pseudoprimes. Thus, 561 is a Carmichael number. In fact, it is the smallest Carmichael number.

Vipul: /* Arithmetic functions */

2012-01-04T22:58:44Z

Arithmetic functions

← Older revision		Revision as of 22:58, 4 January 2012
Line 36:		Line 36:
	\| {{arithmetic function value\|largest prime power divisor\|17}} \|\|		\| {{arithmetic function value\|largest prime power divisor\|17}} \|\|
	\|}		\|}

			==Structure of integers mod 561==

			===Abstract structure===

			{{square-free number multiplicative group facts to check against}}

			By the [[Chinese remainder theorem]], we have the ring decomposition:

			<math>\mathbb{Z}/561\mathbb{Z} \cong \mathbb{Z}/3\mathbb{Z} \times \mathbb{Z}/11\mathbb{Z} \times \mathbb{Z}/17\mathbb{Z}</math>

			For the multiplicative group, this gives:

			<math>(\mathbb{Z}/561\mathbb{Z})^* \cong (\mathbb{Z}/3\mathbb{Z})^* \times (\mathbb{Z}/11\mathbb{Z})^* \times (\mathbb{Z}/17\mathbb{Z})^*</math>

			All groups on the right side are cyclic, and we get:

			<math>(\mathbb{Z}/561\mathbb{Z})^* \cong \mathbb{Z}/2\mathbb{Z} \times \mathbb{Z}/10\mathbb{Z} \times \mathbb{Z}/16\mathbb{Z}</math>

			This group has order <math>2 \times 10 \times 16 = 320</math> (the order of the multiplicative group is termed the [[Euler totient function]] and denoted <math>\varphi</math>, so this is saying that <math>\varphi(561) = 320</math>).

			The exponents of the factor groups are 2, 10, and 16 respectively, hence the exponent of the whole group is the lcm of these, which is 80. The exponent of the multiplicative group is termed the [[universal exponent]] and denoted <math>\lambda</math>, so this is saying that <math>\lambda(561) = 80</math>).

Vipul: /* Properties and families */

2012-01-03T20:55:53Z

Properties and families

← Older revision		Revision as of 20:55, 3 January 2012
Line 12:		Line 12:

	{\| class="sortable" border="1"		{\| class="sortable" border="1"
	! Property or family !! Parameter values !! First few numbers satisfying the property		! Property or family !! Parameter values !! First few numbers satisfying the property !! Proof of satisfaction/membership/containment
	\|-		\|-
	\| [[satisfies property::Carmichael number]] (also called absolute pseudoprime) \|\| first Carmichael number \|\| {{#lst:Carmichael number\|list}}		\| [[satisfies property::Carmichael number]] (also called absolute pseudoprime) \|\| first Carmichael number \|\| {{#lst:Carmichael number\|list}} \|\| The [[universal exponent]] is <math>\operatorname{lcm}\{3-1,11-1,17-1\} = 80</math> which divides <math>561 - 1 = 560</math>
	\|-		\|-
	\| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) \|\| second Poulet number \|\| {{#lst:Poulet number\|list}}		\| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) \|\| second Poulet number \|\| {{#lst:Poulet number\|list}} \|\| follows from its being an odd Carmichael number.
	\|}		\|}

Vipul: /* Factorization */

2012-01-03T20:44:44Z

Factorization

← Older revision		Revision as of 20:44, 3 January 2012
Line 5:		Line 5:
	===Factorization===		===Factorization===

	The factorization ~~into primes~~ is:		561 is a [[square-free number]] with prime factors [[3]], [[11]], and [[17]]. The prime factorization is:

	<math>\! 561 = 3 * 11 * 17</math>		<math>\! 561 = 3 * 11 * 17</math>

Vipul: /* Properties and families */

2012-01-02T21:12:29Z

Properties and families

← Older revision		Revision as of 21:12, 2 January 2012
Line 14:		Line 14:
	! Property or family !! Parameter values !! First few numbers satisfying the property		! Property or family !! Parameter values !! First few numbers satisfying the property
	\|-		\|-
	\| [[satisfies property::Carmichael number]] (also called absolute pseudoprime) \|\| first Carmichael number \|\| ~~[[561]], [[1105]], [[1729]]~~		\| [[satisfies property::Carmichael number]] (also called absolute pseudoprime) \|\| first Carmichael number \|\| {{#lst:Carmichael number\|list}}
	\|-		\|-
	\| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) \|\| second Poulet number \|\| {{#lst:Poulet number\|list}}		\| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) \|\| second Poulet number \|\| {{#lst:Poulet number\|list}}

Vipul: /* Properties and families */

2012-01-02T21:12:12Z

Properties and families

← Older revision		Revision as of 21:12, 2 January 2012
Line 16:		Line 16:
	\| [[satisfies property::Carmichael number]] (also called absolute pseudoprime) \|\| first Carmichael number \|\| [[561]], [[1105]], [[1729]]		\| [[satisfies property::Carmichael number]] (also called absolute pseudoprime) \|\| first Carmichael number \|\| [[561]], [[1105]], [[1729]]
	\|-		\|-
	\| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) \|\| second Poulet number \|\| ~~[[341]], [[561]], [[645]]~~		\| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) \|\| second Poulet number \|\| {{#lst:Poulet number\|list}}
	\|}		\|}

Vipul: /* Properties and families */

2012-01-02T21:10:02Z

Properties and families

@@ Line 16: / Line 16: @@
 | [[satisfies property::Carmichael number]] (also called absolute pseudoprime) || first Carmichael number || [[561]], [[1105]], [[1729]]
 |-
-| [[satisfies property::Poulet number]] ([[Fermat pseudoprime to base 2) || second Poulet number || [[341]], [[561]], [[645]]
+| [[satisfies property::Poulet number]] ([[Fermat pseudoprime]] to base 2) || second Poulet number || [[341]], [[561]], [[645]]
 |}