Euler-Jacobi pseudoprime

﻿
Euler-Jacobi pseudoprime

In number theory, an odd composite integer "n" is called an Euler-Jacobi pseudoprime to base "a", if "a" and "n" are coprime, and

: "a"("n" − 1)/2 = ("a"/"n") (mod "n"),

where ("a"/"n") is the Jacobi symbol.

The motivation for this definition is the fact that all prime numbers "n" satisfy the above equation, as explained in the Legendre symbol article. The equation can be tested rather quickly, which can be used for probabilistic primality testing. These tests are over twice as strong as tests based on Fermat's little theorem.

Every Euler-Jacobi pseudoprime is also a Fermat pseudoprime and an Euler pseudoprime. There are no numbers which are Euler-Jacobi pseudoprimes to all bases as Carmichael numbers are. Solovay and Strassen showed that for every composite "n", for at least "n"/2 bases less than "n", "n" is not an Euler-Jacobi pseudoprime.

These numbers are, in some sources, called "Euler pseudoprimes".

The table below gives all Euler-Jacobi pseudoprimes less than 10000 for some prime bases "a", this table is in the process of being checked and should be used with caution until this notice is removed.

ee also

* Probable prime

Wikimedia Foundation. 2010.

Look at other dictionaries:

• Pseudoprime — A pseudoprime is a probable prime (an integer which shares a property common to all prime numbers) which is not actually prime. Pseudoprimes can be classified according to which property they satisfy.The most important class of pseudoprimes come… …   Wikipedia

• Euler pseudoprime — An odd composite integer n is called an Euler pseudoprime to base a , if a and n are coprime, and : a^{(n 1)/2} equiv pm 1pmod{n}(where mod refers to the modulo operation).The motivation for this definition is the fact that all prime numbers p… …   Wikipedia

• Euler's criterion — In mathematics, Euler s criterion is used in determining in number theory whether a given integer is a quadratic residue modulo a prime. DefinitionEuler s criterion states: Let p be an odd prime and a an integer coprime to p . Then a is a… …   Wikipedia

• Probable prime — In number theory, a probable prime (PRP) is an integer that satisfies a specific condition also satisfied by all prime numbers. Different types of probable primes have different specific conditions. While there may be probable primes that are… …   Wikipedia

• Eulersche Pseudoprimzahl — Eine ungerade natürliche Zahl n wird eulersche Pseudoprimzahl genannt, wenn sie eine zusammengesetzte Zahl ist, die sich in Bezug auf eine zu ihr teilerfremde Basis a wie eine Primzahl verhält: wenn nämlich die Kongruenz erfüllt ist. Anders… …   Deutsch Wikipedia

• List of number theory topics — This is a list of number theory topics, by Wikipedia page. See also List of recreational number theory topics Topics in cryptography Contents 1 Factors 2 Fractions 3 Modular arithmetic …   Wikipedia

• List of mathematics articles (E) — NOTOC E E₇ E (mathematical constant) E function E₈ lattice E₈ manifold E∞ operad E7½ E8 investigation tool Earley parser Early stopping Earnshaw s theorem Earth mover s distance East Journal on Approximations Eastern Arabic numerals Easton s… …   Wikipedia

• Псевдопростое число — Натуральное число называется псевдопростым, если оно обладает некоторыми свойствами простых чисел, являясь тем не менее составным числом. В зависимости от рассматриваемых свойств существует несколько различных типов псевдопростых чисел.… …   Википедия

• Nombre pseudopremier — Un nombre pseudopremier est un nombre premier probable (un entier qui partage une propriété commune à tous les nombres premiers) qui n est pas premier. Les nombres pseudopremiers peuvent être classés par rapport à la propriété qu ils satisfont.… …   Wikipédia en Français

• Fermat number — In mathematics, a Fermat number, named after Pierre de Fermat who first studied them, is a positive integer of the form:F {n} = 2^{2^{ overset{n} {} + 1where n is a nonnegative integer. The first nine Fermat numbers are OEIS|id=A000215:As of|2008 …   Wikipedia