Fermat pseudoprime: Difference between revisions
Jump to navigation
Jump to search
imported>Louise Valmoria (adding subpage template) |
imported>Karsten Meyer No edit summary |
||
| Line 1: | Line 1: | ||
{{subpages}} | {{subpages}} | ||
A composite number | A composite number <math>q\ </math> is called '''Fermat pseudoprime''' to a natural base <math>a\ </math>, coprime to <math>q\ </math>, so that <math>a^{q-1} \equiv 1 \pmod q</math> | ||
==Restriction== | ==Restriction== | ||
It is sufficient, that the base | It is sufficient, that the base <math>a\ </math> satisfy <math>2 \le a \le q-2</math> because every odd number <math>q\ </math> satisfy for <math>a = q-1\ </math> that <math>a^{q-1} \equiv 1 \pmod q</math><ref>Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag , page 132, Therem 3.4.2. </ref> | ||
If | If <math>q\ </math> is a Fermat pseudoprime to base <math>a\ </math>, then <math>n\ </math> is a Fermat pseudoprime to base <math>b\cdot q+a</math> for every integer <math>b \ge 0</math> | ||
== 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> | |||
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== | ==Properties== | ||
Revision as of 05:51, 7 December 2007
A composite number is called Fermat pseudoprime to a natural base , coprime to , so that
Restriction
It is sufficient, that the base satisfy because every odd number satisfy for that [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 pseudoprime, Carmichael number, Fibonacci pseudoprime and Lucas pseudoprime, are Fermat pseudoprimes.
References and notes
- ↑ Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag , page 132, Therem 3.4.2.
Further reading
- Richard E. Crandall and Carl Pomerance: Prime Numbers. A Computational Perspective. Springer Verlag, ISBN 0-387-25282-7
- Paolo Ribenboim: The New Book of Prime Number Records. Springer Verlag, 1996, ISBN 0-387-94457-5