[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
number.
It seems that all absolute Euler pseudoprimes n satisfy the stronger
congruence:
b^((n-1)/2) == 1 (mod n) for every base b coprime to n. Could this be
true?
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,
namely:
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
(n-1)/2.
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
think.
More information about the SeqFan
mailing list