## You are here

HomeEuler pseudoprime

## Primary tabs

# Euler pseudoprime

An Euler pseudoprime $p$ to a base $b$ is a composite number for which the congruence

$b^{{\frac{p-1}{2}}}\equiv\left(\frac{b}{p}\right)\mod p$ |

holds true, where $\left(\frac{a}{n}\right)$ is the Jacobi symbol.

For example, given $b=2$, our Jacobi symbol $\left(\frac{2}{p}\right)$ with $p$ odd will be either 1 or $-1$. Then, for $p=561$, the Jacobi symbol is 1. Next, we see that 2 raised to the 280th is 1942668892225729070919461906823518906642406839052139521251812409738904285205208498176, which is one more than 561 times 3462867900580622229802962400754935662464183313818430519165441015577369492344400175. Hence 561 is an Euler pseudoprime. The next few Euler pseudoprimes to base 2 are 1105, 1729, 1905, 2047, 2465, 4033, 4681 (see A047713 in Sloane’s OEIS). An Euler pseudoprime is sometimes called an Euler-Jacobi pseudoprime, to distinguish it from a pseudoprime for which the congruence can be either to 1 or $-1$ regardless of the Jacobi symbol (341 is then an Euler pseudoprime under this relaxed definition). Both terms are also sometimes used alone with 2 as the implied base.

If a composite number is an Euler pseudoprime to a given base, it is also a regular pseudoprime to that base, but not all regular pseudoprimes to that base are also Euler pseudoprimes to it.

# References

- 1 R. Crandall & C. Pomerance, Prime Numbers: A Computational Perspective, Springer, NY, 2001: 5.1
- 2 B. Fine & G. Rosenberger, Number Theory: An Introduction via the Distribution of the Primes Boston: Birkhäuser, 2007: Definition 5.3.1.4

## Mathematics Subject Classification

11A51*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections