Published in

curiositypapers

# Carmichael Function: A Complete Guide — Number theory

Written for publication on samxsmith.com

The Carmichael function is an important part of number theory. It forms the basis of RSA encryption. We’ll take a look at what the function is exactly, and how we can solve it for various categories of input.

Note

• `LCM()` is the lowest common multiple of the provided integers.

# What is the Carmichael Function?

It takes as input an integer, `n`. The function is written as a Lambda: `𝝀(n)`.

It’s output, `m`, is the lowest value such that every integer coprime to `n`, between `1` & `n`, when raised to the power `m`, and `mod n`, gives `1`. For example:

`n = 8𝝀(8) = ?> Find all coprimes of n, between 1 & n1, 3, 5, 7> We need to find the smallest value of 'm' which satisfies...1ᵐ ≡ 1 (mod 8)3ᵐ ≡ 1 (mod 8)5ᵐ ≡ 1 (mod 8)7ᵐ ≡ 1 (mod 8)> for n = 8, m = 21² % 8 = 13² % 8 = 15² % 8 = 17² % 8 = 1𝝀(8) = 2`

Note that the value `4` would also work. However the Carmichael Function returns the lowest working value.

We know what the Carmichael Function does. But how do we find `m`?

# How do we know that there is a solution?

To prove that there is a solution, we’ll be applying the rules we looked at in ‘Modular Arithmetic: 4 Important Truths’. If you haven’t covered those, go and read that first. It’s short and will give you everything you need to continue with this.

If you’ve forgotten them already, we can summarise them:

1. If `a` & `b` are coprime, AND `a|bc`, THEN `a|c`
2. If `a` & `b` are coprime, AND `ax ≡ ay (mod n)`, THEN `x ≡ y (mod n)`
3. If `a` & `b` are coprime, THEN there is a positive integer, `k` such that `aᵏ≡ 1 (mod n)`
4. If `aᵏ ≡ 1 (mod n)` AND `r` is a multiple of `k` THEN `aʳ≡ 1 (mod n)`

Rule #3 proves that for any two coprimes, `a` & `n`, there is a power `k` such that `aᵏ % n = 1`.

If `n` has `v` coprimes between 1 & `n`, then each coprime, `aᵢ`, must have some power, `kᵢ`, so that `aᵢᵏⁱ ≡ 1 (mod n)`.

Let `k` be the product of all `kᵢ` values: `k = k₁ x k₂ x ... x kᵥ`. `k` is consequently the product of each `kᵢ` value.

`> We know thataᵢᵏⁱ ≡ 1 (mod n)> Rule #4 proves this is true for any multiple of `kᵢ`> We know `k` is a multiple of `kᵢ`aᵢᵏ ≡ 1 (mod n)`

So for all coprimes of `n`, we know there will be some value, `k` that satisfies Carmichael’s Function.

# Solving Carmichael’s Function

## Solving for non-prime, non-prime power, integers

Let `x` be a coprime to the product of `m` & `n`, `mn`. `x < mn`.

We know that `x % n` is also coprime to `n`, and that `x % m` is coprime to `m`. `x` shares no factors with `mn`, so we know it shares no factors with `m` or `n` individually.

Let `r` be an integer which satisfies the following expressions:

`xʳ ≡ 1 (mod m)xʳ ≡ 1 (mod n)`

Given this, we can prove also that `xʳ ≡ 1 (mod mn)`.

`xʳ ≡ 1 (mod m)xʳ ≡ 1 (mod n)> where k₁ & k₂ are positive integers> rearrangexʳ - 1 = mk₁xʳ - 1 = nk₂> thereforemk₁ = nk₂ = xʳ - 1> we've found a common multiplemk₁ = nk₂ = LCM(m, n)xʳ - 1 = LCM(m, n)> because m & n are coprimesLCM(m, n) = mnxʳ - 1 = mn> provingxʳ ≡ 1 (mod mn)`

Now, you may remember that Rule #4 we mentioned above tells us that if `xʳ ≡ 1 (mod mn)`, then the same is true for any multiple of `r`. For example, picking any integer `s`, we know `xʳˢ ≡ 1 (mod mn)`.

We can use this to combine solutions to Carmichael’s Function. If `aᶠ ≡ 1 (mod m)` and `aᵍ ≡ 1 (mod n)` for all of their respective coprimes, then we know that `aᶠᵍ ≡ 1 (mod mn)` is true for all coprimes of `mn`. So if `𝝀(m) = f` & `𝝀(n) = g` then `𝝀(mn) = LCM(𝝀(m), 𝝀(n))`. We use lowest common multiple because we are looking for the lowest working value.

This gives us a recursive formula for finding the Carmichael value. To find the value for a number, first find the value of any two coprime factors, then take the lowest common multiple of those values. As with all recursive functions we need a base case. In this instance, our base is prime numbers, which have no factors besides themselves and 1.

## Solving for prime numbers

Fermat’s Little Theorem states:

`> Where `p` is primeaᵖ⁻¹ ≡ 1 (mod p)`

If you want to know why this is the case, you can take a deeper look at Fermat’s Little Theorem in this post.

The theorem tells us that if we want to satisfy the Carmichael function for any prime `p`, the correct value is `p - 1`. That simple.

This means we can solve the function for primes and for integers which reduce to their prime factors. There are two special cases we still need to look at though.

I would strongly encourage you to take a look at the discussion we had on Fermat’s Little Theorem before you accept the outcome we’ve found reached here. Understanding is a battle to convince yourself of some claim. You cannot understand the Carmichael Function without being sure of the claim that Fermat’s Theorem makes.

