|
%I #74 Apr 24 2018 10:25:46
%S 683,1123,1291,4931,16963,25603,70667,110491,121403,145771,166667,
%T 301703,424843,529547,579883,696323,715523,854467,904103,1112339,
%U 1175723,1234187,1306667,1444523,2146043,2651687,2796203,2882183,3069083,3216931,4284283,4325443
%N Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.
%C The definition's congruence is verified if n is a safe prime A005385 with m the corresponding Sophie Germain prime A005384; and for a few other n, which form the sequence.
%C If that congruence is verified and m is prime, then n is prime (follows from a result by Fedor Petrov).
%C That congruence is equivalent to the combination: 2^m == +-1 (mod n) and 2^m == 2 (mod m).
%C Composite n are Euler pseudoprimes A006970, and strong pseudoprimes A001262 if m is odd. The smallest is a(6534) = (2^47+1)/3 = 46912496118443 = 283*165768537521 (cf. A303448). See Peter Košinár link.
%C Even m belong to A006935. The first is a(986) = 252435584573, m = 126217792286 (cf. A303008).
%H Francois R. Grieu, <a href="/A300193/b300193.txt">Table of n, a(n) for n = 1..2796 </a> (terms <2^42).
%H Peter Košinár, <a href="https://math.stackexchange.com/q/2673678/35016#comment5532212_2673678">Report of a composite n</a>, Math StackExchange, Mar 06 2018.
%H Fedor Petrov, <a href="https://mathoverflow.net/a/295517/122065">Proof that the congruence and m prime imply n prime</a>, MathOverflow.
%e n = 683 = 2*341+1 is in the sequence because 2^341 == 2048 == 3*n-1 (mod 341*683) and m = 341 = 11*13 is composite.
%e n = 301703 = 2*150851+1 is in the sequence because 2^150851 == 301704 == n+1 (mod 150851*301703) and m = 150851 = 251*601 is composite.
%e n = 5 = 2*2+1 is not in the sequence because m = 2 is prime.
%t For[m=1,(n=2m+1)<4444444,++m,If[MemberQ[{n+1,3n-1},PowerMod[2,m,m*n]] &&!PrimeQ[m], Print[n]]] (* _Francois R. Grieu_, Mar 19 2018 *)
%o (PARI) isok(n) = {if ((n % 2) && (m=(n-1)/2) && !isprime(m), v = lift(Mod(2, m*n)^m); if ((v == n+1) || (v == 3*n-1), return (1));); return (0);} \\ _Michel Marcus_, Mar 06 2018
%Y Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.
%K nonn
%O 1,1
%A _Francois R. Grieu_, Mar 05 2018
|
