[Question]
  [
## Task description
In number theory, the [Carmichael function](https://en.wikipedia.org/wiki/Carmichael_function) ***λ*** takes a positive integer **n** and returns the least positive integer **k** so that the **k**-th power of each integer [coprime](https://en.wikipedia.org/wiki/Coprime_integers) 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](https://oeis.org/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
```
  
[Answer]
## Mathematica, 16 bytes
```
CarmichaelLambda
```
Well...
[Answer]
# Python, ~~76~~ ~~73~~ 67 bytes
```
f=lambda n,k=1:1-any(a**-~k*~-a**k%n for a in range(n))or-~f(n,k+1)
```
[Try it online!](https://tio.run/nexus/python2#FY7BDoMgEETP5Sv2QgQLjdTSg4n9F1q1IepigB68@OuW3WQzuy@ZyZxTv7j1PThANfemM9rhLlxd62OuD12OmSNMIYIDjxAdfkeBUoaoj0kUz9XI069biBnSnljZWxpzHD@/mHzAxa8@C9OUkQwYBSEFCaPgrqBVYJoilrQg29LXEHtaY4iSs2OXLXrMouJ2AP0C/hgq4FAKwER15PkH)
A further byte could be saved by returning *True* instead of **1**.
### Alternative implementation
Using the same approach, there is also the following implementation by @feersum which doesn't use list comprehensions.
```
f=lambda n,k=1,a=1:a/n or(a**-~k*~-a**k%n<1)*f(n,k,a+1)or-~f(n,k+1)
```
Note that this implementation requires **O(nλ(n))** time. Efficiency could be improved dramatically while actually *decreasing* score to **66 bytes**, but the function would return *True* for input **2**.
```
f=lambda n,k=1,a=1:a/n or~-a**k*a**-~k%n<1==f(n,k,a+1)or-~f(n,k+1)
```
## Background
### Definitions and notation
All employed variables will denote integers; **n**, **k**, and **α** will denote *positive* integers; and **p** will denote a positive *prime*.
**a | b** if **b** is divisible by **a**, i.e., if there is **q** such that **b = qa**.
**a ≡ b (*mod* m)** if **a** and **b** have the same residue modulo **m**, i.e., if **m | a - b**.
**λ(n)** is the smallest **k** such that **ak ≡ 1 (*mod* n)** – i.e., such that **n | ak - 1** – for all **a** that are coprime to **n**.
**f(n)** is the smallest **k** such that **a2k+1 ≡ ak+1 (*mod* n)** – i.e., such that **n | ak+1(ak - 1)** – for all **a**.
### λ(n) ≤ f(n)
Fix **n** and let **a** be coprime to **n**.
By the definition of **f**, **n | af(n)+1(af(n) - 1)**. Since **a** and **n** do not have a common prime factor, neither do **af(n)+1** and **n**, which implies that **n | af(n) - 1**.
Since **λ(n)** is the smallest integer **k** such that **n | ak - 1** for all integers **a** that are coprime to **n**, it follows that **λ(n) ≤ f(n)**.
### λ(n) = f(n)
Since we've already established the inequality **λ(n) ≤ f(n)**, it is sufficient to verify that **k = λ(n)** satisfies the condition that defines **f**, i.e., that **n | aλ(n)+1(aλ(n) - 1)** for all **a**. For this purpose, we'll establish that **pα | aλ(n)+1(aλ(n) - 1)** whenever **pα | n**.
**λ(k) | λ(n)** whenever **k | n** ([source](https://en.wikipedia.org/wiki/Carmichael_function#Divisibility "Carmichael function - Wikipedia, the free encyclopedia")), so **(aλ(k) - 1)(aλ(n)-λ(k) + aλ(n)-2λ(k) + ⋯ + aλ(k) + 1) = aλ(n) - 1** and, therefore, **aλ(k) - 1 | aλ(n) - 1 | aλ(n)+1(aλ(n) - 1)**.
If **a** and **pα** are coprime, by the definition of **λ** and the above, **pα | aλ(pα) - 1 | aλ(n)+1(aλ(n) - 1)** follows, as desired.
If **a = 0**, then **aλ(n)+1(aλ(n) - 1) = 0**, which is divisible by all integers.
Finally, we must consider the case where **a** and **pα** have a common prime factor. Since **p** is prime, this implies that **p | a**. [Carmichael's theorem](https://en.wikipedia.org/wiki/Carmichael_function#Carmichael.27s_theorem "Carmichael function - Wikipedia, the free encyclopedia") establishes that **λ(pα) = (p - 1)pα - 1** if **p > 2** or **α < 3** and that **λ(pα) = pα - 2** otherwise. In all cases, **λ(pα) ≥ pα - 2 ≥ 2α - 2 > α - 2**.
Therefore, **λ(n) + 1 ≥ λ(pα) + 1 > α - 1**, so **λ(n) + 1 ≥ α** and **pα | pλ(n)+1 | aλ(n)+1 | aλ(n)+1(aλ(n) - 1)**. This completes the proof.
## How it works
While the definitions of **f(n)** and **λ(n)** consider all possible values of **a**, it is sufficient to test those that lie in **[0, ..., n - 1]**.
When **f(n, k)** is called, it computes **ak+1(ak - 1) % n** for all values of **a** in that range, which is **0** if and only if **n | ak+1(ak - 1)**.
If all computed residues are zero, **k = λ(n)** and `any` returns *False*, so **f(n, k)** returns **1**.
On the other hand, while **k < λ(n)**, `1-any(...)` will return **0**, so **f** is called recursively with an incremented value of **k**. The leading `-~` increments the return value of **f(n, k + 1)**, so we add **1** to **f(n, λ(n)) = 1** once for every integer in **[1, ..., λ(n) - 1]**. The final result is thus **λ(n)**.
[Answer]
# Mathematica without built-in, ~~58~~ 57 bytes
*Thanks to Martin Ender for finding an error, then saving me the bytes it took to fix it!*
*Thanks to miles for saving 1 byte! (which seemed like 2 to me)*
Built-ins are totally fine ... but for those who want to implement it without using brute force, here's a formula for the Carmichael function:
```
LCM@@(EulerPhi[#^#2]/If[#==2<#2,2,1]&@@@FactorInteger@#)&
```
If p is a prime, the Carmichael function λ(p^r) equals φ(p^r) = (p-1)\*p^(r-1)—*except* when p=2 and r≥3, in which case it's half that, namely 2^(r-2).
And if the prime-power factorization of n equals p1^r1 \* p2^r2 \* ..., then λ(n) equals the least common multiple of { λ(p1^r1), λ(p2^r2), ...}.
Runtime is one instant more than factoring the integer in the first place.
[Answer]
# [Templates Considered Harmful](https://github.com/feresum/tmp-lang), 246 bytes
```
Fun<Ap<Fun<If<Eq<A<2>,T>,A<1>,And<Eq<Ap<Fun<If<A<1>,Ap<A<0>,Rem<A<2>,A<1>>,A<1>>,A<2>>>,A<1,1>,A<2>>,T>,Sub<Ap<Fun<Rem<If<A<1>,Mul<A<2,1>,Ap<A<0>,Sub<A<1>,T>>>,T>,A<1,2>>>,A<1>>,T>>,Ap<A<0>,Add<A<1>,T>,A<1,1>>,Ap<A<0>,A<1>,Sub<A<2>,T>>>>,T,A<1>>>
```
An unnamed function (not that there are named functions).
This is a forgotten esolang of mine which is interpreted by a C++ compiler instantiating templates. With the default max template depth of `g++`, it can do λ(35), but it can't do λ(101) (the lazy evaluation makes things worse).
[Answer]
# Haskell, ~~57~~ 56 bytes
```
f n=[k|k<-[1..],and[mod(m^k)n<2|m<-[1..n],gcd m n<2]]!!0
```
[Answer]
# Jelly, 2 bytes
```
Æc
```
[Thank you for the builtin, @Lynn](https://github.com/DennisMitchell/jelly/commit/6136ca6a64b3247e2de53587cc4305d0255f7451)
[Answer]
# Pyth - ~~19~~ ~~18~~ 17 bytes
*One byte saved thanks to @TheBikingViking.*
Straight up brute force.
```
f!sm*t.^dTQq1iQdQ
```
[Try it online here](http://pyth.herokuapp.com/?code=f%21sm%2at.%5EdTQq1iQdQ&input=35&debug=0).
[Answer]
# Ruby, ~~59~~ 56 bytes
```
->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}
```
[Answer]
# J, ~~28~~ 27 bytes
```
[:*./@(5&p:%2^0=8&|)2^/@p:]
```
The Carmichael function is λ(*n*) and the totient function is φ(*n*).
Uses the definition where λ(*p**k*) = φ(*p**k*)/2 if *p* = 2 and *k* > 2 else φ(*p**k*). Then, for general *n* = *p*1*k*1 *p*2*k*2 ⋯ *p**i**k**i*, λ(*n*) = LCM[ λ(*p*1*k*1) λ(*p*2*k*2) ⋯ λ(*p**i**k**i*) ].
## Usage
Extra commands used to format multiple input/output.
```
   f =: [:*./@(5&p:%2^0=8&|)2^/@p:]
   f 530
52
   (,.f"0) 1 2 3 10 35 101 530 3010 6511 10000
    1    1
    2    1
    3    2
   10    4
   35   12
  101  100
  530   52
 3010   84
 6511 3056
10000  500
```
## Explanation
```
[:*./@(5&p:%2^0=8&|)2^/@p:]  Input: integer n
                          ]  Identity function, get n
                    2   p:   Get a table of prime/exponent values for n
                     ^/@     Raise each prime to its exponent to get the prime powers of n
[:    (            )         Operate on the prime powers
                8&|            Take each modulo 8
              0=               Test if its equal to 0, 1 if true else 0
            2^                 Raise 2 to the power of each
       5&p:                    Apply the totient function to each prime power
           %                   Divide it by the powers of 2
  *./@                       Reduce using LCM and return
```
[Answer]
## JavaScript (ES6), ~~143~~ 135 bytes
*Edit: saved 8 bytes thanks to Neil*
An implementation using functional programming.
```
n=>(A=[...Array(n).keys()]).find(k=>k&&!c.some(c=>A.slice(0,k).reduce(y=>y*c%n,1)-1),c=A.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1
```
### Ungolfed and commented
```
n =>                                          // Given a positive integer n:
  (A = [...Array(n).keys()])                  // Build A = [0 ... n-1].
  .find(k =>                                  // Try to find k in [1 ... n-1] such as
    k && !c.some(c =>                         // for each coprime c: c^k ≡ 1 (mod n).
      A.slice(0, k).reduce(y =>               // We use reduce() to compute
        y * c % n, 1                          // c^k mod n.
      ) - 1                                   // Compare it with 1.
    ),                                        // The list of coprimes is precomputed
    c = A.filter(x =>                         // before the find() loop is executed:
      (                                       // for each x in [0 ... n-1], keep
        g = (x, y) => x ? g(y % x, x) : y     // only integers that verify:
      )(x, n) == 1                            // gcd(x, n) = 1
    )                                         // (computed recursively)
  ) || 1                                      // Default result is 1 (for n = 1)
```
### Demo
Although it does work for `6511` and `10000`, I won't include them here as it tends to be a bit slow.
```
let f =
n=>(A=[...Array(n).keys()]).find(k=>k&&!c.some(c=>A.slice(0,k).reduce(y=>y*c%n,1)-1),c=A.filter(x=>(g=(x,y)=>x?g(y%x,x):y)(x,n)==1))||1
console.log(f(1));     // 1
console.log(f(2));     // 1
console.log(f(3));     // 2
console.log(f(10));    // 4
console.log(f(35));    // 12
console.log(f(101));   // 100
console.log(f(530));   // 52
console.log(f(3010));  // 84
```
[Answer]
# Actually, ~~30~~ ~~28~~ ~~25~~ ~~19~~ 26 bytes
The Carmichael function, `λ(n)` where `n = p_0**k_0 * p_1**k_1 * ... * p_a**k_a`, is defined as the least common multiple (LCM) of `λ(p_i**k_i)` for the maximal prime powers `p_i**k_i` that divide into `n`. Given that for every prime power except where the prime is `2`, the Carmichael function is equivalent to the Euler totient function, `λ(n) == φ(n)`, we use `φ(n)` instead. For the special case of `2**k` where `k ≥ 3`, we just check if `2**3 = 8` divides into `n` at the beginning of the program, and divide by 2 if it does.
Unfortunately, Actually doesn't currently have an LCM builtin, so I made a brute-force LCM. Golfing suggestions welcome. [Try it online!](http://actually.tryitonline.net/#code=OzcmWXVAXHdgaeKBv-KWkmBN4pWXMmDilZxA4pmAJc6jWWDilZNO&input=NDAzMjA)
```
;7&Yu@\w`iⁿ▒`M╗2`╜@♀%ΣY`╓N
```
**Ungolfing**
```
         Implicit input n.
;        Duplicate n.
7&       n&7 == n%8.
Yu       Logical NOT and increment. If n%8 == 0, return 2. Else, return 1.
@\       Integer divide n by 2 if n%8==0, by 1 otherwise.
          Thus, we have dealt with the special case where p_i == 2 and e_i >= 3.
w        Full prime factorization of n as a list of [prime, exponent] lists.
`...`M   Map the following function over the prime factorization.
  i        Flatten the array, pushing exponent, then prime to the stack.
  ⁿ▒       totient(pow(prime, exponent)).
╗        Save that list of totients in register 0.
2`...`╓  Get the first two values of n where the following function f(n) is truthy.
         Those two numbers will be 0 and our LCM.
  ╜@       Push the list in register 0 and swap with our n.
  ♀%       Get n mod (every number in the list)
  Σ        Sum the modulos. This sum will be 0, if and only if this number is 0 or LCM.
  Y        Logical NOT, so that we only get a truthy if the sum of modulos is 0.
N        Grab the second number, our LCM. Implicit return.
```
[Answer]
# Ruby, ~~101~~ ~~86~~ ~~91~~ 90 bytes
A Ruby port of [my Actually answer](https://codegolf.stackexchange.com/a/93779/47581). Golfing suggestions welcome.
**Edit:** -4 bytes from removing `a` but +9 bytes from fixing a bug where `1` returned `nil`. -1 byte thanks to Cyoce.
```
require'prime'
->n{((n%8<1?n/2:n).prime_division<<[2,1]).map{|x,y|x**~-y*~-x}.reduce :lcm}
```
**Ungolfing**
```
require 'prime'
def carmichael(n)
  if n%8 < 1
    n /= 2
  end
  a = []
  n.prime_division.do each |x,y|
    a << x**(y-1)*(x-1)
  end
  return a.reduce :lcm
end
```
[Answer]
# JavaScript (ES 2016) 149
Python reference implementation ported to JS. Some fancy Pyhton builtin is missing in js, like `gcd` and `pow`, and the array comprehension is not standard in ES 6. This works in Firefox.
```
n=>eval('for(g=(a,b)=>b?g(b,a%b):a,p=(a,b,c)=>eval("for(r=1;b--;)r=r*a%c"),c=[for(_ of Array(i=n))if(g(i--,n)<2)i+1],k=1;c.some(x=>p(x,k,n)-1);)++k')
```
*Less golfed*
```
n=>{
  g=(a,b)=>b?g(b,a%b):a
  p=(a,b,c)=>{ 
    for(r=1;b--;)
      r=r*a%c
    return r
  }
  c=[for(_ of Array(i=n)) if(g(i--,n)<2) i+1]
  for(k=1;c.some(x=>p(x,k,n)-1);)
    ++k
  return k
} 
```
[Answer]
# Java, ~~209~~ ~~207~~ ~~202~~ ~~194~~ 192 bytes
Code (96 bytes):
```
n->{for(int x,k=1,a;;k++){for(a=1,x=0;++x<=n&&a<2;)a=g(x,n)<2?p(x,k,n):1;if(a<2||n<2)return k;}}
```
extra functions (96 bytes):
```
int g(int a,int b){return b<1?a:g(b,a%b);}int p(int n,int p,int m){return p<2?n:n*p(n,p-1,m)%m;}
```
## Testing & ungolfed
```
import java.util.Arrays;
import java.util.function.IntUnaryOperator;
public class Main2 {
  static int g(int a,int b) { // recursive gcd
    return b < 1
        ? a
        : g(b,a%b);
  }
  static int p(int n, int p, int m) { // recursive modpow
    return p < 2
      ? n
      : n * p(n, p - 1, m) % m;
  }
  public static void main(String[] args) {
    IntUnaryOperator f = n -> {
      for(int x,k=1,a;;k++) { // for each k
        for(a=1,x=0;++x<=n&&a<2;) // for each x
          a=g(x,n)<2?p(x,k,n):1; // compute modpow(x,k,n) if g(x,n)
        if(a<2||n<2) // if all modpow(x,k,n)=1. Also check for weird result for n=1.
          return k;
      }
    };
    Arrays.stream(new int[]{1, 2, 3, 10, 35, 101, 530, 3010, 6511, 10000})
        .map(f)
        .forEach(System.out::println);
  }
}
```
## Notes
* the use of `a` being an `int` is shorter than if I had to use a `boolean` to perform my tests.
* Yes, it's shorter to `valueOf` all new `BigInteger` than create a separate function (there are 5, plus the `ONE` constant is a freebie).
* Algorithm is different than @Master\_ex' algorithm, so it's not just a golfed repost. Also, this algorithm is much less efficient as `gcd` is computed again and again for the same values.
## Shaves
1. 209 -> 207 bytes:
	* `if(...)a=...;` -> `a=...?...:1;`
	* `a==1` -> `a<2`
2. 207 -> 202 bytes
	* Got rid of `BigInteger` by golfing `gcd` and `modPow` for `int`.
3. 202 -> 194 bytes
	* looping `modPow` -> recursive
4. 194 -> 192 bytes
	* `==1` -> `<2` (seems to work for all the test cases, don't know for other numbers.)
[Answer]
# Java8 ~~38~~ 19 + ~~287~~ ~~295~~ ~~253~~ ~~248~~ 241 = ~~325~~ ~~333~~ ~~272~~ ~~267~~ 260 bytes
```
BigInteger B(int i){return new BigInteger(""+i);}int c(int...k){int n=k[0];for(k[0]=1;n>1&!java.util.stream.IntStream.range(0,n).filter(i->B(n).gcd(B(i)).equals(B(1))).allMatch(x->B(x).modPow(B(k[0]),B(n)).equals(B(1)));k[0]++);return k[0];}
```
**Imports, 19 bytes**
```
import java.math.*;
```
**Explanation**
It is a straight forward implementation. The co-primes are calculated in the `Set p` and every one's kth power is used to check if it equals 1 modulo n.
I had to use `BigInteger` because of precision issues.
**Usage**
```
public static void main(String[] args) {
    Carmichael c = new Carmichael();
    System.out.println(c.c(3)); // prints 2
}
```
**Ungolfed**
```
// returns the BigInteger representation of the given interger
BigInteger B(int i) {
    return new BigInteger(""+i);
}
// for a given integer it returns the result of the carmichael function again as interger
// so the return value cannot be larger
int c(int... k) {
    int n = k[0];
    // iterate k[0] until for all co-primes this is true: (x^n) mod n == 1, if n==1 skip the loop
    for (k[0]=1;n > 1 && !java.util.stream.IntStream.range(0, n)
                .filter(i -> B(n).gcd(B(i)).equals(B(1)))
                .allMatch(x -> B((int) x).modPow(B(k[0]), B(n)).equals(B(1)));k[0]++);
    return k[0];
}
```
Any suggestions to golf it more are welcome :-)
**Update**
* No elements outside the functions that keep the state
* Followed Olivier Grégoire's advice and saved 1 byte from `B()`
* Removed the `k()` method and `p` (co-primes) Set.
* Removed not required casting to int.
* Added varags and use for instead of while.
[Answer]
# Java, ~~165 163 158 152~~ 143 bytes
```
int l(int n){int k=1,x,a,b,t,d=1;for(;d>0;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;b>0;b=a%b,a=t)t=b;for(t=b=1;b++<=k;t=t*x%n);}return k;}
```
Another port of my [C implementation](https://codegolf.stackexchange.com/a/94142/52904).
[Try it on Ideone](https://ideone.com/tWmaPZ)
[Answer]
# C++, ~~208 200 149 144 140~~ 134 bytes
```
[](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;};
```
A port of my [C implementation](https://codegolf.stackexchange.com/a/94142/52904).
[Try it on Ideone](https://ideone.com/W89903)
[Answer]
## Racket 218 bytes
```
(λ(n)(let((fl #f)(cl(for/list((i n) #:when(coprime? n i))i)))(for/sum((k(range 1 n))#:break fl)(set! fl #t)
(for((i(length cl))#:break(not fl))(when(not(= 1(modulo(expt(list-ref cl i)k)n)))(set! fl #f)))(if fl k 0))))
```
Ungolfed version: 
```
(require math)
(define f
  (λ(n)
    (let ((fl #f)
          (cl (for/list ((i n) #:when (coprime? n i))
                i)))
             (for/sum ((k (range 1 n)) #:break fl)
               (set! fl #t)
               (for ((i (length cl)) #:break (not fl))
                 (when (not (= 1 (modulo (expt (list-ref cl i) k) n)))
                   (set! fl #f)))
               (if fl k 0)))))
```
Testing: 
```
(f 2) 
(f 3)
(f 10)
(f 35)
(f 101)
(f 530)
(f 3010)
(f 6511)
(f 10000)
```
Output: 
```
1
2
4
12
100
52
84
3056
500
```
[Answer]
# C, ~~278 276 272 265 256 243 140 134~~ 125 bytes
```
k,x,a,b,t,d;l(n){for(k=d=1;d;)for(d=x=0;++x<n;d=a<2&t>1?k++:d){for(a=x,b=n;t=b;a=t)b=a%b;for(t=1,b=k;b--;t=t*x%n);}return k;}
```
This uses a slow modular exponentiation algorithm, computes the GCD too often and no longer leaks memory!
Ungolfed:
```
int gcd( int a, int b ) {
  int t;
  while( b ) {
    t = b;
    b = a%b;
    a = t;
  }
  return a;
}
int pw(int a,int b,int c){
  int t=1;
  for( int e=0; e<b; e++ ) {
    t=(t*a)%c;
  }
  return t;
}
int carmichael(int n) {
  int k = 1;
  for( ;; ) {
    int done = 1;
    for( int x=1; x<n; x++ ) {
      if( gcd(x,n)==1 && pw(x,k,n) != 1 ) {
        done = 0;
        k++;
      }
    }
    if( done ) break;
  }
  return k;
}
```
[Try it on Ideone](https://ideone.com/lm9KsO)
[Answer]
**Axiom 129 bytes**
```
c(n)==(r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1);repeat(for a in r repeat(v:=powmod(a,k,n);v~=1=>break);v<=1=>break;k:=k+1);k)
```
less golfed
```
cml(n)==
 r:=[x for x in 1..n|gcd(x,n)=1];(v,k):=(1,1)
 repeat 
   for a in r repeat(v:=powmod(a,k,n);v~=1=>break)
   v<=1=>break
   k:=k+1
 k
```
results
```
(3) -> [i,c(i)] for i in [1,2,3,10,35,101,530,3010,6511,10000]
   Compiling function c with type PositiveInteger -> PositiveInteger
   (3)
   [[1,1], [2,1], [3,2], [10,4], [35,12], [101,100], [530,52], [3010,84],
    [6511,3056], [10000,500]]
                                             Type: Tuple List PositiveInteger
```
]