[seqfan] About the congruence b^((n-1)/2) == +/-1 (mod n)

Tomasz Ordowski tomaszordowski at gmail.com
Sun May 12 17:21:18 CEST 2019

Dear SeqFans,

I defined the following pseudoprimes:

Odd composite numbers n such that b^((n-1)/2) == +-1 (mod n) for every
natural b < log(n).

46657, 162401, 399001, 488881, 1615681, 1857241, 2113921, 2433601, 3057601,
3581761, 3828001, 5148001, 5968873, 6189121, 9439201, 9613297, 10024561,
12490201, 14469841, 14676481, 15829633, 17098369, 17236801, 20964961,
23382529, 37964809, 38151361, 38624041, 40917241, 42490801, ... [Data from
Amiram Eldar].

Conjecture: These are odd composite numbers n such that b^((n-1)/2) == 1
(mod n) for every natural b < log(n).

Equivalent conjecture: These are odd composite numbers n such that
q^((n-1)/2) == 1 (mod n) for every prime q < log(n).

Amiram Eldar checked my conjecture up to n = 1.7 * 10^16.

Ask for a proof or a counterexample.

Best regards,

Thomas Ordowski
Daniel Suteu calculated that 35488761020833 is the smallest such number
that is not an absolute Euler pseudoprime, so it is not a Carmichael

It seems that all absolute Euler pseudoprimes n satisfy the stronger
b^((n-1)/2) == 1 (mod n) for every base b coprime to n.  Could this be
In their well-known definition, is a weaker condition: b^((n-1)/2) == +-1
(mod n).
Note that these pseudoprimes satisfy the modified Korselt's criterion,
odd squarefree n is such a number if and only if p-1 divides (n-1)/2 for
each prime divisor p of n,
thus these are odd numbers n such that Carmichael's lambda(n) divides
Cf. https://oeis.org/history/view?seq=A033181&v=73 (see the last comment).
See also https://www.emis.de/journals/INTEGERS/papers/a7self/a7self.pdf
These special Carmichael numbers are the absolute Euler pseudoprimes, I

More information about the SeqFan mailing list