# [seqfan] Re: The Euler-Fibonacci pseudoprimes

Neil Fernandez primeness at borve.org
Sun Jun 20 11:53:56 CEST 2021

```Hi again everyone,

My previous email got a little garbled.

What I meant to type was that if we split odd integers into those that
are congruent to +/-2 (mod 5) and those that aren't, then for i>5 and
u=powermod(5,(i-1)/2,i) we get

i congruent to +/-2 (mod 5)
===========================
i prime: u = -1 (no exceptions);
i composite: mostly u = neither 1 nor -1, with exceptions: u = 1 for i =
217, 13333, 16297, ..., and u = -1 for i= 7813, 121463, 195313, ....

i not congruent to +/-2 (mod 5)
===============================
i prime: u = 1 (no exceptions);
i composite: mostly u = neither 1 nor -1, with exceptions: u = 1 for i =
781, 1541, 1729,...; and there may or may not be exceptions for which u
= -1.

Neil

***

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:
>> >
>> > >
>> > > 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

```