[seqfan] Re: The Euler-Fibonacci pseudoprimes

[Neil Fernandez]

Hi Ami, Tomasz, and everyone,

If n is prime then 5^((n-1)/2) is congruent to -1 (mod n) only if n is
congruent to +/-2 (mod 5). So if composites congruent to +/-2 (mod 5)
that pass the test are sparse or non-existent then this is a nice
primality test. (For other composites, there will be primes in the same
congruence class, so the best we get is that failure of the test implies
compositeness.)

There are other nice tests too, some of which also involve 5, which I
have been meaning to publish for a long while.

Neil

In message <CAMJ5+ve0ui2-ZWga2jqcmFu2QZLvN88m3hNfjqNyfqeA8+42cQ at mail.gma
il.com>, Ami Eldar <amiram.eldar at gmail.com> writes
>Odd composites n such that F(n) == 5^{(n-1)/2} == -1 (mod n): there are no
>such numbers below 3*10^9.
>
>On Sat, Jun 19, 2021 at 5:52 PM Tomasz Ordowski <tomaszordowski at gmail.com>
>wrote:
>
>> Ami, thanks for finding these numbers!
>>
>> All pseudoprimes m found by Amiram satisfy the congruence
>> F(m) == 5^{(m-1)/2} == 1 (mod m). They are a subset of A094394.
>> Are there odd composites n such that F(n) == 5^{(n-1)/2} == -1 (mod n) ?
>> They are a proper subset (maybe empty) of A094395:
>> https://oeis.org/A094395
>>
>> Have a successful furter search!
>>
>> Tom
>>
>> pt., 18 cze 2021 o 01:22 Ami Eldar <amiram.eldar at gmail.com> napisa
(a):
>>
>> > The odd composites m such  that F(m) == 5^{(m-1)/2} == +-1 (mod m) are:
>> > 146611, 252601, 399001, 512461, 556421, 852841, 1024651, 1193221,
>> 1314631,
>> > 1857241, 1909001, 2100901, 2165801, 2603381, 2704801, 3470921, 3828001,
>> > 3942271, 4504501, 5049001, 5148001, 5481451, 6189121, 6840001, 7267051,
>> > 7519441, 7879681, 8086231, 8341201, 8719921, 9439201, 9863461, ...
>> >
>> > Best,
>> > Amiram
>> >
>> > On Thu, Jun 17, 2021 at 9:48 PM Tomasz Ordowski <
>> tomaszordowski at gmail.com>
>> > wrote:
>> >
>> > > Dear readers!
>> > >
>> > > Let F(n) = Fibonacci(n) = A000045(n).
>> > >
>> > > As is known, if p <> 5 is prime, then p | F(p-1) or p | F(p+1).
>> > > By Cassini's identity, if p <> 5 is prime, then p | F(p)^2+(-1)^p.
>> > > There are composite numbers n | F(n)^2+(-1)^n, namely
>> > > 231, 323, 377, 442, 1378, 1443, 1551, 1891, 2737, 2834, 2849, ...
>> > > Such odd numbers are A337231.
>> > > If p <> 5 is an odd prime, then F(p) == +-1 (mod p).
>> > > Such odd pseudoprimes are A094394 and A094395.
>> > >
>> > > If p <> 5 is an odd prime, then F(p) == 5^{(p-1)/2} == +-1 (mod p).
>> > > The weak Euler-Fibonacci pseudoprimes can be defined as
>> > > odd composites k such that F(k) == 5^{(k-1)/2} (mod k),
>> > > but maybe someone has already done it on the OEIS pages.
>> > > 25, 75, 125, 425, 555, 625, 1625, 1875, 1891, 3125, 4375, 13161, ...
>> > > Such pseudoprimes indivisible by 5 are 1891, 13161, 13981, 68101, ...
>> > > However, this subset is also not in the OEIS. Data from Amiram Eldar.
>> > > Consider the strong Euler-Fibonacci pseudoprimes with the full
>> condition:
>> > > F(m) == 5^{(m-1)/2} == +-1 (mod m). Are there such odd composites m?
>> > > Maybe someone will find such pseudoprimes, if they exist (in the OEIS).
>> > >
>> > > Best regards,
>> > >
>> > > Thomas Ordowski

-- 
Neil Fernandez