A006970 -id:A006970 - cp's OEIS frontend

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

3277, 3281, 29341, 49141, 80581, 88357, 104653, 121463, 196093, 314821, 320167, 458989, 476971, 489997, 491209, 721801, 800605, 838861, 873181, 877099, 973241, 1004653, 1251949, 1268551, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1590751, 1678541, 1809697

Offset: 1

Thomas Ordowski, Apr 27 2019

nonn

As is well known, for an odd prime p, b(p) is the smallest quadratic non-residue b modulo p if and only if b(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p). Note that b(n) is always a prime.
Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as above. This is true for odd primes n; is it for odd composites n? If so, then all composite numbers n such that 2^((n-1)/2) == -1 (mod n) are in this sequence.
It seems that, for defined pseudoprimes n (similar to the odd primes p),
b(n) is the smallest base b such that b^((n-1)/2) == -1 (mod n), although this is not required by their definition.
Note: a "non-residue" pseudoprime n is a strong pseudoprime to base b(n); the Jacobi symbol (b(n)/n) = -1, where b(n) is the smallest non-residue modulo n; such a pseudoprime n is not a Proth number, so n = k*2^m + 1 with odd k > 2^m.
Problem: are there infinitely many such numbers?

			2^((3277-1)/2) == -1 (mod 3277), 3^((3281-1)/2) == -1 (mod 3281), ...

Cf. A001262, A006970, A020649, A047713, A053760, A244626, A307798 (the "residue" pseudoprimes), A307809.

residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; aQ[n_] := CompositeQ[n] && PowerMod[A020649[n], ((n - 1)/2), n] == n - 1; Select[Range[3, 110000, 2], aQ] (* Amiram Eldar, Apr 27 2019 *)

More terms from Amiram Eldar, Apr 27 2019

A214151 Numbers k from the set == 5 (mod 6) with the property that 3^((3*k-1)/2) == 3 (mod k) and 2^((k-1)/2) == (k-1) (mod k).

Original entry on oeis.org

11, 59, 83, 107, 131, 179, 227, 251, 347, 419, 443, 467, 491, 563, 587, 659, 683, 827, 947, 971, 1019, 1091, 1163, 1187, 1259, 1283, 1307, 1427, 1451, 1499, 1523, 1571, 1619, 1667, 1787, 1811, 1907, 1931, 1979, 2003, 2027, 2099, 2243, 2267

Offset: 1

Alzhekeyev Ascar M, Jul 05 2012

nonn

All composites in this sequence are 2-pseudoprimes, see A001567, and strong pseudoprimes to base 2, A001262.
The subsequence of these composites begins: 1441091, 3587553971, 4528686251, 23260036451, 47535120323, 61070250323, 90474845819, 143193768587, 162016315907, 173868807611, 180998962187, 238364070323, 285370693931, 298577370323, ...
Perhaps this sequence contains all the terms of the sequence A107007 or A168539.

Harvey P. Dale, Table of n, a(n) for n = 1..1000

Subsequence of A176997.

Cf. A003629, A006970, A175865.

isA214151 := proc(n)
    if (n mod 6 = 5) and modp(2 &^ ((n-1)/2),n)  = n-1 and modp(3 &^ ((3*n-1)/2),n)  = 3 then
        true;
    else
        false;
    end if;
end proc:
for n from 5 by 6 do
    if isA214151(n) then
        print(n) ;
    end if;
end do: # R. J. Mathar, Jul 20 2012

