A047713 -id:A047713 - cp's OEIS frontend

A375915 Composite numbers k == 1, 9 (mod 10) such that 5^((k-1)/2) == 1 (mod k).

781, 1541, 1729, 5461, 5611, 6601, 7449, 11041, 12801, 13021, 14981, 15751, 15841, 21361, 24211, 25351, 29539, 38081, 40501, 41041, 44801, 47641, 53971, 67921, 75361, 79381, 90241, 100651, 102311, 104721, 106201, 106561, 112141, 113201, 115921, 133141, 135201, 141361

Offset: 1

Jianing Song, Sep 02 2024

nonn

Odd composite numbers k such that 5^((k-1)/2) == (5/k) = 1 (mod k), where (5/k) is the Jacobi symbol (or Kronecker symbol).

			29539 is a term because 29539 = 109*271 is composite, 29539 == 9 (mod 10), and 5^((29539-1)/2) == 1 (mod 29539).

Jianing Song, Table of n, a(n) for n = 1..1000

                                   |        b=2        |   b=3   |   b=5    |
-----------------------------------+-------------------+---------+----------+
  (b/k)=1, b^((k-1)/2)==1 (mod k)  |      A006971      | A375917 | this seq |
-----------------------------------+-------------------+---------+----------+
 (b/k)=-1, b^((k-1)/2)==-1 (mod k) | A244628 U A244626 | A375918 | A375916  |
-----------------------------------+-------------------+---------+----------+
 b^((k-1)/2)==-(b/k) (mod k), also |      A306310      | A375490 | A375816  |
 (b/k)=-1, b^((k-1)/2)==1 (mod k)  |                   |         |          |
-----------------------------------+-------------------+---------+----------+
     Euler-Jacobi pseudoprimes     |      A047713      | A048950 | A375914  |
       (union of first two)        |                   |         |          |
-----------------------------------+-------------------+---------+----------+
        Euler pseudoprimes         |      A006970      | A262051 | A262052  |
       (union of all three)        |                   |         |          |

isA375915(k) = (k>1) && !isprime(k) && (k%10==1 || k%10==9) && Mod(5,k)^((k-1)/2) == 1

A375916 Composite numbers k == 3, 7 (mod 10) such that 5^((k-1)/2) == -1 (mod k).

Original entry on oeis.org

7813, 121463, 195313, 216457, 315283, 319507, 353827, 555397, 559903, 753667, 939727, 1164083, 1653667, 1663213, 1703677, 1809697, 1958503, 2255843, 2339377, 2423323, 2942333, 2987167, 3313643, 4265257, 4635053, 5376463, 5979247, 6611977, 7784297, 7859707

Offset: 1

Jianing Song, Sep 02 2024

nonn

Odd composite numbers k such that 5^((k-1)/2) == (5/k) = -1 (mod k), where (5/k) is the Jacobi symbol (or Kronecker symbol).

			216457 is a term because 216457 = 233*929 is a composite, 216457 == 7 (mod 10), and 5^((216457-1)/2) == -1 (mod 216457).

Jianing Song, Table of n, a(n) for n = 1..1000

                                   |        b=2        |   b=3   |   b=5    |
-----------------------------------+-------------------+---------+----------+
  (b/k)=1, b^((k-1)/2)==1 (mod k)  |      A006971      | A375917 | A375915  |
-----------------------------------+-------------------+---------+----------+
 (b/k)=-1, b^((k-1)/2)==-1 (mod k) | A244628 U A244626 | A375918 | this seq |
-----------------------------------+-------------------+---------+----------+
 b^((k-1)/2)==-(b/k) (mod k), also |      A306310      | A375490 | A375816  |
 (b/k)=-1, b^((k-1)/2)==1 (mod k)  |                   |         |          |
-----------------------------------+-------------------+---------+----------+
     Euler-Jacobi pseudoprimes     |      A047713      | A048950 | A375914  |
       (union of first two)        |                   |         |          |
-----------------------------------+-------------------+---------+----------+
        Euler pseudoprimes         |      A006970      | A262051 | A262052  |
       (union of all three)        |                   |         |          |

isA375916(k) = !isprime(k) && (k%10==3 || k%10==7) && Mod(5,k)^((k-1)/2) == -1

A375917 Composite numbers k == 1, 11 (mod 12) such that 3^((k-1)/2) == 1 (mod k).

Original entry on oeis.org

121, 1729, 2821, 7381, 8401, 10585, 15457, 15841, 18721, 19345, 23521, 24661, 28009, 29341, 31621, 41041, 46657, 47197, 49141, 50881, 52633, 55969, 63973, 74593, 75361, 82513, 87913, 88573, 93961, 111361, 112141, 115921, 125665, 126217, 138481, 148417, 172081

Offset: 1

