A059667 -id:A059667 - cp's OEIS frontend

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

17, 41, 97, 137, 193, 241, 313, 401, 409, 433, 449, 457, 521, 569, 641, 673, 761, 769, 809, 857, 929, 953, 977, 1009, 1129, 1297, 1321, 1361, 1409, 1489, 1657, 1697, 1873, 1993, 2017, 2081, 2137, 2153, 2161, 2297, 2377, 2417, 2521, 2609, 2617, 2633, 2713

Offset: 1

Klaus Brockhaus, Apr 29 2002

Complement of A014754 with regard to primes of the form 8*k+1.
These appear to be the primes p for which 4^((p-1)*n/8) mod p = (p-2)*( n mod 2)+1. For example, 4^(5*n) mod 41 = 1,40,1,40,1,40...= 39*(n mod 2)+1 and 4^(30*n) mod 241 = 1,240,1,240,1,240...= 239*(n mod 2) +1. - Gary Detlefs, Jul 06 2014
Primes p == 1 mod 8 such that 2^((p-1)/4) == -1 mod p. - Robert Israel, Jul 06 2014
A very similar sequence is A293394. - Jonas Kaiser, Nov 08 2017

Bruno Berselli, Table of n, a(n) for n = 1..1000

Cf. A038873, A040098, A040100, A059667, A070180-A070188, A014754.

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

select(p -> isprime(p) and 2 &^((p-1)/4) mod p = p-1, [8*k+1$k=1..10000]); # Robert Israel, Jul 06 2014

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

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

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,2,2^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

is(n)=n%8==1 && Mod(2,n)^(n\4)==-1 && isprime(n) \\ Charles R Greathouse IV, Nov 10 2017

Primes of the form 8*k + 1 but not x^2 + 64*y^2. - Michael Somos, Mar 22 2008

a(n) ~ 8n log n. - Charles R Greathouse IV, Nov 10 2017

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 */

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

A042967 Primes p such that x^7 = 2 has no solution mod p.

Original entry on oeis.org

29, 43, 71, 113, 127, 197, 211, 239, 281, 337, 379, 421, 449, 463, 491, 547, 617, 659, 701, 743, 757, 827, 883, 911, 967, 1009, 1051, 1093, 1289, 1303, 1373, 1429, 1471, 1499, 1583, 1597, 1667, 1723, 1877, 1933, 2017, 2087, 2129, 2213, 2269, 2297, 2311, 2339, 2381, 2423, 2437, 2521

Offset: 1

N. J. A. Sloane

Complement of A042966 relative to A000040. Coincides for the first 96 terms with the sequence of primes p such that x^49 = 2 has no solution mod p (first divergence is at 4999, cf. A059667). - Klaus Brockhaus, Feb 04 2001

			x^7 = 2 has no solution mod 29, so 29 is in the sequence.
8^7 = 2097152 and (2097152 - 2)/31 = 67650, so 31 is not in the sequence.

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

Cf. A000040, A042966, A059667.

[p: p in PrimesUpTo(3000) | forall{x: x in ResidueClassRing(p) | x^7 ne 2}]; // Vincenzo Librandi, Aug 21 2012

[p: p in PrimesUpTo(2600) | not exists{x : x in ResidueClassRing(p) | x^7 eq 2} ]; // Vincenzo Librandi, Sep 19 2012

sevPow2ModPQ[p_] := Reduce[Mod[x^7 - 2, p] == 0, x, Integers] == False; Select[Prime[Range[700]], sevPow2ModPQ] (* Vincenzo Librandi, Sep 19 2012 *)

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 */

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

Original entry on oeis.org

17, 41, 137, 401, 433, 449, 457, 521, 569, 641, 761, 809, 857, 919, 929, 953, 977, 1361, 1409, 1423, 1657, 1697, 1999, 2017, 2081, 2143, 2153, 2287, 2297, 2417, 2609, 2633, 2729, 2753, 2777, 2791, 2801, 2897, 2953, 3041, 3209, 3329, 3457, 3593, 3617

Offset: 1

Klaus Brockhaus, Apr 29 2002

Robert Israel, Table of n, a(n) for n = 1..10000

Cf. A040992, A049568, A059264, A059667, A070179, A070180, A070181, A070182, A070184, A070185, A070186, A070187, A070188.

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

select(p -> isprime(p) and [msolve(x^6=2,p)]<>[] and [msolve(x^36=2,p)]=[] , [seq(i,i=3..10^4,2)]); # Robert Israel, May 13 2018

PARI
```
forprime(p=2,3700,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,6,6^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

from itertools import count, islice
from sympy import nextprime, is_nthpow_residue
def A070183_gen(startvalue=2): # generator of terms >= startvalue
    p = max(nextprime(startvalue-1),2)
    while True:
        if is_nthpow_residue(2,6,p) and not is_nthpow_residue(2,36,p):
            yield p
        p = nextprime(p)
A070183_list = list(islice(A070183_gen(),20)) # Chai Wah Wu, May 02 2024

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

Original entry on oeis.org

12101, 13553, 30493, 32429, 44771, 66067, 103577, 128987, 180533, 182711, 187793, 201829, 242243, 257489, 264749, 299113, 314359, 330331, 337349, 341947, 356467, 371471, 431729, 442619, 475289, 484243, 505781, 513767, 540871, 558053, 564103, 573299, 581527, 582011, 586367, 593869, 596047, 630169

Offset: 1

Klaus Brockhaus, Apr 29 2002

nonn

Cf. A049543, A059667, A070179 - A070186, A070188.

PARI
```
forprime(p=2,550000,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,11,11^2),print1(p,", ")));
/* Joerg Arndt, Sep 21 2012 */

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Maple

PARI

PARI

PARI

PARI

Formula

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

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

A042967 Primes p such that x^7 = 2 has no solution mod p.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Magma

Mathematica

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

PARI

PARI

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

Views

Author

Keywords

Crossrefs

Programs

Magma

PARI

PARI

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

Views

Author

Keywords

Crossrefs