A070179 -id:A070179 - cp's OEIS frontend

A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

3277, 29341, 49141, 80581, 88357, 104653, 196093, 314821, 458989, 489997, 800605, 838861, 873181, 1004653, 1251949, 1373653, 1509709, 1678541, 1811573, 1987021, 2269093, 2284453, 2387797, 2746477, 2909197, 3400013, 3429037, 3539101, 3605429, 4360621, 4502485, 5590621, 5599765

Offset: 1

Gary Detlefs, Jul 02 2014

nonn

This sequence contains the n mod 8 = 5 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is an odd prime congruent to {3,5} (mod 8) then 2^((p-1)/2) mod p = p-1.
This conjecture has been tested to 10^8.
This criterion produces far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a higher probability of success. The number of pseudoprimes for the two tests up to 10^k are:
   10^5    5   26     19.23%
   10^6   13   78     16.66%
   10^7   40  228     17.54%
There are 40 terms < 10^7. If an additional constraint 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 is added, only 4 terms remain: (29341, 314821, 873181, 9863461).
This sequence appears to be a subset of A175865, A001262, A047713, A020230.
Number of terms below 10^k for k = 5..15: 5, 13, 40, 132, 369, 975, 2534, 6592, 17403, 45801, 122473. The corresponding numbers for 2^(n-1) mod n = 1: 26, 78, 228, 637, 1718, 4505, 11645, 29902, 76587, 197455, 513601. - Jens Kruse Andersen, Jul 13 2014
Also composite numbers 2n+1 with n even such that 2n+1 | 2^n+1. - Hilko Koning, Jan 27 2022
Conjecture 1 is true. With p = 2k+1 then 2^k mod (2k+1) == 2k. So 2k+1 | 2k-2^k. Prime numbers 2k+1 == +-3 (mod 8) are the prime numbers such that 2k+1 | 2^k+1 (Comments A007520). A reflection across the x-axis and +1 translation across the y-axis of the graph (2k-2^k) / (2k+1) gives the graph (2^k+1) / (2k+1). So the k values of both 2k+1 | 2k-2^k and 2k+1 | 2^k+1 are identical. - Hilko Koning, Feb 04 2022

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000

Cf. A001567, A003629, A070179.

for n from 5 to 10^7 by 8 do if 2^((n-1)/2) mod n = n-1 and not isprime(n) then print(n) fi od;

a(18) corrected by Jens Kruse Andersen, Jul 13 2014

A244628 Composite numbers n such that n == 3 (mod 8) and 2^((n-1)/2) == -1 (mod n).

Original entry on oeis.org

476971, 877099, 1302451, 1325843, 1397419, 1441091, 1507963, 1530787, 1907851, 2004403, 3090091, 3116107, 5256091, 5919187, 7883731, 9371251, 11081459, 11541307, 12263131, 13057787, 13338371, 15976747, 17134043, 18740971, 19404139, 20261251, 21623659, 22075579, 24214051

Offset: 1

Gary Detlefs, Jul 02 2014

nonn

This sequence contains the n mod 8 = 3 pseudoprimes to the following modified Fermat primality criterion:
Conjecture 1: if p is a prime congruent to {3,5} mod 8 then 2^((p-1)/2) mod p = p-1.
This conjecture has been tested to 10^8.
This modified primality test has far fewer pseudoprimes than the 2^(n-1) mod n = 1 test and thus has a much higher probability of success. The number of pseudoprimes up to 10^k for the two tests are:
   10^3 0     0
   10^4 0     2
   10^5 0     5
   10^6 2    14
   10^7 16   48
This sequence appears to be a subset of the composites in A175865.
The n mod 8 = 3 pseudoprimes are much rarer than the n mod 8 = 5 pseudoprimes. There are 16 terms < 10^7. If the additional constraints 3^(n-1) mod n = 1 and 5^(n-1) mod n = 1 are added, no terms remain.
Number of terms < 10^k: 0, 0, 0, 0, 0, 2, 16, 50, 132, ..., . - Robert G. Wilson v, Jul 21 2014
Number of terms < 10^k for k=5..15: 0, 2, 16, 50, 132, 341, 876, 2330, 6234, 16625, 44885. - Jens Kruse Andersen, Jul 27 2014
It appears that the terms of the sequence are also the composite numbers of A294912. - Hilko Koning, Dec 05 2019
Also composite numbers 2k+1 with k odd such that 2k+1 | 2^k+1. - Hilko Koning, Jan 27 2022
Conjecture 1 is true. With p = 2k+1 then 2^k mod (2k+1) == 2k. So 2k+1 | 2k-2^k . Prime numbers 2k+1 == +-3 (mod 8) are the prime numbers such that 2k+1 | 2^k+1 (Comments A007520). A reflection across the x-axis and +1 translation across the y-axis of the graph (2k-2^k) / (2k+1) gives the graph (2^k+1) / (2k+1). So the k values of both 2k+1 | 2k-2^k and 2k+1 | 2^k+1 are identical. - Hilko Koning, Feb 04 2022

