The Carmichael function is an important theory in the field of Cryptography, as it forms the proof the basis for RSA encryption. Here we’ll take a look at what the function is exactly, and then how the function will operate for various inputs.
What is the Carmichael Function?
The Carmichael function takes as input one integer
n , and returns a value
m such that every integer coprime to
n , between 1 &
n , when raised to the power
mod n , gives 1. Too wordy?
n = 8
Carmichael Function of n
Written 𝝀(n)> Find all coprimes of 8, between 1 and 8
1, 3, 5, 7> What number, as exponent of each of these, mod n, gives 1?> We need to satisfy:
1ᵐ ≡ 1 (mod 8)
3ᵐ ≡ 1 (mod 8)
5ᵐ ≡ 1 (mod 8)
7ᵐ ≡ 1 (mod 8)> where "a" is the smallest value which satisfies all statements> for n = 8 the answer -> m = 2
1² % 8 = 1
3² % 8 = 1
5² % 8 = 1
7² % 8 = 1𝝀(8) = 2
Hopefully that clears up what the Carmichael Function does. But how does it find
How do we know there is a solution?
First let’s tackle the question of how we can be sure there is a solution,
m , at all. The proof that there is a solution relies on 4 rules of modular arithmetic. These rules were covered in detail and proved in our discussion of them here.
Here we’ll satisfy ourselves by summarising them:
bare coprime, AND
bare coprime, AND
ax ≡ ay (mod n), THEN
x ≡ y (mod n)(the cancellation rule)
bare coprime THEN there is a positive integer,
k, such that
aᵏ≡ 1 (mod n)
aᵏ ≡ 1 (mod n)AND
ris a multiple of
aʳ≡ 1 (mod n)
Rule 3 above proves that for any given coprime to
aᵢ, there is an exponent of
kᵢ, that satisfies
aᵢᵏⁱ ≡ 1 (mod n).
v coprimes, define
k = k₁ x k₂ x ... x kᵥ.
k is a consequently a multiple of all
aᵢᵏ ≡ 1 (mod n) , as proven by rule 4 above.
k is an integer exponent raised to which all coprimes of
n smaller than
n are congruent to 1, satisfying Carmichael’s Function.
k may not be the smallest solution, but it proves that there is always a solution to Carmichael’s Function.
Solving Carmichael’s Function
For non-prime, non-prime power, integers
n are coprime, then we know the following:
xis a coprime of
mn, less than
x % mis coprime to
x % nis coprime to
n. This is because if
xshares no factors with
mnthen it shares no factors with either
xʳ ≡ 1 (mod m)and
xʳ ≡ 1 (mod n)then
xʳ ≡ 1 (mod mn), because:
xʳ ≡ 1 (mod m)
> can be rewritten
xʳ - 1 = mk₁> AND
xʳ ≡ 1 (mod n)
> can be rewritten
xʳ - 1 = nk₂> where k₁ & k₂ are each a positive integer> so
mk₁ = nk₂ = xʳ - 1> lcm means lowest common multiple
mk₁ = nk₂ = lcm(m, n)> therefore
xʳ - 1 = lcm(m, n)> m & n are coprimes
lcm(m, n) = mnxʳ - 1 = mn> proving
xʳ ≡ 1 (mod mn)
Following this second bullet point then, rule 4 tells us that if
xʳ ≡ 1 (mod mn) then we know also that, for any multiple of
xˢ ≡ 1 (mod mn) also. So if
aᶠ ≡ 1 (mod m) works for all
m's coprimes, &
aᵍ ≡ 1 (mod n) for all
n’s coprimes, then we know that
aᶠᵍ ≡ 1 (mod mn) will work for all
So if we can find the solution to Carmichael’s Function for
𝝀(n), then we know that a multiple of these results will work for
𝝀(mn). Therefore the smallest number that will work for
𝝀(mn) will be the lowest common multiple of
𝝀(mn) = lcm(𝝀(m), 𝝀(n))
We now have a formula for finding the Carmichael value for a given number. We factorise the number, and solve for each of those. Unfortunately the formula is recursive: it references itself. We need a base case, a point at which we no longer rely on the outcome of one Carmichael function to resolve another. That base case is prime numbers, because primes do can’t be factorised into this
mn format. So how do we solve Carmichael’s Function for prime numbers?
For prime numbers
In a previous article we looked in depth at Fermat’s Little Theorem. You should take a look at that post to understand exactly why this works. Fermat’s Little Theorem states:
> Where "p" is prime
aᵖ⁻¹ ≡ 1 (mod p)
That tells us enough to apply to Carmichael’s function. If we want to know the Carmichael value of any prime,
p, we know the answer is
p-1 . For example,
𝝀(7) = 6 ,
𝝀(5) = 4etc.
I would encourage you to take a look at our discussion of Fermat’s Little Theorem to understand exactly why this does work.
We’ve covered Carmichael’s function for primes, and for numbers which reduce to their prime factors. We haven’t touched upon numbers which reduce to powers of primes, or powers of primes themselves, and how in their particular cases we would find the Carmichael’s function value.
For Powers of Odd Primes
The unique issue with prime powers is that they are not primes, so we can’t make use of Fermat’s Little Theorem, however they don’t reduce to unique primes either.
In this case we make use of a theory closely related to Fermat’s Little Theorem, called Euler’s Theorem. We covered Euler’s Theorem in the same article as Fermat’s Little Theorem, and you can read about them both here.
Euler’s Theorem states:
> Where U = ϕ(n), because notation support on medium is weak
> And where n is coprime to a
aᵁ ≡ 1 (mod n)
ϕ(n) represents Euler’s Totient function. It returns the number of coprimes to
n, less than
n. You can learn more about exactly how Euler’s Totient Function works in our recent post about it.
We can apply Euler’s Theorem to solve Carmichael’s function for prime powers. Importantly, Euler’s theorem doesn’t require
n to be prime. The theorem tells us that for:
> For 𝝀(9), a prime power
9 = 3²U = ϕ(9) = 6
So for prime powers, Carmichael’s function is the same as Euler’s totient function. In fact, this is true for many numbers. However there are a variety of cases where Euler’s totient differs from Carmichael’s function, where the totient is a “workable” solution, but not the smallest workable solution to Carmichael’s function.
For powers of 2
One example of where the Euler totient & Euler theorem method doesn’t provide the correct result is for powers of 2. For example
ɸ(8)= 4 . For all coprimes to 8,
a⁴ ≡ 1 (mod 8), so it does “work”, but 4 is not the lowest value which “works”, & remember that Carmichael’s Function returns the lowest such value. Indeed,
𝞴(8) = 2 .
2 is a prime number, so its powers suffer the same difficulty we face for odd powers, in that we cannot apply the lowest common multiple method, nor can we apply the method reserved for prime numbers. We need another method then, a fourth way of solving Carmichael’s function, for powers of 2.
Firstly, we can observe that where
p = 2, the formula we used for odd primes,
pᵏ — pᵏ⁻¹ simplifies
pᵏ⁻¹ is always going to be half of
pᵏ⁻¹ x 2 = pᵏ . For
k = 3 ,
pᵏ — pᵏ⁻¹ = 8 — 4 = 4. 4 is still a power of 2.
Unlike powers of odd primes, the result of
pᵏ — pᵏ⁻¹ does not satisfy the form
pʰ for any integer
h . Where
p = 3 &
k = 3,
pᵏ — pᵏ⁻¹ = 27 — 9 = 18. 18 is not a power of 3. We’ve introduced other factors. This is a hint at the difference between odd prime powers and powers of 2, with respect to Carmichael’s function.
All odd numbers are coprimes to powers of 2. All even numbers share the factor
2, so are not coprime. We can represent all odd numbers, that is all coprimes to powers of 2 as:
a = 1 + 2h where
h is any integer ≥ 0.
To find the solution for any power of 2,
𝞴(2ᵏ), we need to satisfy
(1 + 2h)ˣ ≡ 1 (mod 8) where
x is the result of Carmichael’s function. We can show that, for powers of 2 greater than 2, Carmichael’s Function gives
k = 2,
𝞴(8) = 𝞴(2³), we assert that the result,
k — 2, will be
2¹. This means we will need to show that
(1 + 2h)² ≡ 1 (mod 8).
(1 + 2h)²> Expand
4h² + 4h + 1> Factorise
1 + 4h(h + 1)
To prove that
1 + 4h(h + 1) ≡ 1 (mod 8) we need to show that
4h(h + 1) ≡ 0 (mod 8). We can clearly see that it divides by 4, giving
h(h + 1). We can prove that
h(h + 1) divides by 2.
h + 1 = even, and
odd x even = even.
h + 1 = odd, and
even x odd = even.
Therefore we know
4h(h + 1) divides by 8, proving
1 + 4h(h + 1) ≡ 1 (mod 8). We’ve shown that
𝞴(8) = 𝞴(2³) = 2¹, and by induction that
𝞴(2ᵏ) = 2ᵏ⁻² .
However, for a fairly evident reason, this is only true for powers of 2 greater than 2. For
2ᵏ⁻² would give
1/2, a fraction rather than an integer. For
2⁰, which is 1, a result that can be shown incorrect for its coprime 3. For
2² , we use
Solving Carmichael’s Function: An Example
We now have everything we need to solve Carmichael’s Function for a given number. So let’s try it out.
𝞴(135) ?> factorise 135
135 = 27 * 5
𝞴(135) = lcm(𝞴(27), 𝞴(5))> 5 is a prime
𝞴(5) = 4 (5-1)> 27 is a prime power
27 = 3³> So we apply the totient function
𝞴(27) = ϕ(27)> Coprimes of 27
1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19, 20, 22, 23, 25, 26> I count 18 (there is an easier way than counting -> here)
𝞴(27) = ϕ(27) = 18> Work backwards
𝞴(135) = lcm(𝞴(27), 𝞴(5))
lcm(𝞴(27), 𝞴(5)) = lcm(18, 4)lcm(18, 4) = 36𝞴(135) = 36
And that’s all
I think that should cover just about every case. We now have the means to solve Carmichael’s function for any and all numbers!