A244628 -id:A244628 - cp's OEIS frontend

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

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

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, ", ")))

A294912 Numbers n such that 2^(n-1), (2n-1)(2^((n-1)/2)), (4ceiling((3/4)n)-2), and (2^((n+1)/2) + floor((1/4)n)2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

Original entry on oeis.org

3, 11, 19, 43, 59, 67, 83, 107, 131, 139, 163, 179, 211, 227, 251, 283, 307, 331, 347, 379, 419, 443, 467, 491, 499, 523, 547, 563, 571, 587, 619, 643, 659, 683, 691, 739, 787, 811, 827, 859, 883, 907, 947, 971, 1019, 1051, 1091, 1123, 1163, 1171, 1187, 1259

Offset: 1

Jonas Kaiser, Nov 10 2017

nonn

It appears that A007520 is a subsequence.
The first composite term is a(9969) = 476971 = 11*131*331. - Alois P. Heinz, Nov 10 2017
From Hilko Koning, Dec 03 2019: (Start)
The next composite terms < 1999979 are
a(17428) = 877099  = 307*2857
a(25090) = 1302451 = 571*2281
a(25518) = 1325843 = 499*2657
a(26785) = 1397419 = 67*20857
a(27549) = 1441091 = 347*4153
a(28715) = 1507963 = 971*1553
a(29117) = 1530787 = 619*2473
a(35635) = 1907851 = 11*251*691
(End)
From Hilko Koning, Dec 05 2019: (Start)
The next composite terms < 24999971 are
a(37344) = 2004403 = 307*6529
a(55773) = 3090091 = 1163*2657
a(56189) = 3116107 = 883*3529
a(91332) = 5256091 = 811*6481
a(102027) = 5919187 = 1777*3331
a(133230) = 7883731 = 811*9721
a(156407) = 9371251 = 1531*6121
a(182911) = 11081459 = 227*48817
a(189922) = 11541307 = 1699*6793
a(201043) = 12263131 = 811*15121
a(213203) = 13057787 = 467*27961
a(217484) = 13338371 = 3163*4217
a(257526) = 15976747 = 3739*4273
a(274961) = 17134043 = 1097*15619
a(299096) = 18740971 = 1531*12241
a(308928) = 19404139 = 2011*9649
a(321676) = 20261251 = 2251*9001
a(341902) = 21623659 = 1163*18593
a(348622) = 22075579 = 163*135433
a(380162) = 24214051 = 281*86171
The composite terms < 25*10^6 match the terms of A244628.
(End)
It appears that composites of the form 2k+1 such that 3*(2k+1) divides 2^k+1 are the composite terms of this sequence. - Hilko Koning, Dec 09 2019

Jonas Kaiser, On the relationship between the Collatz conjecture and Mersenne prime numbers, arXiv:1608.00862 [math.GM], 2016.

Cf. A244626, A294717, A293394, A070179, A007520.

okQ[n_] := AllTrue[{2^(n-1), (2*n-1)*(2^((n-1)/2)), (4*Ceiling@((3/4)*n) - 2), (2^((n+1)/2) + Floor@(n/4)*2^(((n+1)/2)+1))}, Mod[#, n] == 1&];
Select[Range[1300], okQ] (* Jean-François Alcover, Feb 18 2019 *)

isok(n) = (n%2) && lift((Mod(2, n)^(n-1))==1)&&lift((Mod((2*n-1), n)*Mod(2, n)^((n-1)/2)) == 1)&&lift((Mod(((4*ceil((3/4)*n)-2)), n) )== 1)&&lift((Mod(2, n)^((n+1)/2) +Mod(floor((1/4)*n),n)*Mod(2, n)^(((n+1)/2)+1 ))== 1)

More terms from Alois P. Heinz, Nov 10 2017

A356638 Odd composite numbers k such that 2^((k-1)/2) == -1 (mod k).

Original entry on oeis.org

3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 476971, 489997, 800605, 838861, 873181, 877099, 1004653, 1251949, 1302451, 1325843, 1373653, 1397419, 1441091, 1507963, 1509709, 1530787, 1678541, 1811573, 1907851, 1987021, 2004403, 2269093

Offset: 1

Jeppe Stig Nielsen, Aug 19 2022

nonn

Counterexamples (pseudoprimes) to the hypothesis that this congruence is sufficient to prove that an odd number is prime.

Compare with Proth's theorem.

Cf. A244626, A244628.

Select[Range[1, 2.5*10^6, 2], CompositeQ[#] && PowerMod[2, (# - 1)/2, #] == # - 1 &] (* Amiram Eldar, Aug 19 2022 *)

forstep(k=3,10^8,2,isprime(k)&&next();Mod(2,k)^((k-1)/2)==-1&&print1(k,", "))

cp's OEIS Frontend

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

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

A294912 Numbers n such that 2^(n-1), (2*n-1)*(2^((n-1)/2)), (4*ceiling((3/4)*n)-2), and (2^((n+1)/2) + floor((1/4)*n)*2^(((n+1)/2)+1)) are all congruent to 1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A356638 Odd composite numbers k such that 2^((k-1)/2) == -1 (mod k).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

A294912 Numbers n such that 2^(n-1), (2n-1)(2^((n-1)/2)), (4ceiling((3/4)n)-2), and (2^((n+1)/2) + floor((1/4)n)2^(((n+1)/2)+1)) are all congruent to 1 (mod n).