## Solving for powers of odd primes

Powers of odd primes fall into a special category. This means we cannot use either method we’ve seen so far for solving Carmichael’s function. They are not themselves primes, yet they do not have coprime pairs of factors either. This prevents us from using the `𝝀(mn) = LCM(𝝀(m), 𝝀(n))` trick.

For example `3² = 9`. 9 has only 2 factor pairs. We cannot use the pair `9 x 1` because it includes 9 itself, creating an infinite loop: `𝝀(9) = LCM(𝝀(9), 𝝀(1))`. The other pair, `3 x 3`, are evidently not coprime. The formula `𝝀(mn) = LCM(𝝀(m), 𝝀(n))` requires `m` & `n` to be coprime, as shown in the proof.

To solve the function in this case, we need to use Euler’s Theorem. Euler’s Theorem is closely related to Fermat’s Little Theorem, and you can learn about both here. We’ll also be using Euler’s Totient Function. If you aren’t familiar with Euler’s Totient Function, we covered that here. As I said earlier, I encourage you to learn & understand those theorems in order to get a full appreciation of this one.

Phi (`𝛗(n)`) is used to represent Euler’s Totient function. It returns the number of `n`’s coprimes less than `n`. Euler’s Theorem says:

`> When 'n' & 'a' are coprimeaᵠ⁽ⁿ⁾ ≡ 1 (mod n)`

We can use Euler’s Theorem to solve Carmichael’s function for prime powers.

`> For 9, a prime power𝛗(9) = 6> coprimes of 92, 4, 5, 7, 82⁶ % 9 = 14⁶ % 9 = 15⁶ % 9 = 17⁶ % 9 = 18⁶ % 9 = 1𝝀(9) = 𝛗(9) = 6`

So for prime powers, Carmichael’s Function is the same as Euler’s Totient Function. In fact this is true for many other types of number too. However, in many cases Euler’s Totient Function offers a workable, but not smallest, solution. For prime powers though, it can be relied upon to solve Carmichael’s Function.

## Solving for powers of 2

Powers of 2 represent the final class of number for which we need to solve Carmichael’s function. None of the methods seen so far will suit. Powers of 2 have no coprime factor pairs, they are not themselves prime, and Euler’s Totient does not apply. Powers of odd primes use Euler’s Totient to find the value for Carmichael’s Function. The totient 8, `𝛗(8) = 4`. This is a workable, but not smallest, solution to Carmichael’s Function. In fact, `𝞴(8) = 2`.

All odd numbers are coprime to 2 & its powers. All odd numbers fit the formula `a = 1 + 2h`, where the variable `h` can be any integer. The Carmichael Function we need to solve for any power of 2 would be: `(1 + 2h)ᵐ ≡ 1 (mod 2ᵏ)`. `m` is the number we’re looking to find. `k` can be any power of 2.

It can be proven that for any power of 2, `2ᵏ`, the Carmichael Function solution is `2ᵏ⁻²` Let’s take the example of `k = 3`.

`k = 32ᵏ = 2³ = 8k - 2 = 1m = 2ᵏ⁻² = 2¹ = 2> Using (1 + 2h)ᵐ ≡ 1 (mod 2ᵏ)(1 + 2h)² ≡ 1 (mod 8)4h² + 4h + 1 ≡ 1 (mod 8)> factorise and rearrange1 + 4h(h + 1) ≡ 1 (mod 8)`

We know that `4h(h + 1)` will divide by 4.

We also know that `h(h + 1)` will divide by 2, because:

• If `h` is odd, `h + 1 = even`, and `odd x even = even`.
• If `h` is even, `h + 1 = odd`, and `even x odd = even` .

Therefore we know `4h(h + 1)` will divide by 8.

So we know that `1 + 4h(h + 1) % 8 = 1`.

This demonstrates that `𝞴(8) = 𝞴(2³) = 2¹` and by induction that `𝞴(2ᵏ) = 2ᵏ⁻²`.

BUT only where `k > 2`. `2¹ = 2`, `2ᵏ⁻² = 2⁻¹ = 1/2`, not an integer. For `2² = 4`, `2ᵏ⁻² = 2⁰ = 1` it doesn’t work either. For example, `3¹ % 4 != 1`. Where `k < 3`, the smallest solution to Carmichael’s Function is `2ᵏ⁻¹` for powers of `2`.

# Solving Carmichael’s Function: An Example

We’ve seen how to solve Carmichael’s for all classes of numbers. Now let’s have a go at an example problem:

`𝞴(135) ?> factorise 135135 = 27 * 5𝞴(135) = lcm(𝞴(27), 𝞴(5))> 5 is a prime𝞴(5) = 4 (5-1)> 27 is a prime power27 = 3³> So we apply the totient function𝞴(27) = 𝛗(27)> Coprimes of 271, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26> I count 18`

You don’t need to count these manually. You can learn an easier method for finding total coprimes -> here.

`𝞴(27) = 𝛗(27) = 18𝞴(5) = 4> Now working back up𝞴(135) = lcm(𝞴(27), 𝞴(5))lcm(𝞴(27), 𝞴(5)) = lcm(18, 4)lcm(18, 4) = 36𝞴(135) = 36`

# That’s Everything

That should just about cover the Carmichael Function. We’ve seen how to solve it in any scenario. The Carmichael Function is used often in cryptography, and pulls together a number of other ideas in Number Theory. You’ll see us put it to work soon when we take a deep dive into RSA encryption.

--

--

--

## More from curiositypapers

How the world works. Science, maths & technology applied.

## Sam x Smith

A Software Engineer working in London