Fermat pseudoprime: Difference between revisions
Jump to navigation
Jump to search
imported>Karsten Meyer mNo edit summary |
imported>Hendra I. Nurdin m (copy-edit) |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
A composite number <math>q\ </math> is called '''Fermat pseudoprime''' to a natural base <math>a\ </math>, coprime to <math>q\ </math>, | A composite number <math>\scriptstyle q\ </math> is called a '''Fermat pseudoprime''' to a natural base <math>\scriptstyle a\ </math>, which is coprime to <math>\scriptstyle q\ </math>, if <math>\scriptstyle a^{q-1} \equiv 1 \pmod q</math>. | ||
==Restriction== | ==Restriction== | ||
It is sufficient | It is sufficient that the base <math>\scriptstyle a\ </math> satisfies <math>\scriptstyle 2 \le a \le q-2</math> because every odd number <math>\scriptstyle q\ </math> satisfies <math>\scriptstyle a^{q-1} \equiv 1 \pmod q</math> for <math>\scriptstyle a = q-1\ </math><ref>Richard E. Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, page 132, Theorem 3.4.2. </ref>. | ||
If <math>q\ </math> is a Fermat pseudoprime to base <math>a\ </math> | If <math>\scriptstyle q\ </math> is a Fermat pseudoprime to base <math>\scriptstyle a\ </math> then <math>\scriptstyle n\ </math> is a Fermat pseudoprime to base <math>\scriptstyle b\cdot q+a</math> for every integer <math>\scriptstyle b \ge 0</math>. | ||
== Odd Fermat pseudoprimes == | == Odd Fermat pseudoprimes == | ||
To every odd Fermat pseudoprime <math>\scriptstyle q\ </math> exist an even number of bases <math>\scriptstyle a\ </math>. Every base <math>\scriptstyle a\ </math> has a cobase <math>\scriptstyle a' = q - a\ </math> | To every odd Fermat pseudoprime <math>\scriptstyle q\ </math> exist an even number of bases <math>\scriptstyle a\ </math>. Every base <math>\scriptstyle a\ </math> has a cobase <math>\scriptstyle a' = q - a\ </math>. | ||
Examples | Examples: | ||
:15 is a Fermat pseudoprime to the bases 4 and 15 | :15 is a Fermat pseudoprime to the bases 4 and 15 | ||
| Line 20: | Line 20: | ||
==Properties== | ==Properties== | ||
Most of the | Most of the pseudoprimes, like [[Euler pseudoprime]]s, [[Carmichael number]]s, [[Fibonacci pseudoprime]]s and [[Lucas pseudoprime]]s, are Fermat pseudoprimes. | ||
==References and notes== | ==References and notes== | ||
| Line 26: | Line 26: | ||
== Further reading == | == Further reading == | ||
* [[Richard E. Crandall]] and [[Carl Pomerance]]: Prime Numbers | * [[Richard E. Crandall]] and [[Carl Pomerance]]: Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7 | ||
* [[Paolo Ribenboim]]: The New Book of Prime Number Records. Springer Verlag, 1996, ISBN 0-387-94457-5 | * [[Paolo Ribenboim]]: The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5 | ||
==Links== | ==Links== | ||
* [http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Pseudoprimzahlen_(15_-_4999) Table of the Fermat pseudoprimes between 15 and 4997] | * [http://de.wikibooks.org/wiki/Pseudoprimzahlen:_Tabelle_Pseudoprimzahlen_(15_-_4999) Table of the Fermat pseudoprimes between 15 and 4997] | ||
Revision as of 16:44, 8 December 2007
A composite number is called a Fermat pseudoprime to a natural base , which is coprime to , if .
Restriction
It is sufficient that the base satisfies because every odd number satisfies for [1].
If is a Fermat pseudoprime to base then is a Fermat pseudoprime to base for every integer .
Odd Fermat pseudoprimes
To every odd Fermat pseudoprime exist an even number of bases . Every base has a cobase .
Examples:
- 15 is a Fermat pseudoprime to the bases 4 and 15
- 49 is a Fermat pseudoprime to the bases 18, 19, 30 and 31
Properties
Most of the pseudoprimes, like Euler pseudoprimes, Carmichael numbers, Fibonacci pseudoprimes and Lucas pseudoprimes, are Fermat pseudoprimes.
References and notes
- ↑ Richard E. Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, page 132, Theorem 3.4.2.
Further reading
- Richard E. Crandall and Carl Pomerance: Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7
- Paolo Ribenboim: The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5