|
|
A033181
|
|
Absolute Euler pseudoprimes: odd composite numbers n such that a^((n-1)/2) == +-1 (mod n) for every a coprime to n.
|
|
10
|
|
|
1729, 2465, 15841, 41041, 46657, 75361, 162401, 172081, 399001, 449065, 488881, 530881, 656601, 670033, 838201, 997633, 1050985, 1615681, 1773289, 1857241, 2113921, 2433601, 2455921, 2704801, 3057601, 3224065, 3581761, 3664585, 3828001, 4463641, 4903921
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
|
LINKS
|
|
|
FORMULA
|
|
|
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
|
|
|
EXTENSIONS
|
"Absolute Euler pseudoprimes" added to name by Daniel Lignon, Sep 09 2015
|
|
STATUS
|
approved
|
|
|
|