Euler pseudoprime: Difference between revisions
Jump to navigation
Jump to search
imported>Karsten Meyer mNo edit summary |
imported>Meg Taylor (copyedit) |
||
(7 intermediate revisions by 4 users not shown) | |||
Line 1: | Line 1: | ||
A composite number ''n'' is called an '''Euler pseudoprime''' to a natural base ''a'' | {{subpages}} | ||
A composite number ''n'' is called an '''Euler pseudoprime''' to a natural base ''a'' if <math>\scriptstyle a^{\frac {n-1}{2}} \equiv 1 \pmod n</math> or <math>\scriptstyle a^{\frac {n-1}{2}} \equiv \left( -1\right) \pmod n</math> | |||
== Properties == | == Properties == | ||
*Every Euler pseudoprime is odd. | *Every Euler pseudoprime is odd. | ||
*Every Euler pseudoprime is also a [[Fermat pseudoprime]]: | *Every Euler pseudoprime is also a [[Fermat pseudoprime]]: | ||
:<math>\left( a^{\frac{n-1}{2}}\right)^2 = a^{n-1}</math> | ::<math>\left( a^{\frac{n-1}{2}}\right)^2 = a^{n-1}</math> | ||
:and | ::and | ||
:<math>1^2 = \left( -1\right) ^2 = 1\ </math> | ::<math>1^2 = \left( -1\right) ^2 = 1\ </math> | ||
*Every Euler Pseudoprime to base ''a'' | *Every Euler Pseudoprime to base ''a'' that satisfies <math>\scriptstyle a^{\frac{n-1}{2}}\equiv\left(\frac an\right)\pmod n</math> is an [[Euler-Jacobi pseudoprime]]. | ||
*[[ | *[[strong pseudoprime|Strong pseudoprimes]] are Euler pseudoprimes too. | ||
== Absolute Euler pseudoprime == | == Absolute Euler pseudoprime == | ||
An absolute Euler pseudoprime is a composite number ''c'' | An absolute Euler pseudoprime is a composite number ''c'' that satisfies the congruence <math>\scriptstyle a^{\frac{c-1}{2}} \equiv 1 \pmod c </math> or <math>\scriptstyle a^{\frac {n-1}{2}} \equiv \left( -1\right) \pmod n</math> for every base ''a'' that is coprime to ''c''. Every absolute Euler pseudoprime is also a [[Carmichael number]]. | ||
== Further reading == | == Further reading == | ||
* [[Richard E. Crandall]] and [[Carl Pomerance]] | * [[Richard E. Crandall]] and [[Carl Pomerance]]. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7 | ||
* [[ | * [[Paulo Ribenboim]]. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5 | ||
Revision as of 21:54, 19 February 2010
A composite number n is called an Euler pseudoprime to a natural base a if or
Properties
- Every Euler pseudoprime is odd.
- Every Euler pseudoprime is also a Fermat pseudoprime:
- and
- Every Euler Pseudoprime to base a that satisfies is an Euler-Jacobi pseudoprime.
- Strong pseudoprimes are Euler pseudoprimes too.
Absolute Euler pseudoprime
An absolute Euler pseudoprime is a composite number c that satisfies the congruence or for every base a that is coprime to c. Every absolute Euler pseudoprime is also a Carmichael number.
Further reading
- Richard E. Crandall and Carl Pomerance. Prime Numbers: A Computational Perspective. Springer-Verlag, 2001, ISBN 0-387-25282-7
- Paulo Ribenboim. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5