Jens Kruse Andersen, Table of n, a(n) for n = 1..10000 (first 132 terms from Robert G. Wilson v)

Cf. A003629, A070179, A175865.

for n from 3 to 10^8 by 8 do if Power(2,(n-1)/2) mod n =  n -1 and not isprime(n) then print(n) fi od

fQ[n_] := !PrimeQ@ n && PowerMod[2, (n - 1)/2, n] == n - 1; k = 3; lst = {}; While[k < 10^8, If[fQ@ k, AppendTo[lst, k]]; k += 8]; lst (* Robert G. Wilson v, Jul 21 2014 *)

A059667 Primes p such that x^49 = 2 has no solution mod p, but x^7 = 2 has a solution mod p.

Original entry on oeis.org

4999, 6959, 7351, 11467, 15583, 16073, 20483, 21169, 21757, 30773, 35771, 37339, 38711, 41161, 45179, 46649, 48119, 51157, 51647, 57527, 58997, 64877, 75167, 75853, 80263, 83791, 84869, 85751, 86927, 93983, 95747, 105253, 110251, 115837

Offset: 1

Klaus Brockhaus, Feb 04 2001

nonn

Vincenzo Librandi, Table of n, a(n) for n = 1..76

Cf. A042966, A042967, A070179 - A070188.

