A033181 - OEIS

%I #82 Sep 03 2024 01:16:37

%S 1729,2465,15841,41041,46657,75361,162401,172081,399001,449065,488881,

%T 530881,656601,670033,838201,997633,1050985,1615681,1773289,1857241,

%U 2113921,2433601,2455921,2704801,3057601,3224065,3581761,3664585,3828001,4463641,4903921

%N Absolute Euler pseudoprimes: odd composite numbers n such that a^((n-1)/2) == +-1 (mod n) for every a coprime to n.

%C 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

%C All these numbers are Carmichael numbers (A002997). - _Daniel Lignon_, Sep 12 2015

%C 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

%C 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

%C 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

%H Daniel Lignon and Dana Jacobsen, <a href="/A033181/b033181.txt">Table of n, a(n) for n = 1..10000</a> (first 124 terms from Daniel Lignon)

%H Lorenzo Di Biagio, <a href="https://www.emis.de/journals/INTEGERS/papers/a7self/a7self.Abstract.html">Euler Pseudoprimes for Half of the Bases</a>, Integers, Vol. 12, No. 6 (2012), pp. 1231-1237, <a href="https://arxiv.org/abs/1109.3596">arXiv preprint</a>, arXiv:1109.3596 [math.NT] (2011).

%H Math Help Forum, <a href="http://mathhelpforum.com/number-theory/102196-how-many-absolute-euler-pseudoprimes-less-than-million.html">how many absolute euler pseudoprimes less than a million</a>, Sep 2009.

%H Louis Monier, <a href="https://doi.org/10.1016/0304-3975(80)90007-9">Evaluation and comparison of two efficient primality testing algorithms</a>, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.

%H <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>

%F a(n) == 1 (mod 4). - _Thomas Ordowski_, May 02 2019

%p filter:=  proc(n)

%p   local q;

%p   if isprime(n) then return false fi;

%p   if 2 &^ (n-1) mod n <> 1 then return false fi;

%p   if not numtheory:-issqrfree(n) then return false fi;

%p   for q in numtheory:-factorset(n) do

%p     if (n-1)/2 mod (q-1) <> 0 then return false fi

%p   od:

%p   true;

%p end proc:

%p select(filter, [seq(i,i=3..10^7,2)]); # _Robert Israel_, Nov 24 2015

%t absEulerpspQ[n_Integer?PrimeQ]:=False;

%t absEulerpspQ[n_Integer?EvenQ]:=False;

%t absEulerpspQ[n_Integer?OddQ]:=Module[{a=2},

%t While[a<n&&(GCD[a,n]!=1||!Unequal[PowerMod[a,(n-1)/2,n],1,n-1]),a++];

%t (a==n)];

%t Select[Range[1,1000000,2],absEulerpspQ] (* _Daniel Lignon_, Sep 09 2015 *)

%t 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 *)

%o (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

%Y Cf. A002997, A006970, A047713, A080075, A329726.

%K nonn

%O 1,1

%A _N. J. A. Sloane_, Dec 11 1999

%E "Absolute Euler pseudoprimes" added to name by _Daniel Lignon_, Sep 09 2015

%E Definition edited by _Thomas Ordowski_, Apr 29 2019