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

91, 247, 325, 343, 485, 703, 871, 901, 931, 949, 1099, 1111, 1157, 1247, 1261, 1271, 1387, 1445, 1525, 1649, 1765, 1807, 1891, 1975, 2047, 2059, 2071, 2117, 2501, 2701, 2863, 2871, 3277, 3281, 3365, 3589, 3845, 4069, 4141, 4187, 4291, 4371, 4411, 4525

Offset: 1

Author

Arkadiusz Wesolowski, Aug 11 2017

Keywords

• nonn

Comments

If the condition "odd composite numbers" in the definition is replaced by "odd numbers", then every odd prime number is in the sequence.

This is not a subsequence of A290543 (for example, 65683 is missing in A290543).

Examples

			91 is in the sequence because:
1) it is an odd composite number.
2) k^90 == 1 (mod 91) and gcd(k^45 - 1, 91) = 1 with k = 10 < sqrt(91) + 1.
		

Links

• Giovanni Resta, Table of n, a(n) for n = 1..10000 (first 1000 terms from A. Wesolowski)
• Wikipedia, Pocklington primality test.
• Index entries for sequences related to pseudoprimes.

Crossrefs

Cf. A130569, A290543.

Programs

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;

Mathematica

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

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