Java, 165 163 158 152 143 131 bytes

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=1;b++<k;t=t*x%n);}return k;}

Another port of my C implementation.

Try it online!

C, 278 276 272 265 256 243 140 134 125 120 bytes

k,x,a,b,t,d;l(n){for(k=d=1;d;)for(d=x=0;a=++x%n;d=t>1>=a?k++:d){for(b=n;t=b;a=t)b=a%b;for(t=1;b++<k;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 online!

C++, 208 200 149 144 140 134 129 bytes

[](int n){int k=1,x,a,b,t,d=1;for(;d;)for(d=x=0;a=++x%n;d=t>1>=a?k++:d){for(b=n;t=b;a=t)b=a%b;for(t=1;b++<k;t=t*x%n);}return k;};

A port of my C implementation.

Try it online!

APL(NARS), 28 chars

∧/{(13π⍵)÷1+0=8∣⍵}¨×/¨⊂⍨1,π⎕

13π is here the builtin totient function, π find factors of input. It would use the totient function for build lambda as other answers. It add 1 as a factor of input number, it would than apply {(13π⍵)÷1+0=8∣⍵} in the prime factors pow to their multiplicity, of number of input. It seems ⊂⍨ enclose 1 too, so ok.

Test:

  ∧/{(13π⍵)÷1+0=8∣⍵}¨×/¨⊂⍨1,π⎕
⎕:
  10000
500
  ∧/{(13π⍵)÷1+0=8∣⍵}¨×/¨⊂⍨1,π⎕
⎕:
  6511
3056

slower of above this below, traslate of one other answer

APL(NARS), 160 chars

r←l w;b;e;n
(b e n)←w⋄r←1
→3×⍳0=2∣e⋄r←n∣r×b
b←n∣b×b⋄→2×⍳0<e←⌊e÷2

r←c w;t;a;i;v;s
s←≢t←t/⍨1=w∨t←⍳w⋄v←r←i←1
→3×⍳i>s⋄v←l t[i],r,w⋄i+←1⋄→2×⍳v=1
→0×⍳v≤1⋄r+←1⋄i←1⋄→2

//12+14+18+21+16+25+34+20 where l is ltor, and c is the function of the question

  c¨1 2 3 10 35 101 530 6511 10000
1 1 2 4 12 100 52 3056 500 

SAKO, 297 bytes

PODPROGRAM:F(N)
CALKOWITE:N,I,J,*T,K
BLOK(9):T
GDYN>2:0,INACZEJ4
4)K=1
SKOCZDO9
0)J=0
*)T(J)=I
J=J+0*(G(N,I)-1)
POWTORZ:I=2(1)N-1
K=1
*1)GDYMOD(T(I)*K,N)=1:2,INACZEJ3
2)POWTORZ:I=0(1)J-1
9)F()=K
WROC
3)K=K+1
SKOCZDO1
PODPROGRAM:G(A,B)
CALKOWITE:A,B
GDYB>0:1,INACZEJ2
1)A=G(B,MOD(A,B))
2)G()=A
WROC

Due to a lack of terrifyingly long answers, I decided to post mine.

Explanation:

1. We take an integer value as an argument N.
2. We get all coprimes of N and put it in the list T.
3. We check for every T(I) if MOD(T(I)*K, N) = 1 and if yes we print K. Else we increase K by one.

There is probably a shorter way to do this; however, I do not know it.

Templates Considered Harmful, 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).

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!

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 a^k ≡ 1 (mod n) – i.e., such that n | a^k - 1 – for all a that are coprime to n.

f(n) is the smallest k such that a^2k+1 ≡ a^k+1 (mod n) – i.e., such that n | a^k+1(a^k - 1) – for all a.

λ(n) ≤ f(n)

Fix n and let a be coprime to n.

By the definition of f, n | a^f(n)+1(a^f(n) - 1). Since a and n do not have a common prime factor, neither do a^f(n)+1 and n, which implies that n | a^f(n) - 1.

Since λ(n) is the smallest integer k such that n | a^k - 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), 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 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 a^k+1(a^k - 1) % n for all values of a in that range, which is 0 if and only if n | a^k+1(a^k - 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).

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

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!

;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.

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

Ruby, 101 86 91 90 bytes

A Ruby port of my Actually answer. 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

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

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.

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.)

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.

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₁^k₁ p₂^k₂ ⋯ p_i^k_i, λ(n) = LCM[ λ(p₁^k₁) λ(p₂^k₂) ⋯ λ(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

Ruby, 59 56 bytes

->x{a=1..x
a.detect{|k|a.all?{|y|x.gcd(y)>1||y**k%x<2}}}