Euler pseudoprime

From Citizendium, the Citizens' Compendium

Jump to: navigation, search


This article is a stub and thus not approved.
Main Article
Talk
Related Articles  [?]
Bibliography  [?]
External Links  [?]
Code [?]
 
http://en.citizendium.org/wiki?title=Euler_pseudoprime&printable=yes
This is a draft article, under development and not meant to be cited but you can help to improve it. These unapproved articles are subject to a disclaimer.

A composite number n is called an Euler pseudoprime to a natural base a if \scriptstyle a^{\frac {n-1}{2}} \equiv 1 \pmod n or \scriptstyle a^{\frac {n-1}{2}} \equiv \left( -1\right) \pmod n

Properties

\left( a^{\frac{n-1}{2}}\right)^2 = a^{n-1}
and
1^2 = \left( -1\right) ^2 = 1\

Absolute Euler pseudoprime

An absolute Euler pseudoprime is a composite number c that satisfies the congruence \scriptstyle a^{\frac{c-1}{2}} \equiv 1 \pmod c or \scriptstyle a^{\frac {n-1}{2}} \equiv \left( -1\right) \pmod n for every base a that is coprime to c. Every absolute Euler pseudoprime is also a Carmichael number.

Further reading

Retrieved from "http://en.citizendium.org/wiki/Euler_pseudoprime"
Views
Personal tools