A006970 -id:A006970 - cp's OEIS frontend

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

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

A303448 Numbers m such that both m and (m-1)/2 are Fermat pseudoprimes base 2 (A001567).

Original entry on oeis.org

19781763, 46912496118443, 192153584101141163

Offset: 1

Max Alekseyev, Apr 24 2018

No other terms below 2^65.
Terms a(2) and a(3) are of the form (2^(2k+1)+1)/3 = A007583(k).
Terms A007583(k) belong to this sequence for k in A303009. Correspondingly, a(4) <= A007583(A303009(3)) = (2^83+1)/3 = 3223802185639011132549803.
If a(n) is not divisible by 3, then it also belongs to A175625.

Numbers (a(n)-1)/2 are listed in A303447.
Subsequence of A006970 and A300193.
Cf. A175625, A175942, A298758.

a(n) = 2*A303447(n) + 1.

a(1) from Amiram Eldar, Jan 26 2018

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

Original entry on oeis.org

185, 217, 301, 481, 1111, 1261, 1333, 1729, 2465, 2701, 3421, 3565, 3589, 3913, 5713, 6533, 8365, 10585, 11041, 11137, 12209, 14701, 15841, 17329, 18361, 20017, 21049, 22049, 29341, 31021, 31621, 34441, 36301, 38081, 39305, 39493, 41041, 43621, 44801, 46657

Offset: 1

Daniel Lignon, Sep 09 2015

nonn

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

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

