Compute the Carmichael function Task description

In number theory, the Carmichael function λ takes a positive integer n and returns the least positive integer k so that the k-th power of each integer coprime to n equals 1 modulo n.

Given a positive integer n, your solution must compute λ(n). The shortest code in bytes wins.

Your program should theoretically work for arbitrarily large inputs, but doesn’t need to be efficient.

Tips

The sequence of all λ(n) is OEIS A002322.

An ungolfed Python implementation would look like

from fractions import gcd

def carmichael(n):
    coprimes = [x for x in range(1, n) if gcd(x, n) == 1]
    k = 1
    while not all(pow(x, k, n) == 1 for x in coprimes):
        k += 1
    return k


(In Python, pow(A, B, C) efficiently computes pow(A, B) % C.)

Test cases

Input    Output
1        1
2        1
3        2
10       4
35       12
101      100
530      52
3010     84
6511     3056
10000    500
Mathematica, 16 bytes

CarmichaelLambda


Well...