|
%I #28 Jul 20 2019 17:41:27
%S 3277,3281,29341,49141,80581,88357,104653,121463,196093,314821,320167,
%T 458989,476971,489997,491209,721801,800605,838861,873181,877099,
%U 973241,1004653,1251949,1268551,1302451,1325843,1373653,1397419,1441091,1507963,1509709,1530787,1590751,1678541,1809697
%N The "non-residue" pseudoprimes: odd composite numbers n such that b(n)^((n-1)/2) == -1 (mod n), where base b(n) = A020649(n).
%C As is well known, for an odd prime p, b(p) is the smallest quadratic non-residue b modulo p if and only if b(p) is the smallest base b such that b^((p-1)/2) == -1 (mod p). Note that b(n) is always a prime.
%C Conjecture: If 2^((n-1)/2) == -1 (mod n), then b(n) = 2, where b(n) as above. This is true for odd primes n; is it for odd composites n? If so, then all composite numbers n such that 2^((n-1)/2) == -1 (mod n) are in this sequence.
%C It seems that, for defined pseudoprimes n (similar to the odd primes p),
%C b(n) is the smallest base b such that b^((n-1)/2) == -1 (mod n), although this is not required by their definition.
%C Note: a "non-residue" pseudoprime n is a strong pseudoprime to base b(n); the Jacobi symbol (b(n)/n) = -1, where b(n) is the smallest non-residue modulo n; such a pseudoprime n is not a Proth number, so n = k*2^m + 1 with odd k > 2^m.
%C Problem: are there infinitely many such numbers?
%e 2^((3277-1)/2) == -1 (mod 3277), 3^((3281-1)/2) == -1 (mod 3281), ...
%t residueQ[n_, m_] := Module[{ans = 0}, Do[If[Mod[k^2, m] == n, ans = True; Break[]], {k, 0, Floor[m/2]}]; ans]; A020649[n_] := Module[{m = 0}, While[ residueQ[m, n], m++]; m]; aQ[n_] := CompositeQ[n] && PowerMod[A020649[n], ((n - 1)/2), n] == n - 1; Select[Range[3, 110000, 2], aQ] (* _Amiram Eldar_, Apr 27 2019 *)
%Y Cf. A001262, A006970, A020649, A047713, A053760, A244626, A307798 (the "residue" pseudoprimes), A307809.
%K nonn
%O 1,1
%A _Thomas Ordowski_, Apr 27 2019
%E More terms from _Amiram Eldar_, Apr 27 2019
|