Jianing Song, Sep 02 2024

nonn

Odd composite numbers k such that 3^((k-1)/2) == (3/k) = 1 (mod k), where (3/k) is the Jacobi symbol (or Kronecker symbol).

It seems that most terms are congruent to 1 modulo 12. The first terms congruent to 11 modulo 12 are 1683683, 1898999, 2586083, 2795519, 4042403, 4099439, 5087171, 8243111, ...

			1683683 is a term because 1683683 = 59*28537 is composite, 1683683 == 11 (mod 12), and 3^((1683683-1)/2) == 1 (mod 1683683).

Jianing Song, Table of n, a(n) for n = 1..1000

                                   |        b=2        |   b=3    |   b=5   |
-----------------------------------+-------------------+----------+---------+
  (b/k)=1, b^((k-1)/2)==1 (mod k)  |      A006971      | this seq | A375915 |
-----------------------------------+-------------------+----------+---------+
 (b/k)=-1, b^((k-1)/2)==-1 (mod k) | A244628 U A244626 | A375918  | A375916 |
-----------------------------------+-------------------+----------+---------+
 b^((k-1)/2)==-(b/k) (mod k), also |      A306310      | A375490  | A375816 |
 (b/k)=-1, b^((k-1)/2)==1 (mod k)  |                   |          |         |
-----------------------------------+-------------------+----------+---------+
     Euler-Jacobi pseudoprimes     |      A047713      | A048950  | A375914 |
       (union of first two)        |                   |          |         |
-----------------------------------+-------------------+----------+---------+
        Euler pseudoprimes         |      A006970      | A262051  | A262052 |
       (union of all three)        |                   |          |         |

isA375917(k) = (k>1) && !isprime(k) && (k%12==1 || k%12==11) && Mod(3,k)^((k-1)/2) == 1

A375918 Composite numbers k == 5, 7 (mod 12) such that 3^((k-1)/2) == -1 (mod k).

Original entry on oeis.org

703, 1891, 3281, 8911, 12403, 16531, 44287, 63139, 79003, 97567, 105163, 152551, 182527, 188191, 211411, 218791, 288163, 313447, 320167, 364231, 385003, 432821, 453259, 497503, 563347, 638731, 655051, 658711, 801139, 859951, 867043, 973241, 994507, 1024651, 1097227

Offset: 1

Jianing Song, Sep 02 2024

nonn

Odd composite numbers k such that 3^((k-1)/2) == (3/k) = -1 (mod k), where (3/k) is the Jacobi symbol (or Kronecker symbol).

			3281 is a term because 3281 = 17*193 is composite, 3281 == 5 (mod 12), and 3^((3281-1)/2) == -1 (mod 3281).

Jianing Song, Table of n, a(n) for n = 1..1000

                                   |        b=2        |   b=3    |   b=5   |
-----------------------------------+-------------------+----------+---------+
  (b/k)=1, b^((k-1)/2)==1 (mod k)  |      A006971      | A375917  | A375915 |
-----------------------------------+-------------------+----------+---------+
 (b/k)=-1, b^((k-1)/2)==-1 (mod k) | A244628 U A244626 | this seq | A375916 |
-----------------------------------+-------------------+----------+---------+
 b^((k-1)/2)==-(b/k) (mod k), also |      A306310      | A375490  | A375816 |
 (b/k)=-1, b^((k-1)/2)==1 (mod k)  |                   |          |         |
-----------------------------------+-------------------+----------+---------+
     Euler-Jacobi pseudoprimes     |      A047713      | A048950  | A375914 |
       (union of first two)        |                   |          |         |
-----------------------------------+-------------------+----------+---------+
        Euler pseudoprimes         |      A006970      | A262051  | A262052 |
       (union of all three)        |                   |          |         |

isA375918(k) = !isprime(k) && (k%12==5 || k%12==7) && Mod(3,k)^((k-1)/2) == -1

A270698 Composite numbers k == 1 (mod 4) such that (1 + i)^k == 1 + i (mod k), where i = sqrt(-1).

Original entry on oeis.org

561, 1105, 1729, 1905, 2465, 3277, 4033, 4681, 6601, 8321, 8481, 10585, 12801, 15841, 16705, 18705, 25761, 29341, 30121, 33153, 34945, 41041, 46657, 49141, 52633, 62745, 65281, 74665, 75361, 80581, 85489, 87249, 88357, 104653, 113201, 115921, 126217, 129921

Offset: 1

José María Grau Ribas, Mar 21 2016

nonn

From Jianing Song, Sep 05 2018: (Start)
Numbers in A047713 that are congruent to 1 mod 4. Most terms are congruent to 1 mod 8. For terms congruent to 5 mod 8, see A244626.
Also composite k == 1 (mod 4) such that (-4)^((k-1)/4) == 1 (mod k). Note that this is satisfied by all primes == 1 (mod 4), see A318898. (End)

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..889 from Jianing Song using data from A047713)