eulerPseudoQ[n_?PrimeQ, b_] = False; eulerPseudoQ[n_, b_] := Block[{p = PowerMod[b, (n - 1)/2, n]}, p == Mod[1, n] || p == Mod[-1, n]]; Select[2 Range[25000] + 1, eulerPseudoQ[#, 6] &] (* Michael De Vlieger, Sep 09 2015, after Jean-François Alcover at A006970 *)

for(n=1, 1e5, if( Mod(6, (2*n+1))^n == 1 ||  Mod(6, (2*n+1))^n == 2*n && bigomega(2*n+1) != 1 , print1(2*n+1", "))); \\ Altug Alkan, Oct 11 2015

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

Original entry on oeis.org

25, 325, 703, 817, 1825, 2101, 2353, 2465, 3277, 4525, 6697, 8321, 10225, 11041, 11521, 12025, 13665, 14089, 19345, 20197, 20417, 20425, 25829, 29857, 29891, 35425, 38081, 39331, 46657, 49241, 49321, 50881, 58825, 64681, 75241, 75361, 76627, 78937, 79381

Offset: 1

Daniel Lignon, Sep 09 2015

nonn

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

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

eulerPseudoQ[n_?PrimeQ, b_] = False; eulerPseudoQ[n_, b_] := Block[{p = PowerMod[b, (n - 1)/2, n]}, p == Mod[1, n] || p == Mod[-1, n]]; Select[2 Range[25000] + 1, eulerPseudoQ[#, 7] &] (* Michael De Vlieger, Sep 09 2015, after Jean-François Alcover at A006970 *)

for(n=1, 1e5, if( Mod(7, (2*n+1))^n == 1 ||  Mod(7, (2*n+1))^n == 2*n && bigomega(2*n+1) != 1 , print1(2*n+1", "))); \\ Altug Alkan, Oct 11 2015

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

Original entry on oeis.org

9, 21, 65, 105, 133, 273, 341, 481, 511, 561, 585, 1001, 1105, 1281, 1417, 1541, 1661, 1729, 1905, 2047, 2465, 2501, 3201, 3277, 3641, 4033, 4097, 4641, 4681, 4921, 5461, 6305, 6533, 6601, 7161, 8321, 8481, 9265, 9709, 10261, 10585, 10745, 11041, 12545

Offset: 1

Daniel Lignon, Sep 09 2015

nonn

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

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

eulerPseudoQ[n_?PrimeQ, b_] = False; eulerPseudoQ[n_, b_] := Block[{p = PowerMod[b, (n - 1)/2, n]}, p == Mod[1, n] || p == Mod[-1, n]]; Select[2 Range[11000] + 1, eulerPseudoQ[#, 8] &] (* Michael De Vlieger, Sep 09 2015, after Jean-François Alcover at A006970 *)

for(n=1, 1e5, if( Mod(8, (2*n+1))^n == 1 ||  Mod(8, (2*n+1))^n == 2*n && bigomega(2*n+1) != 1 , print1(2*n+1", "))); \\ Altug Alkan, Oct 11 2015

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Original entry on oeis.org

683, 1123, 1291, 4931, 16963, 25603, 70667, 110491, 121403, 145771, 166667, 301703, 424843, 529547, 579883, 696323, 715523, 854467, 904103, 1112339, 1175723, 1234187, 1306667, 1444523, 2146043, 2651687, 2796203, 2882183, 3069083, 3216931, 4284283, 4325443

Offset: 1

Francois R. Grieu, Mar 05 2018

nonn

The definition's congruence is verified if n is a safe prime A005385 with m the corresponding Sophie Germain prime A005384; and for a few other n, which form the sequence.
If that congruence is verified and m is prime, then n is prime (follows from a result by Fedor Petrov).
That congruence is equivalent to the combination: 2^m == +-1 (mod n) and 2^m == 2 (mod m).
Composite n are Euler pseudoprimes A006970, and strong pseudoprimes A001262 if m is odd. The smallest is a(6534) = (2^47+1)/3 = 46912496118443 = 283*165768537521 (cf. A303448). See Peter Košinár link.
Even m belong to A006935. The first is a(986) = 252435584573, m = 126217792286 (cf. A303008).

			n = 683 = 2*341+1 is in the sequence because 2^341 == 2048 == 3*n-1 (mod 341*683) and m = 341 = 11*13 is composite.
n = 301703 = 2*150851+1 is in the sequence because 2^150851 == 301704 == n+1 (mod 150851*301703) and m = 150851 = 251*601 is composite.
n = 5 = 2*2+1 is not in the sequence because m = 2 is prime.

Francois R. Grieu, Table of n, a(n) for n = 1..2796 (terms <2^42).
Peter Košinár, Report of a composite n, Math StackExchange, Mar 06 2018.
Fedor Petrov, Proof that the congruence and m prime imply n prime, MathOverflow.

Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.

For[m=1,(n=2m+1)<4444444,++m,If[MemberQ[{n+1,3n-1},PowerMod[2,m,m*n]] &&!PrimeQ[m], Print[n]]] (* Francois R. Grieu, Mar 19 2018 *)

isok(n) = {if ((n % 2) && (m=(n-1)/2) && !isprime(m), v = lift(Mod(2, m*n)^m); if ((v == n+1) || (v == 3*n-1), return (1));); return (0);} \\ Michel Marcus, Mar 06 2018

A303447 Numbers m such that both m and 2m+1 are Fermat pseudoprimes base 2 (A001567).

Original entry on oeis.org

9890881, 23456248059221, 96076792050570581

Offset: 1

Max Alekseyev, Apr 24 2018

No other terms below 2^64.

Terms a(2) and a(3) are of the form (4^k-1)/3=A002450(k). Terms A002450(k) belong to this sequence for k in A303009. Correspondingly, a(4) <= A002450(A303009(3)) = (4^41-1)/3 = 1611901092819505566274901.

Numbers 2*a(n)+1 are listed in A303448.
Subsequence of A006970.
Cf. A298758, A300193.

a(1) from Amiram Eldar, Jan 26 2018

A181781 Numbers n that are Euler pseudoprimes to some base b, 2 <= b <= n-2.

Original entry on oeis.org

21, 25, 33, 45, 49, 57, 65, 69, 77, 85, 91, 93, 105, 117, 121, 125, 129, 133, 141, 145, 153, 161, 165, 169, 175, 177, 185, 189, 201, 205, 209, 213, 217, 221, 225, 231, 237, 245, 247, 249, 253, 259, 261, 265, 273, 285, 289, 297, 301, 305, 309, 321, 325, 329, 333, 341, 343, 345

Offset: 1

Karsten Meyer, Nov 12 2010

nonn

Amiram Eldar, Table of n, a(n) for n = 1..10000
Karsten Meyer, Tabelle Pseudoprimzahlen (15-4999)
Karsten Meyer, Rexx program
Eric W. Weisstein, MathWorld: Euler Pseudoprime

Cf. A006970, A181780.

isEulPSP := proc(n,b) if isprime(n) then false; else m := modp(b &^ ((n-1)/2),n) ; if m= 1 or m = n-1 then true; else false; end if; end if;end proc:
isA181781 := proc(n) for b from 2 to n-2 do if isEulPSP(n,b) then return true; end if; end do: return false;end proc:
for n from 3 to 800 do if isA181781(n) then printf("%d,",n) ; end if; end do: # R. J. Mathar, May 30 2011

fQ[n_?PrimeQ, b_] = False; fQ[n_, b_] := Block[{p = PowerMod[b, (n - 1)/2, n]}, p == Mod[1, n] || p == Mod[-1, n]]; gQ[n_] := AnyTrue[Range[2, n - 2], fQ[n, #] &]; Select[2 Range[172] + 1, gQ] (* Michael De Vlieger, Sep 09 2015, after Jean-François Alcover at A006970, Version 10 *)

Definition corrected by Max Alekseyev, Nov 12 2010

Edited definition to be consistent with OEIS style. - N. J. A. Sloane, Nov 13 2010

A262028 a(n) = (A262026(n) - 1)/2.

Original entry on oeis.org

0, 1, 0, 1, 0, 19, 2, 0, 2, 136, 1, 0, 1, 265, 3, 0, 3, 34, 0, 2983, 206, 1, 4, 0, 4, 1, 10, 82, 2, 0, 11209, 2, 46, 52, 5, 0, 5, 209887, 25, 463, 10, 1, 3289414, 0, 70317346, 1, 52, 28, 2509567, 6, 0, 6, 76, 7, 156595

Offset: 1

Wolfdieter Lang, Oct 04 2015

nonn

This is the column Y_0 of the Table of a proof given as a W. Lang link under A007970.

(x0(n), y0(n) = 2*a(n) + 1) with x0(n) = A262067(n) are the fundamental solutions of the Pell equation x^2 - d*y^2 = +1 with odd y. The d values coincide with d = d(n) = A007970(n). For a proof see the mentioned link.

			For the first triples [d(n), x0(n), 2*a(n) + 1] see A262066.

Cf. A006970, A262026, A262067.

A262067(n)^2 - A007970(n)*(2*a(n) + 1)^2 = +1, n >= 1.

cp's OEIS Frontend

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

A303448 Numbers m such that both m and (m-1)/2 are Fermat pseudoprimes base 2 (A001567).

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

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

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A303447 Numbers m such that both m and 2m+1 are Fermat pseudoprimes base 2 (A001567).

Views

Author

Keywords

Comments

Crossrefs

Extensions

A181781 Numbers n that are Euler pseudoprimes to some base b, 2 <= b <= n-2.

Views

Author

Keywords

Links

Crossrefs