A130421 -id:A130421 - cp's OEIS frontend

A006935 Even pseudoprimes (or primes) to base 2: even n that divide 2^n - 2.

2, 161038, 215326, 2568226, 3020626, 7866046, 9115426, 49699666, 143742226, 161292286, 196116194, 209665666, 213388066, 293974066, 336408382, 377994926, 410857426, 665387746, 667363522, 672655726, 760569694, 1066079026, 1105826338, 1423998226, 1451887438, 1610063326, 2001038066, 2138882626, 2952654706, 3220041826

Offset: 1

N. J. A. Sloane, Richard C. Schroeppel

Of course, 2 is the only true prime here.
Numbers a(n)/2 form the odd terms of A130421. - Max Alekseyev, May 28 2014
a(n) == 2 (mod 4), hence there are no consecutive even numbers in this sequence. The closest two terms below 2*10^15 (as computed by Alekseyev) are a(2) = 161038 and a(3) = 215326 with a(3) - a(2) = 54288. Do smaller gaps exist? - Charles R Greathouse IV, Dec 02 2014
Corollary (Rotkiewicz-Ziemak, 1995): 2(2^p-1)(2^q-1) is a pseudoprime if and only if 2(2^(pq)-1) is a pseudoprime, where p,q are distinct primes. - Thomas Ordowski, Apr 09 2016
Numbers 2k such that 2^(2k-1) == 1 (mod k). - Thomas Ordowski, Nov 22 2016
There exist even pseudoprimes that are not squarefree, with the smallest being 190213279479817426 = 2 * 7 * 79 * 1951 * 3511^2 * 7151 (cf. A295740). - Max Alekseyev, Nov 26 2017
Terms of the form 2^k - 2 corresponds to k in A296104. - Max Alekseyev, Dec 04 2017
From Bernard Schott, Oct 11 2021: (Start)
Two significant dates in the history of these terms:
1949: Derrick Henry Lehmer finds the smallest even pseudoprime to base 2, a(2) = 161038 (see Lehmer link).
1951: Dutch mathematician N. G. W. H. Beeger proves that the number of even pseudoprimes is infinite (see Beeger link). (End)

A. H. Beiler, Recreations in the Theory of Numbers, Dover, NY, 1964, p. 23.
J. Brillhart, D. H. Lehmer, J. L. Selfridge, B. Tuckerman, and S. S. Wagstaff, Jr., Factorizations of b^n+/-1 b=2, 3, 5, 6, 7, 10, 11, 12 up to high powers, Contemporary Math. v.22.
R. K. Guy, Unsolved Problems in Number Theory, A12.
Paulo Ribenboim, The Little Book of Bigger Primes, Springer-Verlag NY 2004. See p. 91.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Max Alekseyev, Table of n, a(n) for n = 1..1319 (contains all terms below 2*10^15; first 156 terms from R. G. E. Pinch)
N. G. W. H. Beeger, On even numbers m dividing 2^m-2, Amer. Math. Monthly, Vol. 58, No. 8 (1951), pp. 553-555.
D. H. Lehmer, On the Converse of Fermat's Theorem II, Amer. Math. Monthly, Vol. 56, No. 5 (1949), pp. 300-309.
A. Rotkiewicz and K. Ziemak, On Even Pseudoprimes, The Fibonacci Quarterly, Vol. 33, No. 2 (1995), pp. 123-125.
Eric Weisstein's World of Mathematics, Fermat Pseudoprime.
Index entries for sequences related to pseudoprimes

The even terms of A015919.

Cf. A295740.

