A275596 Primes p such that q is the least prime factor > p of 2^(p-1)-1 and p is the greatest prime factor < q of 2^(q-1)-1.

11, 17, 23, 31, 37, 59, 73, 83, 97, 103, 167, 233, 257, 263, 307, 359, 401, 431, 433, 443, 467, 479, 487, 491, 499, 569, 727, 733, 743, 773, 839, 863, 877, 911, 919, 971, 991, 1013, 1039, 1069, 1091, 1097, 1103, 1153, 1163, 1193, 1229, 1237, 1297, 1409

Offset

1,1

Comments

Associated primes q = 31, 257, 89, 151, 73, ...

If p is in the sequence, then 2^(q-p) == 1 (mod pq).

If p is in the sequence, then 2^gcd(p-1,q-1) == 1 (mod pq). - Robert Israel, Aug 03 2016

From Thomas Ordowski, Aug 03 2016: (Start)

Theorem: if p == 1 (mod 4) and q = 2p-1 are primes, then 2^(q-p) == 1 (mod pq); such p = 37, 97, 157, 229, ...

Thus q divides 2^(p-1)-1 and p divides 2^(q-1)-1.

Problem: are there infinitely many pairs of primes p < q such that 2^(q-p) == 1 (mod pq)?

Lemma: let p < q are primes, then 2^(pq-1) == 1 (mod pq) if and only if 2^(q-p) == 1 (mod pq). (End)

Links

Table of n, a(n) for n=1..50.

Example

For p=11 and q=31, 2^(p-1)-1 = 3*p*q and 2^(q-1)-1 = 3*3*7*p*q*151*331.

Maple

filter:= proc(p)
     local Q, q, t;
     if not isprime(p) then return false fi;
     Q:= select(type, map(t -> t[1], ifactors(2^(p-1)-1, easy)[2]), integer);
     q:= min(select(`>`, Q, p));
     if not q::integer then
       q:= min(select(`>`, numtheory:-factorset(2^(p-1)-1), p));
       if not q::integer then return false fi;
     fi;
     if 2 &^(q-1) mod p <> 1 then return false fi;
     for t from p+2 to q-2 by 2 do
       if isprime(t) and 2 &^(q-1) mod t = 1 then return false fi
     od;
     true
end proc;
select(filter, [seq(p, p=3..700, 2)]); # Robert Israel, Aug 03 2016

Prog

(PARI) is(n)=if(!isprime(n), return(0)); my(f=factor(2^(n-1)-1)[, 1], q); f=select(k->k>n, f); if(#f==0, return(0)); q=f[1]; forprime(p=n+1, q-1, if(Mod(2, p)^(q-1)==1, return(0))); Mod(2, n)^(q-1)==1 \\ Charles R Greathouse IV, Aug 03 2016

Crossrefs

Sequence in context: A145481 A006621 A337359 * A158913 A363638 A066938

Adjacent sequences: A275593 A275594 A275595 * A275597 A275598 A275599

Keyword

nonn

Author

Thomas Ordowski, Aug 03 2016

Extensions

a(2) inserted by Charles R Greathouse IV, Aug 03 2016

a(6)-a(21) from Charles R Greathouse IV, Aug 03 2016

a(22)-a(30) from Robert Israel, Aug 03 2016

a(31)-a(50) from Charles R Greathouse IV, Aug 03 2016

Status

approved