Select[Prime[Range[PrimePi[120000]]], ! MemberQ[PowerMod[Range[#], 49, #], Mod[2, #]] && MemberQ[PowerMod[Range[#], 7, #], Mod[2, #]] &] (* Vincenzo Librandi, Sep 21 2013 *)

PARI
```
forprime(p=2,116000,x=0; while(x
				
```

N=10^6;  default(primelimit,N);
ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,N, if (ok(p,2,7,7^2),print1(p,", ")));
\\ Joerg Arndt, Sep 21 2012

A070188 Primes p such that x^12 = 2 has a solution mod p, but x^(12^2) = 2 has no solution mod p.

Original entry on oeis.org

113, 281, 353, 593, 617, 919, 1049, 1097, 1193, 1217, 1423, 1481, 1553, 1601, 1753, 1777, 1889, 1999, 2129, 2143, 2273, 2281, 2287, 2393, 2689, 2791, 2833, 3089, 3137, 3761, 3833, 4001, 4049, 4153, 4177, 4217, 4289, 4457, 4481, 4519, 4657, 4663, 4817

Offset: 1

Klaus Brockhaus, Apr 29 2002

Cf. A049544, A059667, A070179 - A070187.

[p: p in PrimesUpTo(5000) | not exists{x: x in ResidueClassRing(p) | x^144 eq 2} and exists{x: x in ResidueClassRing(p) | x^12 eq 2}]; // Vincenzo Librandi, Sep 21 2012

PARI
```
forprime(p=2,5000,x=0; while(x
				
```

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^5, if (ok(p,2,12,12^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

A014754 Primes p == 1 mod 8 such that 2 and -2 are both 4th powers (one implies other) mod p.

Original entry on oeis.org

73, 89, 113, 233, 257, 281, 337, 353, 577, 593, 601, 617, 881, 937, 1033, 1049, 1097, 1153, 1193, 1201, 1217, 1249, 1289, 1433, 1481, 1553, 1601, 1609, 1721, 1753, 1777, 1801, 1889, 1913, 2089, 2113, 2129, 2273, 2281, 2393, 2441, 2473, 2593, 2657, 2689

Offset: 1

Warren D. Smith

nonn

Primes p such that x^4 == 2 has more than two (in fact four) solutions mod p. This is the sequence of terms common to A040098 (primes p such that x^4 == 2 has a solution mod p) and A007519 (primes of form 8n+1). Solutions mod p are represented by integers from 0 to p - 1. For p > 2, i is a solution mod p of x^4 == 2 iff p - i is a solution mod p of x^4 == 2, thus the sum of first and fourth solution is p and so is the sum of second and third solution. The solutions are given in A065909, A065910, A065911 and A065912. - Klaus Brockhaus, Nov 28 2001

Primes of the form x^2+64y^2. - T. D. Noe, May 13 2005

N. J. A. Sloane and Vincenzo Librandi, Table of n, a(n) for n = 1..9769 (the first 1000 terms were found by Vincenzo Librandi)

Cf. A040098, A007519, A014754, A007522, A065909, A065910, A065911, A065912, A070179.

A014754(m) = local(p,s,x,z); forprime(p = 3,m,s = []; for(x = 0,p-1, if(x^4%p == 2%p,s = concat(s,[x]))); z = matsize(s)[2]; if(z>2,print1(p,",")))

{a(n) = local(m, c, x); if( n<1, 0, c = 0; m = 1; while( cMichael Somos, Mar 22 2008 */

forprime(p=1, 9999, p%8==1&&ispower(Mod(2, p), 4)&&print1(p", ")) \\ M. F. Hasler, Feb 18 2014

is_A014754(p)={p%8==1&&ispower(Mod(2, p), 4)&&isprime(p)} \\ M. F. Hasler, Feb 18 2014

Removed erroneous Mma program; extended b-file using first PARI program of M. F. Hasler. - N. J. A. Sloane, Jun 06 2014

A070184 Primes p such that x^8 = 2 has a solution mod p, but x^(8^2) = 2 has no solution mod p.

Original entry on oeis.org

257, 1217, 1249, 1553, 1777, 2113, 2657, 2833, 4049, 4273, 4481, 4993, 5297, 6449, 6481, 6689, 7121, 7489, 8081, 8609, 9137, 9281, 9649, 10177, 10337, 10369, 10433, 11329, 11617, 11633, 12241, 12577, 13121, 13441, 13633, 14321, 14753, 15073, 15121, 15569, 16417, 16433, 16673, 17137

Offset: 1

Klaus Brockhaus, Apr 29 2002

Is this the same as "x^8 = 2 (mod p) has a solution but x^32 = 2 (mod p) doesn't"? It appears that this sequence is exactly the complement of A045316 in A059349. - M. F. Hasler, Jun 21 2024

M. F. Hasler, Table of n, a(n) for n = 1..2000, Jun 22 2024

Cf. A045315, A059667, A070179 - A070183, A070185 - A070188.

[p: p in PrimesUpTo(15000) | not exists{x: x in ResidueClassRing(p) | x^64 eq 2} and exists{x: x in ResidueClassRing(p) | x^8 eq 2}]; // Vincenzo Librandi, Sep 21 2012

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^5, if (ok(p,2,8,8^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

select( {is_A070184(p)=Mod(2,p)^(p\gcd(8,p-1))==1 && Mod(2,p)^(p\gcd(64,p-1))!=1 && isprime(p)}, primes(1999)) \\ The only composite numbers that would pass the test without isprime are A242880. - M. F. Hasler, Jun 22 2024

from itertools import islice
from sympy import is_nthpow_residue, nextprime
def A070184_gen(startvalue=2): # generator of terms >= startvalue
    p = max(1,startvalue-1)
    while (p:=nextprime(p)):
        if is_nthpow_residue(2,8,p) and not is_nthpow_residue(2,64,p):
            yield p
A070184_list = list(islice(A070184_gen(),10)) # Chai Wah Wu, Jun 23 2024

A070185 Primes p such that x^9 = 2 has a solution mod p, but x^(9^2) = 2 has no solution mod p.

Original entry on oeis.org

3943, 5347, 11287, 12853, 14149, 17659, 20143, 21061, 21277, 23059, 23599, 25759, 26407, 26731, 29863, 32833, 33751, 35803, 37747, 38287, 39367, 39799, 46441, 47737, 47791, 54919, 57781, 59887, 61291, 62047, 63127, 65557, 68311, 71443, 73063, 75169, 78301, 79273, 82351, 84457, 84673, 86077, 88129, 90289

Offset: 1

Klaus Brockhaus, Apr 29 2002

nonn

Cf. A049596, A059667, A070179 - A070184, A070186 - A070188.

Cf. A059354.

PARI
```
forprime(p=2,72000,x=0; while(x
				
```

N=10^6;  default(primelimit,N);
ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,N, if (ok(p,2,9,9^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

A070186 Primes p such that x^10 = 2 has a solution mod p, but x^(10^2) = 2 has no solution mod p.

Original entry on oeis.org

17, 97, 137, 151, 193, 241, 313, 409, 433, 449, 457, 569, 641, 673, 769, 809, 857, 929, 953, 977, 1009, 1129, 1297, 1409, 1489, 1657, 1697, 1873, 1993, 2017, 2137, 2153, 2297, 2377, 2417, 2609, 2617, 2633, 2713, 2729, 2753, 2777, 2897, 2953, 3169, 3209

Offset: 1

Klaus Brockhaus, Apr 29 2002

Cf. A049542, A059667, A070179 - A070185, A070187, A070188.

[p: p in PrimesUpTo(3500) | not exists{x: x in ResidueClassRing(p) | x^100 eq 2} and exists{x: x in ResidueClassRing(p) | x^10 eq 2}]; // Vincenzo Librandi, Sep 21 2012

PARI
```
forprime(p=2,3300,x=0; while(x
				
```

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^5, if (ok(p,2,10,10^2),print1(p,", "))); \\ A070186
/* Joerg Arndt, Sep 21 2012 */

A070180 Primes p such that x^3 = 2 has a solution mod p, but x^(3^2) = 2 has no solution mod p.

Original entry on oeis.org

109, 307, 433, 739, 811, 919, 1423, 1459, 1999, 2017, 2143, 2179, 2251, 2287, 2341, 2791, 2917, 2953, 3061, 3259, 3331, 3457, 3889, 4177, 4339, 4519, 4663, 5113, 5167, 5419, 5437, 5653, 6301, 6427, 6661, 6679, 6967, 7723, 7741, 8011, 8389, 8713

Offset: 1

Klaus Brockhaus, Apr 29 2002

Cf. A040028, A049596, A059262, A059667, A070179, A070181 - A070188.

[p: p in PrimesUpTo(10000) | not exists{x: x in ResidueClassRing(p) | x^9 eq 2} and exists{x: x in ResidueClassRing(p) | x^3 eq 2}]; // Vincenzo Librandi, Sep 21 2012

PARI
```
forprime(p=2,8800,x=0; while(x
				
```

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^4, if (ok(p,2,3,3^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

A070181 Primes p such that x^4 = 2 has a solution mod p, but x^(4^2) = 2 has no solution mod p.

Original entry on oeis.org

113, 281, 353, 577, 593, 617, 1033, 1049, 1097, 1153, 1193, 1201, 1217, 1249, 1481, 1553, 1601, 1753, 1777, 1889, 2129, 2273, 2281, 2393, 2473, 2689, 2833, 2857, 3049, 3089, 3121, 3137, 3217, 3313, 3361, 3529, 3673, 3761, 3833, 4001, 4049, 4153, 4217

Offset: 1

Klaus Brockhaus, Apr 29 2002

Cf. A040098, A045315, A045316, A059667, A070179, A070180, A070182 - A070188.

[p: p in PrimesUpTo(5000) | not exists{x: x in ResidueClassRing(p) | x^16 eq 2} and exists{x: x in ResidueClassRing(p) | x^4 eq 2}]; // Vincenzo Librandi, Sep 21 2012

PARI
```
forprime(p=2,4250,x=0; while(x
				
```

ok(p, r, k1, k2)={
    if (  Mod(r,p)^((p-1)/gcd(k1,p-1))!=1, return(0) );
    if (  Mod(r,p)^((p-1)/gcd(k2,p-1))==1, return(0) );
    return(1);
}
forprime(p=2,10^5, if (ok(p,2,4,4^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

cp's OEIS Frontend

A244626 Composite numbers k congruent to 5 (mod 8) such that 2^((k-1)/2) mod k = k-1.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Extensions

A244628 Composite numbers n such that n == 3 (mod 8) and 2^((n-1)/2) == -1 (mod n).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

A059667 Primes p such that x^49 = 2 has no solution mod p, but x^7 = 2 has a solution mod p.

Views

Author

Keywords

Links

Crossrefs

Programs

Mathematica

PARI

PARI

A070188 Primes p such that x^12 = 2 has a solution mod p, but x^(12^2) = 2 has no solution mod p.

Views

Author

Keywords

Crossrefs

Programs

Magma

PARI

PARI

A014754 Primes p == 1 mod 8 such that 2 and -2 are both 4th powers (one implies other) mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

PARI

PARI

PARI

Extensions

A070184 Primes p such that x^8 = 2 has a solution mod p, but x^(8^2) = 2 has no solution mod p.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

PARI

PARI

Python

A070185 Primes p such that x^9 = 2 has a solution mod p, but x^(9^2) = 2 has no solution mod p.

Views

Author

Keywords

Crossrefs

Programs

PARI

PARI

A070186 Primes p such that x^10 = 2 has a solution mod p, but x^(10^2) = 2 has no solution mod p.

Views

Author

Keywords

Crossrefs

Programs

Magma