Select[2*Range[5000000],PowerMod[2,#,#]==2&] (* Harvey P. Dale, Dec 02 2012 *)

is(n)=Mod(2,n)^n==2 && n%2==0 \\ Charles R Greathouse IV, Dec 02 2014

More terms from Robert G. Wilson v
Corrected by T. D. Noe, May 27 2003
b-file corrected by Max Alekseyev, Oct 09 2016

A116622 Positive integers n such that 13^n == 2 (mod n).

Original entry on oeis.org

1, 11, 140711, 863101, 1856455, 115602923, 566411084209, 706836043419179

Offset: 1

Zak Seidov, Feb 19 2006

No other terms below 10^16. - Max Alekseyev, Nov 02 2018

Cf. A116609.
Solutions to b^n == 2 (mod n): A015919 (b=2), A276671 (b=3), A130421 (b=4), A124246 (b=5), A277401 (b=7), this sequence (b=13), A333269 (b=17).
Solutions to 13^n == k (mod n): A015963 (k=-1), A116621 (k=1), this sequence (k=2), A116629 (k=3), A116630 (k=4), A116611 (k=5), A116631 (k=6), A116632 (k=7), A295532 (k=8), A116636 (k=9), A116620 (k=10), A116638 (k=11), A116639 (k=15).

Select[Range[1, 500000], Mod[13^#, #] == 2 &] (* G. C. Greubel, Nov 19 2017 *)
Join[{1}, Select[Range[5000000], PowerMod[13, #, #] == 2 &]] (* Robert Price, Apr 10 2020 *)

isok(n) = Mod(13, n)^n == 2; \\ Michel Marcus, Nov 19 2017

One more term from Ryan Propper, Jun 11 2006

Term a(1)=1 is prepended and a(7)-a(8) are added by Max Alekseyev, Jun 29 2011

A277401 Positive integers n such that 7^n == 2 (mod n).

Original entry on oeis.org

1, 5, 143, 1133, 2171, 8567, 16805, 208091, 1887043, 517295383, 878436591673

Offset: 1

Seiichi Manyama, Oct 13 2016

All terms are odd.

No other terms below 10^15. Some larger terms: 181204957971619289, 21305718571846184078167, 157*(7^157-2)/1355 (132 digits). - Max Alekseyev, Oct 18 2016

			7 == 2 mod 1, so 1 is a term;
16807 == 2 mod 5, so 5 is a term.

Cf. A066438.
Cf. Solutions to 7^n == k (mod n): A277371 (k=-3), A277370 (k=-2), A015954 (k=-1), A067947 (k=1), this sequence (k=2), A277554 (k=3).
Cf. Solutions to b^n == 2 (mod n): A015919 (b=2), A276671 (b=3), A130421 (b=4), A124246 (b=5), this sequence (b=7), A116622 (b=13).

Join[{1},Select[Range[5173*10^5],PowerMod[7,#,#]==2&]] (* The program will generate the first 10 terms of the sequence; it would take a very long time to generate the 11th term. *) (* Harvey P. Dale, Apr 15 2020 *)

isok(n) = Mod(7, n)^n == 2; \\ Michel Marcus, Oct 13 2016

A066438(a(n)) = 2 for n > 1.

a(10) from Michel Marcus, Oct 13 2016

a(11) from Max Alekseyev, Oct 18 2016

A347906 Numbers k such that 2^(2*k-1) == 1 (mod k).

Original entry on oeis.org

1, 80519, 107663, 1284113, 1510313, 3933023, 4557713, 24849833, 71871113, 80646143, 98058097, 104832833, 106694033, 146987033, 168204191, 188997463, 205428713, 332693873, 333681761, 336327863, 380284847, 533039513, 552913169, 711999113, 725943719, 805031663, 1000519033, 1069441313, 1476327353, 1610020913

Offset: 1

Jianing Song, Sep 18 2021

nonn

Odd numbers k such that ord(2,k) divides 2*k-1, where ord(2,k) is the multiplicative order of 2 modulo k.
Numbers k such that 2*k is in A006935. For k > 1, k is a term if and only if 2*k is an even pseudoprime to base 2.
Odd terms in A130421. Complement of A347908 in A130421.
Terms > 1 must be composite, since for odd primes p we have 2^(2*p-1) == 2 (mod p). If k > 1 is a term, then 2*k-1 must also be composite, since ord(2,k) | (2*k-1) and ord(2,k) <= eulerphi(k) <= k-1 < 2*k-1.
If k > 1 is a term, then (2^(2*k-1) - 1)/k is composite. Proof: since 2*k-1 is composite, write 2*k-1 = u*v, u >= v > 1, then (2^(2*k-1) - 1)/k = (2^u - 1)*(2^(u*(v-1)) + ... + 2^u + 1)/k. Since k | 2^(2*k-1) - 1, there exist positive integers a,b such that a*b = k and that a | 2^u - 1 and b | 2^(u*(v-1)) + ... + 2^u + 1. Note that (2^u - 1)/a, (2^(u*(v-1)) + ... + 2^u + 1)/b >= (2^u - 1)/k >= (2^sqrt(2*k-1) - 1)/k > 1, so (2^(2*k-1) - 1)/k is the product of two integers > 1, so it is composite.
2^t - 1 is a term if and only if 2^(t+1) == 3 (mod t) (t = 1, 111481, 465793, ... in A296370).

			80519 is a term since 80519 divides 2^161037 - 1 (the multiplicative order of 2 modulo 80519 is 261, which is a divisor of 161037). Note that 2 * 80519 = 161038 = A006935(2) is the smallest even pseudoprime to base 2.

Jianing Song, Table of n, a(n) for n = 1..1319 (contains all terms below 10^15; based on Max Alekseyev's b-file for A006935)

Cf. A006935, A130421, A347908, A296370.

Cf. A347907 (a similar sequence).

isA347906(k) = if(k%2 && !isprime(k), Mod(2, k)^(2*k-1)==1, 0)

a(n) = A006935(n)/2.

A130422 Numbers k such that 4^k == 3 (mod k).

Original entry on oeis.org

1, 137243, 2517961, 117741349, 369940993, 19049924867, 30861256333, 1087115897989, 38969560049629

Offset: 1

Jon E. Schoenfield, May 26 2007

No other terms below 10^15.

222775558403218644781528238995676668723498240827403019 belongs to this sequence. - Max Alekseyev, Jul 03 2014

M. Miller, Digraph covering and its application to two optimization problems for digraphs, Australasian Journal of Combinatorics, 3 (1991), pp. 151-164.

Cf. A130421.

for (n=1,10^33, if ( Mod(4,n)^n==3, print1(n,", "))); /* Joerg Arndt, Jun 09 2012 */

a(6) from Jon E. Schoenfield, Sep 30 2013
a(7) from Jared Polzer, Oct 03 2013
a(8)-a(9) from Max Alekseyev, Jul 03 2014

A327840 Numbers m that divide 4^m + 3.

Original entry on oeis.org

1, 7, 16387, 4509253, 24265177, 42673920001, 103949349763, 12939780075073

Offset: 1

Juri-Stepan Gerasimov, Sep 27 2019

Number of solutions < 10^9 to k^n == k-1 (mod n): 1 (if k = 1), 188 (if k = 2, see A006521), 5 (if k = 3, see A015973), 5 (if k = 4, see this sequence), 5 (if k = 5), 10 (if k = 6), 10 (if k = 7), 7 (if k = 8), 5 (if k = 9), 8 (if k = 10), 11 (if k = 11), 8 (if k = 12), 9 (if k = 13), 4 (if k = 14), 3 (if k = 15), 6 (if k = 16), 7 (if k = 17), 7 (if k = 18), ...

a(9) > 10^15. - Max Alekseyev, Nov 10 2022

Solutions to k^n == 1-k (mod n): A006521 (k = 2), A015973 (k = 3), this sequence (k = 4), A123047 (k = 5), A327943 (k = 6).
Solutions to 4^n == k (mod n): A000079 (k = 0), A015950 (k = -1), A014945 (k = 1), A130421 (k = 2), this sequence (k = -3), A130422 (k = 3).
Cf. A015940, A253208.

[1] cat [n: n in [1..10^8] | Modexp(4,n,n) + 3 eq n];

Select[Range[10^7], IntegerQ[(PowerMod[4, #, # ]+3)/# ]&] (* Metin Sariyar, Sep 28 2019 *)

is(n)=Mod(4,n)^n==-3 \\ Charles R Greathouse IV, Sep 29 2019

a(6)-a(7) from Giovanni Resta, Sep 29 2019

a(8) from Max Alekseyev, Nov 10 2022

A347908 Even numbers k such that 2^(2*k) == 2 (mod k).

Original entry on oeis.org

2, 14, 1022, 20066, 485918, 2531678, 3677198, 8277458, 8893262, 21122318, 26358638, 39852014, 42448478, 76712318, 131492498, 144322478, 164360606, 175126478, 176647378, 196705598, 249126626, 306789074, 317051378, 438023138, 497041538, 696970718, 996520658

Offset: 1

Jianing Song, Sep 18 2021

nonn

Numbers of the form 2*t where 2^(4*t-1) == 1 (mod t).
Even terms in A130421. Complement of A347906 in A130421.
If k > 14 is a term, then k/2 must be composite, since for odd primes p we have 2^(4*p) == 16 (mod 2*p). If k = 2*t > 2 is a term, then 2*k-1 = 4*t-1 must also be composite, since ord(2,t) | (4*k-1) and ord(2,t) <= eulerphi(t) <= t-1 < 4*t-1.
If k = 2*t > 2 is a term, then (2^(2*k) - 2)/k = (2^(4*k-1) - 1)/t is composite. See A347907 for a proof.
2*(2^t - 1) is a term if and only if 2^(t+2) == 5 (mod t) (t = 1, 3, 9, 871, 2043, 2119, 8769, ...).

			14 is a term since 14 divides 2^28 - 2.

Jianing Song, Table of n, a(n) for n = 1..1298 (contains all terms below 10^15; based on Max Alekseyev's b-file for A130421)

Cf. A130421, A347906, A347907.

isA347908(k) = if(k%4==2, k=k>>1; if(isprime(k) && k!=7, 0, Mod(2, k)^(4*k-1)==1), 0)

a(n) = A347907(n)*2.

A333269 Positive integers n such that 17^n == 2 (mod n).

Original entry on oeis.org

1, 3, 5, 3585, 4911, 5709, 1688565, 7361691, 16747709, 3226850283899, 8814126944005, 33226030397603

Offset: 1

Seiichi Manyama, Mar 14 2020

No other terms below 10^16. Some larger term: 95549099691107109423357503242294996525424418266995858732192019626694044445113. - Max Alekseyev, Jan 09 2025

Cf. Solutions to b^n == 2 (mod n): A015919 (b=2), A276671 (b=3), A130421 (b=4), A124246 (b=5), A277401 (b=7), A116622 (b=13), this sequence (b=17).

for(k=1, 1e6, if(Mod(17, k)^k==2, print1(k", ")))

A333269_list = [n for n in range(1,10**6) if n == 1 or pow(17,n,n) == 2] # Chai Wah Wu, Mar 14 2020

a(10)-a(12) from Max Alekseyev, Jan 09 2025

A347907 Numbers k such that 2^(4*k-1) == 1 (mod k).

Original entry on oeis.org

1, 7, 511, 10033, 242959, 1265839, 1838599, 4138729, 4446631, 10561159, 13179319, 19926007, 21224239, 38356159, 65746249, 72161239, 82180303, 87563239, 88323689, 98352799, 124563313, 153394537, 158525689, 219011569, 248520769, 348485359, 498260329, 636381799, 638395369, 685333399, 689463889

Offset: 1

Jianing Song, Sep 18 2021

nonn

Odd numbers k such that ord(2,k) divides 4*k-1, where ord(2,k) is the multiplicative order of 2 modulo k.
Numbers k such that 2*k is in A130421.
Terms > 7 must be composite, since for odd primes p we have 2^(4*p-1) == 8 (mod p). If k > 1 is a term, then 4*k-1 must also be composite, since ord(2,k) | (4*k-1) and ord(2,k) <= eulerphi(k) <= k-1 < 4*k-1.
If k > 1 is a term, then (2^(4*k-1) - 1)/k is composite. Proof: since 4*k-1 is composite, write 4*k-1 = u*v, u >= v > 1. Proof: since 4*k-1 is composite, write 4*k-1 = u*v, u >= v > 1, then (2^(4*k-1) - 1)/k = (2^u - 1)*(2^(u*(v-1)) + ... + 2^u + 1)/k. Since k | 2^(4*k-1) - 1, there exist positive integers a,b such that a*b = k and that a | 2^u - 1 and b | 2^(u*(v-1)) + ... + 2^u + 1. Note that (2^u - 1)/a, (2^(u*(v-1)) + ... + 2^u + 1)/b >= (2^u - 1)/k >= (2^sqrt(4*k-1) - 1)/k > 1, so (2^(4*k-1) - 1)/k is the product of two integers > 1, so it is composite.
2^t - 1 is a term if and only if 2^(t+2) == 5 (mod t) (t = 1, 3, 9, 871, 2043, 2119, 8769, ...).

			7 is a term since 7 divides 2^27 - 1.

Jianing Song, Table of n, a(n) for n = 1..1298 (contains all terms below 5*10^14; based on Max Alekseyev's b-file for A130421)

Cf. A130421, A347908.

Cf. A347906 (a similar sequence).

Join[{1},Parallelize[Select[Range[69*10^7],PowerMod[2,4#-1,#]==1&]]] (* Harvey P. Dale, Apr 16 2023 *)

isA347907(k) = if(k%2 && (!isprime(k) || k==7), Mod(2, k)^(4*k-1)==1, 0)

a(n) = A347908(n)/2.

A333134 Positive integers k such that 11^k == 2 (mod k).

Original entry on oeis.org

1, 3, 413, 1329, 6587, 11629, 75761, 925071199, 9031140861789, 114876097917387, 1314252479257933

Offset: 1

Seiichi Manyama, Mar 20 2020

No other terms below 10^16. Some larger terms: 1584680529929001639, 15598123298097725094806152851164088027801112472240274433891889912569153113. - Max Alekseyev, Jan 07 2025

Solutions to b^n == 2 (mod n): A015919 (b=2), A276671 (b=3), A130421 (b=4), A124246 (b=5), A277401 (b=7), this sequence (b=11), A116622 (b=13), A333269 (b=17).

Cf. A015960.

for(k=1, 1e6, if(Mod(11, k)^k==2, print1(k", ")))

a(9)-a(11) from Max Alekseyev, Jan 07 2025

cp's OEIS Frontend

A006935 Even pseudoprimes (or primes) to base 2: even n that divide 2^n - 2.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A116622 Positive integers n such that 13^n == 2 (mod n).

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

PARI

Extensions

A277401 Positive integers n such that 7^n == 2 (mod n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A347906 Numbers k such that 2^(2*k-1) == 1 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A130422 Numbers k such that 4^k == 3 (mod k).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Extensions

A327840 Numbers m that divide 4^m + 3.

Views

Author

Keywords

Comments

Crossrefs

Programs

Magma

Mathematica

PARI

Extensions

A347908 Even numbers k such that 2^(2*k) == 2 (mod k).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula

A333269 Positive integers n such that 17^n == 2 (mod n).

Views