

A300193


Pseudosafeprimes: numbers n = 2m+1 with 2^m congruent to n+1 or 3n1 modulo m*n, but m composite.


6



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


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


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.


EXAMPLE

n = 683 = 2*341+1 is in the sequence because 2^341 == 2048 == 3*n1 (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.


MATHEMATICA

For[m=1, (n=2m+1)<4444444, ++m, If[MemberQ[{n+1, 3n1}, PowerMod[2, m, m*n]] &&!PrimeQ[m], Print[n]]] (* Francois R. Grieu, Mar 19 2018 *)


PROG

(PARI) isok(n) = {if ((n % 2) && (m=(n1)/2) && !isprime(m), v = lift(Mod(2, m*n)^m); if ((v == n+1)  (v == 3*n1), return (1)); ); return (0); } \\ Michel Marcus, Mar 06 2018


CROSSREFS

Cf. A005385, A005384, A000040, A001262, A001567, A006935, A006970.
Sequence in context: A174105 A320772 A045154 * A234502 A089201 A292174
Adjacent sequences: A300190 A300191 A300192 * A300194 A300195 A300196


KEYWORD

nonn


AUTHOR

Francois R. Grieu, Mar 05 2018


STATUS

approved



