cp's OEIS Frontend

A290812 Odd composite numbers m such that k^(m - 1) == 1 (mod m) and gcd(k^((m - 1)/2) - 1, m) = 1 for some integer k in the interval [2, sqrt(m) + 1].

%I A290812 #23 Nov 06 2023 03:01:18
%S A290812 91,247,325,343,485,703,871,901,931,949,1099,1111,1157,1247,1261,1271,
%T A290812 1387,1445,1525,1649,1765,1807,1891,1975,2047,2059,2071,2117,2501,
%U A290812 2701,2863,2871,3277,3281,3365,3589,3845,4069,4141,4187,4291,4371,4411,4525
%N A290812 Odd composite numbers m such that k^(m - 1) == 1 (mod m) and gcd(k^((m - 1)/2) - 1, m) = 1 for some integer k in the interval [2, sqrt(m) + 1].
%C A290812 If the condition "odd composite numbers" in the definition is replaced by "odd numbers", then every odd prime number is in the sequence.
%C A290812 This is not a subsequence of A290543 (for example, 65683 is missing in A290543).
%H A290812 Giovanni Resta, <a href="/A290812/b290812.txt">Table of n, a(n) for n = 1..10000</a> (first 1000 terms from A. Wesolowski)
%H A290812 Wikipedia, <a href="https://en.wikipedia.org/wiki/Pocklington_primality_test">Pocklington primality test</a>.
%H A290812 <a href="/index/Ps#pseudoprimes">Index entries for sequences related to pseudoprimes</a>.
%e A290812 91 is in the sequence because:
%e A290812 1) it is an odd composite number.
%e A290812 2) k^90 == 1 (mod 91) and gcd(k^45 - 1, 91) = 1 with k = 10 < sqrt(91) + 1.
%t A290812 Select[Range[3, 4525, 2], Function[n, And[CompositeQ@ n, AnyTrue[Range[2, Sqrt[n] + 1], And[PowerMod[#, n - 1, n] == 1, CoprimeQ[#^((n - 1)/2) - 1, n]] &]]]] (* _Michael De Vlieger_, Aug 16 2017 *)
%o A290812 (Magma) lst:=[]; for n in [3..4525 by 2] do if not IsPrime(n) then for a in [2..Floor(Sqrt(n)+1)] do if Modexp(a, n-1, n) eq 1 and GCD(a^Truncate((n-1)/2)-1, n) eq 1 then Append(~lst, n); break; end if; end for; end if; end for; lst;
%o A290812 (PARI) is(n) = if(n > 1 && n%2==1 && !ispseudoprime(n), for(x=2, sqrt(n)+1, if(Mod(x, n)^(n-1)==1 && gcd(x^((n-1)/2)-1, n)==1, return(1)))); 0 \\ _Felix Fröhlich_, Aug 18 2017
%Y A290812 Cf. A130569, A290543.
%K A290812 nonn
%O A290812 1,1
%A A290812 _Arkadiusz Wesolowski_, Aug 11 2017