A347906 Numbers k such that 2^(2*k-1) == 1 (mod k).

1, 80519, 107663, 1284113, 1510313, 3933023, 4557713, 24849833, 71871113, 80646143, 98058097, 104832833, 106694033, 146987033, 168204191, 188997463, 205428713, 332693873, 333681761, 336327863, 380284847, 533039513, 552913169, 711999113, 725943719, 805031663, 1000519033, 1069441313, 1476327353, 1610020913

Offset: 1

Author

Jianing Song, Sep 18 2021

Keywords

• nonn

Comments

Odd numbers k such that ord(2,k) divides 2*k-1, where ord(2,k) is the multiplicative order of 2 modulo k.

Numbers k such that 2*k is in A006935. For k > 1, k is a term if and only if 2*k is an even pseudoprime to base 2.

Odd terms in A130421. Complement of A347908 in A130421.

Terms > 1 must be composite, since for odd primes p we have 2^(2*p-1) == 2 (mod p). If k > 1 is a term, then 2*k-1 must also be composite, since ord(2,k) | (2*k-1) and ord(2,k) <= eulerphi(k) <= k-1 < 2*k-1.

If k > 1 is a term, then (2^(2*k-1) - 1)/k is composite. Proof: since 2*k-1 is composite, write 2*k-1 = u*v, u >= v > 1, then (2^(2*k-1) - 1)/k = (2^u - 1)*(2^(u*(v-1)) + ... + 2^u + 1)/k. Since k | 2^(2*k-1) - 1, there exist positive integers a,b such that a*b = k and that a | 2^u - 1 and b | 2^(u*(v-1)) + ... + 2^u + 1. Note that (2^u - 1)/a, (2^(u*(v-1)) + ... + 2^u + 1)/b >= (2^u - 1)/k >= (2^sqrt(2*k-1) - 1)/k > 1, so (2^(2*k-1) - 1)/k is the product of two integers > 1, so it is composite.

2^t - 1 is a term if and only if 2^(t+1) == 3 (mod t) (t = 1, 111481, 465793, ... in A296370).

Examples

			80519 is a term since 80519 divides 2^161037 - 1 (the multiplicative order of 2 modulo 80519 is 261, which is a divisor of 161037). Note that 2 * 80519 = 161038 = A006935(2) is the smallest even pseudoprime to base 2.
		

Links

• Jianing Song, Table of n, a(n) for n = 1..1319 (contains all terms below 10^15; based on Max Alekseyev's b-file for A006935)

Crossrefs

Cf. A006935, A130421, A347908, A296370.

Cf. A347907 (a similar sequence).

Programs

PARI

isA347906(k) = if(k%2 && !isprime(k), Mod(2, k)^(2*k-1)==1, 0)

Formula

a(n) = A006935(n)/2.