Carmichael index

DefinitionCarmichael index#✓fully proved

For a natural number \(n\), the Carmichael index \(N(n)\) is the number of integers \(a\) with \(0 \le a \le n - 1\) and \(a^n \equiv a \pmod{n}\).

public def carmichaelIndex (n : ℕ) : ℕ :=
  ((Finset.range n).filter fun a => a ^ n ≡ a [MOD n]).card

Sources

• Atsushi Yamagami and Youichi Inaba, On a Formula and Some Properties of Carmichael Indices, INTEGERS 24 (2024), Article A40, Definition 1.

Used by 4

Used byProduct formula for the Carmichael index · The Carmichael indices of 4 and 66 · The Carmichael index of \(n\) is never \(n - 1\) · The Carmichael index of 1

TheoremThe Carmichael index of 1#✓fully proved

The Carmichael index of \(1\) is \(N(1) = 1\).

public theorem carmichaelIndex_one : carmichaelIndex 1 = 1

Sources

• Yamagami and Inaba, On a Formula and Some Properties of Carmichael Indices, INTEGERS 24 (2024), Article A40, Section 1.

Uses 1

Statement usesCarmichael index

TheoremThe Carmichael indices of 4 and 66#✓fully proved

The Carmichael index satisfies \(N(4) = 2\) and \(N(66) = 24\).

public theorem carmichaelIndex_four_and_sixtySix :
    carmichaelIndex 4 = 2 ∧ carmichaelIndex 66 = 24

Sources

• Yamagami and Inaba, On a Formula and Some Properties of Carmichael Indices, INTEGERS 24 (2024), Article A40, Example 1 (Table 1) and Example 3.

Uses 1

Statement usesCarmichael index

TheoremProduct formula for the Carmichael index#●ready to prove

Let \(n \ge 2\) and, for each prime \(p\) dividing \(n\), let \(p^{e_p}\) be the largest power of \(p\) dividing \(n\). Then the Carmichael index of \(n\) is \(N(n) = \prod_p \bigl(N(n; p^{e_p}) + 1\bigr)\), the product running over the primes \(p\) dividing \(n\), where \(N(n; p^{e_p})\) is the number of units of \(\mathbb{Z}/p^{e_p}\mathbb{Z}\) whose multiplicative order divides \(\gcd(p - 1, n/p^{e_p} - 1)\).

public theorem_wanted carmichaelIndex_eq_prod (n : ℕ) (hn : 2 ≤ n) :
    carmichaelIndex n = ∏ p ∈ n.primeFactors,
      (Nat.card {u : (ZMod (p ^ n.factorization p))ˣ //
        orderOf u ∣ Nat.gcd (p - 1) (n / p ^ n.factorization p - 1)} + 1)

Sources

• Yamagami and Inaba, On a Formula and Some Properties of Carmichael Indices, INTEGERS 24 (2024), Article A40, Theorem 1.

Uses 1

Statement usesCarmichael index

TheoremThe Carmichael index of \(n\) is never \(n - 1\)#●ready to prove

For every positive integer \(n\), the Carmichael index \(N(n)\), the number of integers \(a\) with \(0 \le a \le n - 1\) and \(a^n \equiv a \pmod{n}\), is not equal to \(n - 1\).

public theorem_wanted carmichaelIndex_ne_sub_one (n : ℕ) (hn : 0 < n) :
    carmichaelIndex n ≠ n - 1

Sources

• Yamagami and Inaba, On a Formula and Some Properties of Carmichael Indices, INTEGERS 24 (2024), Article A40, Theorem 2.

Uses 1

Statement usesCarmichael index

3 fully proved2 ready to prove

The dependency explorer needs JavaScript and its graph data.

Download the complete graph data.