A300193 Pseudo-safe-primes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n-1 modulo m*n, but m composite.

683, 1123, 1291, 4931, 16963, 25603, 70667, 110491, 121403, 145771, 166667, 301703, 424843, 529547, 579883, 696323, 715523, 854467, 904103, 1112339, 1175723, 1234187, 1306667, 1444523, 2146043, 2651687, 2796203, 2882183, 3069083, 3216931, 4284283, 4325443

Offset: 1

Author

Francois R. Grieu, Mar 05 2018

Keywords

• nonn

Comments

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.

If that congruence is verified and m is prime, then n is prime (follows from a result by Fedor Petrov).

That congruence is equivalent to the combination: 2^m == +-1 (mod n) and 2^m == 2 (mod m).

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.

Even m belong to A006935. The first is a(986) = 252435584573, m = 126217792286 (cf. A303008).

Examples

			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.
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.
n = 5 = 2*2+1 is not in the sequence because m = 2 is prime.
		

Links

• Francois R. Grieu, Table of n, a(n) for n = 1..2796 (terms <2^42).
• Peter Košinár, Report of a composite n, Math StackExchange, Mar 06 2018.
• Fedor Petrov, Proof that the congruence and m prime imply n prime, MathOverflow.

Crossrefs

Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.

Programs

Mathematica

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

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