A346988 a(n) is the smallest k > n such that n^(k-n) == 1 (mod k).

2, 20737, 9299, 7, 13, 311, 15, 127, 17, 37, 14, 23, 17, 157, 106, 31, 29, 312953, 45, 95951, 41, 91, 33, 47, 28, 95, 35, 271, 35, 9629, 39, 311, 85, 397, 46, 71, 43, 1793, 95, 79, 61, 821, 51, 18881, 67, 103, 51, 12409, 73, 409969, 65, 87, 65, 71233, 63, 155, 65, 69, 87, 1962251, 91, 2443783, 155

Offset: 1

Author

Thomas Ordowski, Aug 10 2021

Keywords

• nonn

Comments

Smallest k > n coprime to n such that n^k == n^n (mod k).

If a(n) is a prime p, then n^(n-1) == 1 (mod p).

Links

• Chai Wah Wu, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A173572, A242865, A344681.

Programs

Mathematica

a[n_] := Module[{k = n + 1}, While[PowerMod[n, k - n, k] != 1, k++]; k]; Array[a, 60] (* Amiram Eldar, Aug 10 2021 *)

PARI

a(n) = my(k=n+1); while (Mod(n, k)^(k-n) != 1, k++); k; \\ Michel Marcus, Aug 10 2021

Python

def A346988(n):
    k, kn = n+1, 1
    while True:
        if pow(n,kn,k) == 1:
            return k
        k += 1
        kn += 1 # Chai Wah Wu, Aug 28 2021

Extensions

More terms from Amiram Eldar, Aug 10 2021