Talk:Euler–Jacobi pseudoprime

Even numbers

I removed the even numbers because they are usually excluded, they are not useful, and the formula doesn't make sense for even n. AxelBoldt 20:39 Oct 8, 2002 (UTC)

Okay. Another thing with the definition. We do not have to say "if a and n are relatively prime", since if they would be coprime they wouldn't never satisfy the Euler's criterion.

I think that if a is a multiple of n, for instance, then the Euler criterion is satisfied, but we don't want to call n a pseudoprime to base a in that case. AxelBoldt 22:20 Oct 8, 2002 (UTC)

I wasn't quite precise. We do not need three conditions here, but just two. It is not true that for some composite numbers, which are not coprime, Euler's criterion is satisfied. So, when one composite number n for the base a satisfies the Euler's criterion and is equal to (a/n) (mod n), must be automatically coprime to a. And furthermore just these composite numbers satisfy already Euler's criterion. Euler' criterion alone is sufficient condition. We can also say:

An odd composite integer n is called an Euler pseudoprime to base a, if:

a^(n-1)/2 = 1 (mod n).

The Jacobi symbol is missing here. We actually have to require that a and n are coprime; otherwise, we would have to say that 6 is an Euler pseudoprime to base 12.

Motivation

The motivation for this definition is the fact that all prime numbers n satisfy the above equation...

I don't get the idea of this sentence. Primes which satisfy the Euler's criterion (and also above equation) are for the base a just these from the set:

{2, 11, 13, 23, 37, 47, 59, 61, 71, 73, 83, 97, 107, 109, 131, 157, 167, 179, 181, 191, 193, ...}

and not all primes. Primes from the set:

{3, 5, 7, 17, 19, 29, 31, 41, 43, 53, 67, 79, 89, 101, 103, 113, 127, 137, 139, 149, 151, 163, 173, 197, 199, ...}

do not satisfy above equation for base a=3. For instance:

3^(11-1)/2 = 1 and (3/11) (mod 11) = 1, but:

3^(5-1)/2 = 1 and (3/5) (mod 5) = 4.

What is wrong with the sentence than? --XJamRastafire 14:31 Oct 11, 2002 (UTC)

All primes n satisfy Euler's criterion

a^(n-1)/2 = (a/n) (mod n).

for any number a that's relatively prime to n. In your example, you got 4, but that's the same as -1 modulo 5.

Move

Would anyone object to my moving this page to Euler-Jacobi pseudoprime? As far as I know the definitions a^(n-1)/2 = + - 1 (mod n) for an Euler pseudoprime and a^(n-1)/2 = (a/n) (mod n) for an Euler-Jacobi pesudoprime are more well known. There are references on some pages on Wikipedia to both Euler and Euler-Jacobi pseudoprimes and if this is our definition for Euler pseudoprime then any mention of Euler-Jacobi is essentially redundant. Also the link in the article to SIDN A006970 is incorrect as it stands as it links to a sequence of what I would define as Euler pseudoprimes and not what this article defines as Euler pseudoprimes. This is the sequence that the article as it stands should link to, a sequence described as 'Euler-Jacobi pseudoprimes: 2^{(n-1)/2} == (2 / n) mod n.' Wolfram also defines these numbers as Euler-Jacobi pseudoprimes but mentions that they are sometimes known as Euler pseudoprimes.

I've also just noticed that the table is in fact wrong and is giving the numbers satisfying a^(n-1)/2 = + - 1 (mod n), i.e. 341 is an Euler pseudoprime but not an Euler-Jacobi pseudoprime, i.e. it doesn't satisfy 2^(341-1)/2 = (2/341) (mod 341), 2^(341-1)/2 = 1 (mod 341) but (2/341) = -1 (mod 341). So the table should probably stay with a new definition I guess (and I'll check the table values with a program I have to make sure that they are right, and can make a new table for the Euler-Jacobi pseudoprimes). -- Ams80 11:42 May 8, 2003 (UTC)

I have no objections as long as everything you've noticed is quite correct. I am also glad for your notifications. It is elementary article but in fact it isn't, so it would probably take some time to get a good and correct representation of what was meant to be in. See also a short prepared link for different types of pseudoprimes there at the bottom (and add or correct if necessary. I'll also allocate some more time for this article and watch it. Best regards. --XJamRastafire 13:29 May 8, 2003 (UTC)

I agree, the change makes sense and doublechecking the table is also very much appreciated. And if you can even find the time to check the links to Euler pseudoprime and Euler-Jacobi pseudoprime and make sure that everything is consistent, that would be even better. Cheers! AxelBoldt 04:37 May 9, 2003 (UTC)

Math

$a^{\frac {n-1}{2}}\equiv 1\mod n$ means the same like $(a^{\frac {n-1}{2}}\mod n)=(1\mod n)$, which you, because $1\mod n$ is 1 for every integer greater 1, could substitute to $a^{\frac {n-1}{2}}\mod n=1$.

But you shouldn't do that because you could get a contrdiction:

if a*n = b*n => a = b

but

if a mod n = b mod n !=> a = b (a is not necessarily equal b, if a mod n is equal b mod n)

let a 4, b 7 and n 3. Then it is true: 4 mod 3 = 7 mod 3, but 4 is not equal 7.

so it is better to write $4\equiv 7\mod 3$. It describe a relationship from 4 and 7 to the mod of 3. --217.233.234.42 00:05, 8 Apr 2004 (UTC)

561

561 is not the smallest absolute Euler Pseudoprime In fact 561 is Euler Pseudoprime to the primebases (2, 13, 19, 43, 47, 53, 59, 67, 83, 89, 101, 103, 127, 137, 149, 151, 157, 179, 191, 223, 229, 239, 251, 257, 263, 271, 281, 293, 307, 331, 349, 353, 359, 373, 383, 389, 409, 421, 433, 443, 457, 461, 463, 467, 491, 509, 523, 557, ). It is not epsp to 5, , 7, 23, 29, 31, ... . The smallest absolute epsp is 1729. Then follow 2465 and 15841. --Arbol01 16:11, 26 Dec 2004 (UTC)

Table corrections

There were a number of omissions in the table. I wrote some code to do the calculations myself, and have replaced the table with those results. I verified the results of my program (and thus the table) against OEIS A047713 (base 2 ejpp, checked < 10000), A048950 (base 3 ejpp, checked < 10000), A055551 (number of base 2 ejpp < 10^n, checked for n <= 8).

Here's my Haskell code:

-- computes (a ^ b) `mod` n efficiently
modpow :: (Integral a) => a -> a -> a -> a
modpow a 1 n = mod a n
modpow a b n = mod ((modpow a (div b 2) n) ^ 2 * (a ^ (mod b 2))) n

-- integer sqrt: floor (sqrt n), aka the largest integer x such that x^2 <= n
isqrt :: (Integral a) => a -> a
isqrt n = if (g * g > n) then (g - 1) else g
  where g = isqrti 1 n

isqrti :: (Integral a) => a -> a -> a
isqrti g n = if (abs (g - g1) <= 1) then (g) else (isqrti (div (g + g1) 2) n)
  where g1 = div n g

primes :: [Integer]
primes = 2:[x | x <- [3,5..], (all ((/= 0) . (mod x)) (takeWhile ((<=x).(^2)) primes))]

isPrime :: Integer -> Bool
isPrime x | x <= 1 = False
isPrime x = all ((/= 0) . (mod x)) (takeWhile ((<= x) . (^2)) primes)

jacobi :: (Integral a) => a -> a -> a
jacobi _ n | (n < 0 || even n) = error "n must be positive odd integer"
jacobi a 1                     = 1
jacobi 2 n                     = if (n `mod` 8 == 1 || n `mod` 8 == 7) then 1 else -1
jacobi a n | (gcd a n /= 1)    = 0
jacobi a n | (a > n)           = jacobi (a `mod` n) n
jacobi a n | (a `mod` 2 == 0)  = (jacobi 2 n) * (jacobi (a `div` 2) n)
jacobi a n | (a < n)           = if ((a `mod` 4 == 3) && (n `mod` 4 == 3)) then ((-1) * j) else j
  where j = jacobi n a

isEJPrime :: (Integral a) => a -> a -> Bool
isEJPrime a n | (gcd a n /= 1) = False
isEJPrime a n | (even n)       = False
isEJPrime a n                  = (modpow a ((n-1) `div` 2) n) == ((jacobi a n) `mod` n)

ejPseudoPrimes :: Integer -> [Integer]
ejPseudoPrimes a = [x | x <- [3,5..], isEJPrime a x, not (isPrime x)]

Evand (talk) 13:15, 25 October 2009 (UTC)

Euler-Jacobi pseudoprime is really Euler pseudoprime; merge them

I recommend that this page be merged into the Euler Pseudoprime page.

In primality testing, an Euler pseudoprime base a is normally defined to be a composite number n such that

$a^{(n-1)/2}\equiv (a/n){\pmod {n}}$

where (a/n) is the Jacobi symbol.

See, for example, and , or any of numerous more recent books on the subject. Wikipedia calls this an Euler-Jacobi pseudoprime.

However, Wikipedia defines an Euler pseudoprime to be a composite number n such that

$a^{(n-1)/2}\equiv \pm 1{\pmod {n}}$.

As far as I know, this definition is not used anywhere in the mathematical literature.