A275596 - OEIS

%I #27 Aug 27 2016 10:18:44

%S 11,17,23,31,37,59,73,83,97,103,167,233,257,263,307,359,401,431,433,

%T 443,467,479,487,491,499,569,727,733,743,773,839,863,877,911,919,971,

%U 991,1013,1039,1069,1091,1097,1103,1153,1163,1193,1229,1237,1297,1409

%N 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.

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

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

%C If p is in the sequence, then 2^gcd(p-1,q-1) == 1 (mod pq). - _Robert Israel_, Aug 03 2016

%C From _Thomas Ordowski_, Aug 03 2016: (Start)

%C 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, ...

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

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

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

%e 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.

%p filter:= proc(p)

%p      local Q,q,t;

%p      if not isprime(p) then return false fi;

%p      Q:= select(type, map(t -> t[1], ifactors(2^(p-1)-1,easy)[2]),integer);

%p      q:= min(select(`>`,Q,p));

%p      if not q::integer then

%p        q:= min(select(`>`,numtheory:-factorset(2^(p-1)-1),p));

%p        if not q::integer then return false fi;

%p      fi;

%p      if 2 &^(q-1) mod p <> 1 then return false fi;

%p      for t from p+2 to q-2 by 2 do

%p        if isprime(t) and 2 &^(q-1) mod t = 1 then return false fi

%p      od;

%p      true

%p end proc;

%p select(filter, [seq(p,p=3..700,2)]); # _Robert Israel_, Aug 03 2016

%o (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

%K nonn

%O 1,1

%A _Thomas Ordowski_, Aug 03 2016

%E a(2) inserted by _Charles R Greathouse IV_, Aug 03 2016

%E a(6)-a(21) from _Charles R Greathouse IV_, Aug 03 2016

%E a(22)-a(30) from _Robert Israel_, Aug 03 2016

%E a(31)-a(50) from _Charles R Greathouse IV_, Aug 03 2016