[seqfan] Re: The primality test

[Max Alekseyev]

Something is fishy about this test.
Its first part means that n is a prime or a Carmichael number. but the
second part (involving k) does let most primes pass it.
E.g., for n=7 we have k = 2^1+1 = 3,
"the number of nonnegative m < n such that m^k == m (mod n)" = 7
and
"(the number of nonnegative m < n such that -m^k == m (mod n))*k" = 3.
So, prime n=7 does not pass the test.

Regards,
Max

On Wed, Jun 16, 2021 at 6:27 AM юрий герасимов <2stepan at rambler.ru> wrote:

> Dear SequFans, what Carmichael number (> 10^8) is the least pseudoprime
> for the next primality test:
> a(n) is numbers n such that the number of nonnegative m < n such that m^n
> == m (mod n) is equal to (the number of nonnegative m < n such that -m^n ==
> m (mod n))*n and the number of nonnegative m < n such that m^k == m (mod n)
> is equal to (the number of nonnegative m < n such that -m^k == m (mod
> n))*k, where k = 2^ https://oeis.org/A007814 A007814 (n-1) + 1, where
> A007814(n) is the 2-adic valuation of n.
> P. S. The weakness of MAGMA-calculator allowed me to limit muself only an
> interval of up to 10^8.
> Sorry. Thanks. JSG.
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>