A367229 Fermat pseudoprimes to base 2 that are products of two Mersenne numbers (not necessarily distinct) that are larger than 1.

1905, 15841, 129921, 8322945, 66977281, 4395899025409, 4398012825601, 140735340806145, 36892925197465616385, 2342736497361113055105, 4951750712408555360305545217, 39304596247310823728047193985, 2535301191011725837253847547905, 1298074214624262174166747352924161

Offset: 1

Author

Amiram Eldar, Nov 11 2023

Keywords

• nonn

Comments

Without the restriction to Mersenne numbers that are larger than 1 all the composite Mersenne numbers (A065341) will be terms.

Szymiczek (1964) proved that if p is a prime == 7 (mod 8) (A007522) and t = 2^phi((p-1)/2), then M(p)*M(t) is a Fermat pseudoprime to base 2, where phi is the Euler totient function (A000010) and M(n) = 2^n-1 = A000225(n) is the n-th Mersenne number. The smallest pseudoprime that is generated by this rule, for p = 7 and t = 2^phi((7-1)/2) = 4, is M(7) * M(4) = 1905. The next two, corresponding to p = 23 and 31, have 316 and 87 digits, respectively.

Rotkiewicz and Makowski (1966) proved that if p is a prime or a Fermat pseudoprime to base 2 such that o(p), the multiplicative order of 2 modulo p, is odd (A014663 for primes, A367230 for pseudoprimes), then for each positive k <= p/o(o(p)), if t = 2^(k*o(o(p))) then M(p)*M(t) is a Fermat pseudoprime to base 2. For example, for p = 7, p/o(o(7)) = 7/2, so for k = 1, 2 and 3 the resulting pseudoprimes are 1905, 8322945 and 2342736497361113055105, respectively.

Examples

			a(1) = 1905 = (2^4-1) * (2^7-1).
a(2) = 15841 = (2^5-1) * (2^9-1).
		

Links

• Amiram Eldar, Table of n, a(n) for n = 1..242
• Andrzej Rotkiewicz and Andrzej Makowski, On Pseudoprime Numbers of the Form M_p M_t, Elemente der Mathematik, Vol. 21 (1966), pp. 133-134.
• Kazimierz Szymiczek, On prime numbers p,q and r such that pq, pr, and qr are pseudoprimes, Colloquium Mathematicum, Vol. 13 (1964), pp. 259-263; alternative link.

Crossrefs

Cf. A000010, A000225, A001567, A007522, A014663, A065341, A367230.

Programs

Mathematica

With[{max = 110}, m = 2^Range[2, max] - 1; Sort@ Select[Times @@@ Subsets[m, {2}], # < m[[-1]] && PowerMod[2, # - 1, #] == 1 &]]