Select[Range[5,2500,6],PowerMod[3,(3#-1)/2,#]==3&&PowerMod[2,(#-1)/2,#] == #-1&] (* Harvey P. Dale, Mar 14 2022 *)

for(n=0, 200, b=6*n+5; if(Mod(3, b)^((3*b-1)/2)==3, if(Mod(2, b)^((b-1)/2)==b-1 , print1(b, ", "))));

A227136 Fermat pseudoprimes to base 2 which are not Euler pseudoprimes to base 2.

Original entry on oeis.org

645, 1387, 2701, 2821, 4369, 4371, 7957, 8911, 11305, 13741, 13747, 13981, 14491, 18721, 19951, 23001, 23377, 30889, 31417, 31609, 35333, 39865, 41665, 55245, 57421, 60701, 60787, 63973, 68101, 72885, 83665, 88561, 91001, 93961, 101101, 107185, 121465

Offset: 1

José María Grau Ribas, Jul 02 2013

nonn

These numbers can be factored by finding k = 2^((n-1)/2) mod n and taking gcd(k-1, n) and gcd(k+1, n). This is a special case of Kraitchik's method. - Charles R Greathouse IV, Dec 27 2013

Numbers n such that 2^(n-1) == 1 (mod n) and 2^((n-1)/2) != +-1 (mod n). - Thomas Ordowski, Feb 25 2016

Charles R Greathouse IV, Table of n, a(n) for n = 1..10000
Eric W. Weisstein, MathWorld: Euler Pseudoprime
Eric W. Weisstein, MathWorld: Fermat Pseudoprime

Cf. A001567, A006970.

Select[Range[1000000], PowerMod[2, #-1, #] == 1 && ! PowerMod[2, (#-1)/2, #] == 1 && ! PowerMod[2, (#-1)/2, #] == # -1 &]

is(n)=my(k=Mod(2,n)^(n\2)); k^2==1 && n%2 && k!=1 && k!=-1 \\ Charles R Greathouse IV, Dec 27 2013

A263239 Euler pseudoprimes to base 9: composite integers such that abs(9^((n - 1)/2)) == 1 mod n.

Original entry on oeis.org

4, 28, 91, 121, 286, 532, 671, 703, 949, 1036, 1105, 1541, 1729, 1891, 2465, 2665, 2701, 2821, 3281, 3367, 3751, 4636, 4961, 5551, 6364, 6601, 7381, 8401, 8911, 10585, 11011, 11476, 12403, 14383, 15203, 15457, 15841, 16471, 16531, 18721, 19345, 19684, 23521, 24046, 24661, 24727

Offset: 1

Daniel Lignon, Oct 12 2015

nonn

Even numbers are permitted since 9 is an integer square. - Charles R Greathouse IV, Oct 12 2015

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..116 from Daniel Lignon)

Cf. A020138 (pseudoprimes to base 9).

Cf. A006970 (base 2), A262051 (base 3), A262052 (base 5), A262053 (base 6), A262054 (base 7), A262055 (base 8).

eulerPseudo9Q[n_]:=(Mod[9^((n-1)/2)+1,n]==0 ||Mod[9^((n-1)/2)-1,n]==0) && Not[PrimeQ[n]];
Select[Range[2,200000],eulerPseudo9Q]

is(n) = abs(centerlift(Mod(3, n)^(n-1)))==1 && !isprime(n) && n>1 \\ Charles R Greathouse IV, Oct 12 2015

A309284 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == -1 (mod k) and b^((k-1)/2) == 1 (mod k) for every natural b < prime(n).

Original entry on oeis.org

3277, 5173601, 2329584217, 188985961, 5113747913401, 30990302851201, 2528509579568281, 5189206896360728641, 12155831039329417441

Offset: 1

Thomas Ordowski, Jul 21 2019

a(n) is an Euler pseudoprime to base 2, so it is also a Fermat pseudoprime to base 2.
This sequence is analogous to the sequence A000229 of primes.
Conjecture: the smallest quadratic non-residue modulo a(n) is prime(n), i.e., A020649(a(n)) = prime(n).
a(10) <= 41154189126635405260441. - Daniel Suteu, Jul 22 2019

Cf. A000229, A001567, A006970, A307767, A309285.

isok(n,k) = (k%2==1) && !isprime(k) && Mod(prime(n), k)^((k-1)/2) == Mod(-1, k) && !for(b=2, prime(n)-1, if(Mod(b, k)^((k-1)/2) != Mod(1, k), return(0)));
a(n) = for(k=9, oo, if(isok(n, k), return(k))); \\ Daniel Suteu, Jul 22 2019

According to the data, b^((a(n)-1)/2) == (b / a(n)) (mod a(n)) for every natural b <= prime(n), where (x / y) is the Jacobi symbol.

a(5)-a(9) from Amiram Eldar, Jul 21 2019

A309285 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == 1 (mod k) and q^((k-1)/2) == -1 (mod k) for every prime q < prime(n).

Original entry on oeis.org

341, 29341, 48354810571, 493813961816587, 32398013051587

Offset: 1

Thomas Ordowski, Jul 21 2019

a(n) is an Euler pseudoprime to base 2, so it is also a Fermat pseudoprime to base 2.
This sequence is analogous to the sequence A307965 of primes.
Conjecture: the smallest prime quadratic residue modulo a(n) is prime(n).
a(6) <= 35141256146761030267, a(7) <= 4951782572086917319747. - Daniel Suteu, Jul 22 2019

Cf. A001567, A006970, A307798, A307965, A309284.

isok(n,k) = (k%2==1) && !isprime(k) && Mod(prime(n), k)^((k-1)/2) == Mod(1, k) && !forprime(q=2, prime(n)-1, if(Mod(q, k)^((k-1)/2) != Mod(-1, k), return(0)));
a(n) = for(k=9, oo, if(isok(n, k), return(k))); \\ Daniel Suteu, Jul 22 2019

According to the data, for n > 1, q^((a(n)-1)/2) == (q / a(n)) (mod a(n)) for every prime q <= prime(n), where (x / y) is the Jacobi symbol.

a(4)-a(5) from Amiram Eldar, Jul 21 2019

A336689 Composite numbers k such that the decimal expansion of ((1/2^((k-1)/2))+1)/k or ((1/2^((k-1)/2))-1)/k is finite.

Original entry on oeis.org

15, 25, 75, 125, 175, 325, 341, 375, 425, 561, 625, 645, 1105, 1729, 1875, 1905, 2047, 2465, 3125, 3277, 4033, 4375, 4681, 5461, 6025, 6601, 8125, 8321, 8481, 8625, 9375, 10261, 10585, 10625, 12025, 12801, 15625, 15709, 15841, 16705, 16725, 18705, 25761, 29341

Offset: 1

Davide Rotondo, Jul 31 2020

If (1/2^((k-1)/2))+-1 divided by k results in a finite decimal number, k is prime or pseudoprime.
Euler pseudoprimes: A006970 are a subsequence.
If k is a power of 5, both +1 and -1 result in a finite decimal number.
A composite integer is part of this list, if and only if
(((n-1)!-1)*(1/(2^((n-1)/2)))+1)/n or (((n-1)!-1)*(1/(2^((n-1)/2)))-1)/n results in a finite decimal number.

			15 is a term because ((1/(2^7))+1)/15 = 0.0671875.
9 is not a term because ((1/(2^4))+-1)/9 = 0.11805555... and -0.10416666... .

Cf. A006970 (Euler pseudoprimes, a subsequence), A003592, A334834.

A003592Q[n_] := n/2^IntegerExponent[n, 2]/5^IntegerExponent[n, 5] == 1; seqQ[n_] := CompositeQ[n] && (A003592Q[Denominator[((1/2^((n-1)/2)) + 1)/n]] || A003592Q[ Denominator[((1/2^((n-1)/2)) - 1)/n]]); Select[Range[1, 30000, 2], seqQ] (* Amiram Eldar, Jul 31 2020 *)

More terms from Amiram Eldar, Jul 31 2020

A354689 Smallest Euler pseudoprime to base n.

Original entry on oeis.org

9, 341, 121, 341, 217, 185, 25, 9, 91, 9, 133, 65, 21, 15, 341, 15, 9, 25, 9, 21, 65, 21, 33, 25, 217, 9, 65, 9, 15, 49, 15, 25, 545, 21, 9, 35, 9, 39, 133, 39, 21, 451, 21, 9, 133, 9, 65, 49, 25, 21, 25, 51, 9, 55, 9, 33, 25, 57, 15, 341, 15, 9, 341, 9, 33, 65

Offset: 1

Jinyuan Wang, Jun 03 2022

nonn

An Euler pseudoprime to the base b is a composite number k which satisfies b^((k-1)/2) == +-1 (mod k).

Eric Weisstein's World of Mathematics, Euler Pseudoprime.

Cf. A006970, A090086, A298756, A326614.

a(n) = my(m); forcomposite(k=3, oo, if(k%2 && ((m=Mod(n, k)^(k\2))==1 || m==k-1), return(k)));

from sympy import isprime
from itertools import count
def a(n): return next(k for k in count(3, 2) if not isprime(k) and ((r:=pow(n, (k-1)//2, k)) == 1 or r == k-1))
print([a(n) for n in range(1, 67)]) # Michael S. Branicky, Jun 03 2022

a(n) = 9 for n == 1 or 8 (mod 9).

cp's OEIS Frontend

A307767 The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A214151 Numbers k from the set == 5 (mod 6) with the property that 3^((3*k-1)/2) == 3 (mod k) and 2^((k-1)/2) == (k-1) (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

A227136 Fermat pseudoprimes to base 2 which are not Euler pseudoprimes to base 2.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A263239 Euler pseudoprimes to base 9: composite integers such that abs(9^((n - 1)/2)) == 1 mod n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A309284 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == -1 (mod k) and b^((k-1)/2) == 1 (mod k) for every natural b < prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions

A309285 a(n) is the smallest odd composite k such that prime(n)^((k-1)/2) == 1 (mod k) and q^((k-1)/2) == -1 (mod k) for every prime q < prime(n).

Views

Author

Keywords

Comments

Crossrefs

Programs

PARI

Formula

Extensions

A336689 Composite numbers k such that the decimal expansion of ((1/2^((k-1)/2))+1)/k or ((1/2^((k-1)/2))-1)/k is finite.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Extensions

A354689 Smallest Euler pseudoprime to base n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs