OFFSET
1,1
COMMENTS
These numbers n have the property that, for each prime divisor p, p-1 divides (n-1)/2. E.g., 2465 = 5*17*29; 1232/4 = 308; 1232/16 = 77; 1232/28 = 44. - Karsten Meyer, Nov 08 2005
All these numbers are Carmichael numbers (A002997). - Daniel Lignon, Sep 12 2015
These are odd composite numbers n such that b^((n-1)/2) == 1 (mod n) for every base b that is a quadratic residue modulo n and coprime to n. There are no odd composite numbers n such that b^((n-1)/2) == -1 (mod n) for every base b that is a quadratic non-residue modulo n and coprime to n. Note: the absolute Euler-Jacobi pseudoprimes do not exist. Theorem: if an absolute Euler pseudoprime n is a Proth number, then b^((n-1)/2) == 1 for every b coprime to n; by Proth's theorem. Such numbers are 1729, 8355841, 40280065, 53282340865, ...; for example, 1729 = 27*2^6 + 1 with 27 < 2^6. However, it seems that all absolute Euler pseudoprimes n satisfy the stronger congruence b^((n-1)/2) == 1 (mod n) for every b coprime to n, as evidenced by the modified Korselt's criterion (see the first comment). It should be noted that these are odd numbers n such that Carmichael's lambda(n) divides (n-1)/2. Also, these are odd numbers n > 1 coprime to Sum_{k=1..n-1} k^{(n-1)/2}. - Amiram Eldar and Thomas Ordowski, Apr 29 2019
Carmichael numbers k such that (p-1)|(k-1)/2 for each prime p|k. These are odd composite numbers k with half (the maximal possible fraction) of the numbers 1 <= b < k coprime to k that are bases in which k is an Euler-Jacobi pseudoprime, i.e. A329726((k-1)/2)/phi(k) = 1/2. - Amiram Eldar, Nov 20 2019
By Karsten Meyer's and Amiram Eldar's comment, this sequence is numbers k > 1 such that 2*psi(k) | (k-1), where psi = A002322. This means that if k is a term in this sequence, then we actually have a^((k-1)/2) == 1 (mod k) for every a coprime to k. - Jianing Song, Sep 03 2024
LINKS
Daniel Lignon and Dana Jacobsen, Table of n, a(n) for n = 1..10000 (first 124 terms from Daniel Lignon)
Lorenzo Di Biagio, Euler Pseudoprimes for Half of the Bases, Integers, Vol. 12, No. 6 (2012), pp. 1231-1237, arXiv preprint, arXiv:1109.3596 [math.NT] (2011).
Math Help Forum, how many absolute euler pseudoprimes less than a million, Sep 2009.
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
FORMULA
a(n) == 1 (mod 4). - Thomas Ordowski, May 02 2019
MAPLE
filter:= proc(n)
local q;
if isprime(n) then return false fi;
if 2 &^ (n-1) mod n <> 1 then return false fi;
if not numtheory:-issqrfree(n) then return false fi;
for q in numtheory:-factorset(n) do
if (n-1)/2 mod (q-1) <> 0 then return false fi
od:
true;
end proc:
select(filter, [seq(i, i=3..10^7, 2)]); # Robert Israel, Nov 24 2015
MATHEMATICA
absEulerpspQ[n_Integer?PrimeQ]:=False;
absEulerpspQ[n_Integer?EvenQ]:=False;
absEulerpspQ[n_Integer?OddQ]:=Module[{a=2},
While[a<n&&(GCD[a, n]!=1||!Unequal[PowerMod[a, (n-1)/2, n], 1, n-1]), a++];
(a==n)];
Select[Range[1, 1000000, 2], absEulerpspQ] (* Daniel Lignon, Sep 09 2015 *)
aQ[n_] := Module[{f = FactorInteger[n], p}, p=f[[;; , 1]]; Length[p] > 1 && Max[f[[;; , 2]]]==1 && AllTrue[p, Divisible[(n-1)/2, #-1] &]]; Select[Range[3, 2*10^5], aQ] (* Amiram Eldar, Nov 20 2019 *)
PROG
(Perl) use ntheory ":all"; my $n; foroddcomposites { say if is_carmichael($_) && vecall { (($n-1)>>1) % ($_-1) == 0 } factor($n=$_); } 1e6; # Dana Jacobsen, Dec 27 2015
CROSSREFS
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Dec 11 1999
EXTENSIONS
"Absolute Euler pseudoprimes" added to name by Daniel Lignon, Sep 09 2015
Definition edited by Thomas Ordowski, Apr 29 2019
STATUS
approved