Subsequence of A001567 and A047713.
A244626 is a proper subsequence.
Cf. A006971, A270697, A318898.

Select[1 + 4*Range[100000], PrimeQ[#] == False && PowerMod[1 + I, #, #] == 1 + I &]

forstep(n=5, 10^5, 4, if(Mod(2, n)^((n-1)/2)==kronecker(2, n) && !isprime(n), print1(n, ", "))) \\ Jianing Song, Sep 06 2018

A270697 Composite numbers k == 3 (mod 4) such that (1 + i)^k == 1 - i (mod k), where i = sqrt(-1).

Original entry on oeis.org

2047, 42799, 90751, 256999, 271951, 476971, 514447, 741751, 877099, 916327, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 2205967, 2304167, 2748023, 2811271, 2953711, 2976487, 3090091, 3116107, 4469471, 4863127, 5016191

Offset: 1

José María Grau Ribas, Mar 21 2016

nonn

Composite k == 3 (mod 4) such that 2*(-4)^((k-3)/4) == -1 (mod k). - Robert Israel, Mar 21 2016
2*(-4)^((p-3)/4) == -1 (mod p) is satisfied by all primes p == 3 (mod 4), see A318908. - Jianing Song, Sep 05 2018
Numbers in A047713 that are congruent to 3 mod 4. Most terms are congruent to 7 mod 8. For terms congruent to 3 mod 8, see A244628. - Jianing Song, Sep 05 2018
Question: Is this a subsequence of A001262? I have verified that it contains all terms up to 2^64. - Joseph M. Shunia, Jul 02 2019

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..111 from Jianing Song using data from A047713)

Subsequence of A001567 and A047713.
A244628 is a proper subsequence.
Cf. A001262, A006971, A270698, A318908.

select(t -> not isprime(t) and 1 + 2*(-4) &^ ((t-3)/4) mod t = 0, [seq(i, i=7..10^7, 4)]); # Robert Israel, Mar 21 2016

Select[3 + 4*Range[10000000], PrimeQ[#] == False && PowerMod[1 + I, #, #] == Mod[1 - I, #] &]

forstep(n=3, 10^7, 4, if(Mod(2, n)^((n-1)/2)==kronecker(2, n) && !isprime(n), print1(n, ", ")))

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).

Original entry on oeis.org

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

A329726 Number of witnesses for Solovay-Strassen primality test of 2*n+1.

Original entry on oeis.org

2, 4, 6, 2, 10, 12, 2, 16, 18, 2, 22, 4, 2, 28, 30, 2, 2, 36, 2, 40, 42, 4, 46, 6, 2, 52, 2, 2, 58, 60, 2, 8, 66, 2, 70, 72, 2, 2, 78, 2, 82, 8, 2, 88, 18, 2, 2, 96, 2, 100, 102, 8, 106, 108, 2, 112, 2, 4, 2, 10, 2, 4, 126, 2, 130, 18, 2, 136, 138, 2, 2, 8, 2

Offset: 1

Amiram Eldar, Nov 20 2019

nonn

Number of bases b, 1 <= b <= 2*n, such that GCD(b, 2*n+1) = 1 and b^n == (b / 2*n+1) (mod 2*n+1), where (b / 2*n+1) is a Jacobi symbol.
If 2*n+1 is composite then it is the number of bases b, 1 <= b <= 2*n, in which 2*n+1 is an Euler-Jacobi pseudoprime.
Differs from A071294 from n = 22.

			a(1) = 2 since there are 2 bases b in which 2*1 + 1 = 3 is an Euler-Jacobi pseudoprime: b = 1 since GCD(1, 3) = 1 and 1^1 == (1 / 3) == 1 (mod 3), and b = 2 since GCD(2, 3) = 1 and 2^1 == (2 / 3) == -1 (mod 3).

Paulo Ribenboim, The Little Book of Bigger Primes, 2nd ed., Springer-Verlag, New York, 2004, p. 96.

Amiram Eldar, Table of n, a(n) for n = 1..10000
Louis Monier, Evaluation and comparison of two efficient primality testing algorithms, Theoretical Computer Science, Vol. 11 (1980), pp. 97-108.
Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.
Wikipedia, Euler-Jacobi pseudoprime.
Wikipedia, Solovay-Strassen primality test.

Cf. A006093, A007324, A007814, A047713, A063994, A071294.

v[n_] := Min[IntegerExponent[#, 2]& /@ (FactorInteger[n][[;;, 1]] - 1)];
pQ[n_, p_] := OddQ[IntegerExponent[n, p]] && IntegerExponent[p-1, 2] < IntegerExponent[n-1, 2];
psQ[n_] := AnyTrue[FactorInteger[n][[;;, 1]], pQ[n, #] &];
delta[n_] := If[IntegerExponent[n-1, 2] == v[n], 2, If[psQ[n], 1/2, 1]];
a[n_] := delta[n] * Module[{p = FactorInteger[n][[;;, 1]]}, Product[GCD[(n-1)/2, p[[k]]-1], {k, 1, Length[p]}]];
Table[a[n], {n, 3, 147, 2}]

a(n) = delta(n) * Product_{p|n} gcd((n-1)/2, p-1), where delta(n) = 2 if nu(n-1, 2) = min_{p|n} nu(p-1, 2), 1/2 if there is a prime p|n such that nu(p, n) is odd and nu(p-1, 2) < nu(n-1, 2), and 1 otherwise, where nu(n, p) is the exponent of the highest power of p dividing n.

a(p) = p-1 for prime p.

A326614 Smallest Euler-Jacobi pseudoprime to base n.

Original entry on oeis.org

9, 561, 121, 341, 781, 217, 25, 9, 91, 9, 133, 91, 85, 15, 1687, 15, 9, 25, 9, 21, 221, 21, 169, 25, 217, 9, 121, 9, 15, 49, 15, 25, 545, 33, 9, 35, 9, 39, 133, 39, 21, 451, 21, 9, 481, 9, 65, 49, 25, 49, 25, 51, 9, 55, 9, 55, 25, 57, 15, 481, 15, 9, 529, 9, 33, 65, 33, 25, 35, 69, 9

Offset: 1

Richard N. Smith, Jul 14 2019

nonn

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

Richard N. Smith, Table of n, a(n) for n = 1..5000
Wikipedia, Euler-Jacobi pseudoprime

Cf. A047713, A048950, A090086 (least Fermat pseudoprime to base n), A298756 (least strong pseudoprime to base n).

ejpspQ[n_,b_] := CoprimeQ[n,b] && CompositeQ[n] && Mod[b^((n - 1)/2) - JacobiSymbol[b, n], n] == 0; leastEJpsp[b_] := Module[{k=9}, While[!ejpspQ[k, b], k+=2]; k]; Array[leastEJpsp, 100] (* Amiram Eldar, Jul 15 2019 *)

isok(k, n) = ((k%2==1) && (gcd(k, n)==1) && Mod(n, k)^((k-1)/2)==kronecker(n, k) && !isprime(k));
a(n) = my(k=2); while (! isok(k, n), k++); k; \\ Michel Marcus, Jul 15 2019

A354692 Smallest Euler-Jacobi pseudoprime to all natural bases up to prime(n) - 1 that is not a base prime(n) Euler-Jacobi pseudoprime.

Original entry on oeis.org

9, 561, 10585, 1729, 488881, 399001, 2433601, 1857241, 6189121, 549538081, 50201089, 14469841, 86566959361, 311963097601, 369838909441, 31929487861441, 6389476833601, 8493512837546881, 31585234281457921, 10120721237827201, 289980482095624321, 525025434548260801, 91230634325542321

Offset: 1

Jinyuan Wang, Jun 03 2022

nonn

An Euler-Jacobi pseudoprime to the base b is an odd composite number k such that gcd(b, k) = 1 and the Jacobi symbol (.,.) satisfies b^((k-1)/2) == (b,k) (mod k).
a(n) is coprime to A002110(n-1).
a(24) > 2^64. - Daniel Suteu, Jun 05 2022

Eric Weisstein's World of Mathematics, Euler-Jacobi Pseudoprime.

Cf. A002110, A007324, A047713, A285549, A354694.

a(n) = my(b, p=factorback(primes(n-1))); forcomposite(k=9, oo, if(gcd(k, p)==1, b=2; while(Mod(b, k)^(k\2) == kronecker(b, k), b++); if(b==prime(n), return(k))));

a(13)-a(23) from Daniel Suteu, Jun 05 2022

cp's OEIS Frontend

A375915 Composite numbers k == 1, 9 (mod 10) such that 5^((k-1)/2) == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A375916 Composite numbers k == 3, 7 (mod 10) such that 5^((k-1)/2) == -1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A375917 Composite numbers k == 1, 11 (mod 12) such that 3^((k-1)/2) == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A375918 Composite numbers k == 5, 7 (mod 12) such that 3^((k-1)/2) == -1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A270698 Composite numbers k == 1 (mod 4) such that (1 + i)^k == 1 + i (mod k), where i = sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A270697 Composite numbers k == 3 (mod 4) such that (1 + i)^k == 1 - i (mod k), where i = sqrt(-1).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

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

A329726 Number of witnesses for Solovay-Strassen primality test of 2*n+1.

Views

Author

Keywords

Comments

Examples

References

Links