Euler pseudoprime: Difference between revisions

From Citizendium
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'', if <math>a^{\frac {n-1}{2}} \equiv 1 \pmod n</math> or <math>a^{\frac {n-1}{2}} \equiv \left( -1\right) \pmod n</math>
{{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'', which satisfy <math>a^{(n-1)/2}\equiv\left(\frac an\right)\pmod n</math> is an [[Euler-Jacobi pseudoprime]].
*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]].
*[[Carmichael number|Carmichael numbers]] and [[Strong pseudoprime|Strong pseudoprimes]] are Euler pseudoprimes too.
*[[strong pseudoprime|Strong pseudoprimes]] are Euler pseudoprimes too.


== Absolute Euler pseudoprime ==
== Absolute Euler pseudoprime ==
An absolute Euler pseudoprime is a composite number ''c'', that satisfies the conrgruence <math>a^{\frac{c-1}{2}} \equiv 1 \pmod c </math>  or <math>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]].
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]]: Prime Numbers. A Computational Perspective. Springer Verlag, ISBN 0-387-25282-7  
* [[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
* [[Paulo Ribenboim]]. The New Book of Prime Number Records. Springer-Verlag, 1996, ISBN 0-387-94457-5
 
[[Category:Mathematics Workgroup]]
[[Category:Stub Articles]]
[[Category:CZ Live]]

Revision as of 21:54, 19 February 2010

This article is a stub and thus not approved.
Main Article
Discussion
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Citable Version  [?]
Code [?]
 
This editable Main Article is under development and subject to a disclaimer.

A composite number n is called an Euler pseudoprime to a natural base a if or

Properties

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