What is the *congruence of exponents*? The term is, so far, rather vague, but I’d like to use it to refer to something quite specific. Allow me to explain precisely what I mean.

First, let’s take a look at the Carmichael function. The Carmichael function is also known as the least universal exponent function. It represents the period of the modular exponential cycle for a given positive integer *m*. The following congruence relationship describes this cycle, and is a known quality of the Carmichael function:

*a*^{b} ≡ *a*^{b + λ(m)} (mod *m*)

where *a* is an integer, *m* is a positive integer, *b* is an integer such that *b* ≥ *e*_{max} of *m*, and where *e*_{max} of *m* is the largest exponent of *m* under prime factorization.

It’s important to note that *b* can be any integer greater than or equal to *e*_{max} of *m*. Let’s say that *c* = *b* + λ(*m*). It follows that *c* ≥ *e*_{max} of *m*, since *b* ≥ *e*_{max} of *m* and λ(*m*) ≥ 1. Therefore:

*a*^{c} ≡ *a*^{c + λ(m)} (mod *m*)

But remember that we defined *c* = *b* + λ(*m*). We can combine the previous two congruences:

*a*^{b} ≡ *a*^{b + λ(m)} = *a*^{c} ≡ *a*^{c + λ(m)} (mod *m*)

Since *c* = *b* + λ(*m*), we can rewrite the last term as:

*a*^{c + λ(m)} = *a*^{b + λ(m) + λ(m)} = *a*^{b + (2 * λ(m))}

So now we have:

*a*^{b} ≡ *a*^{b + λ(m)} ≡ *a*^{b + (2 * λ(m))} (mod *m*)

If we define *d* = *b* + (2 * λ(*m*)), we can follow the same process to show that:

*a*^{b} ≡ *a*^{b + λ(m)} ≡ *a*^{b + (2 * λ(m))} ≡ *a*^{b + (3 * λ(m))} (mod *m*)

We can continue by this method indefinitely an arbitrary number of times. In this fashion, I’ll show by mathematical induction that the following is therefore true:

*a*^{b} ≡ *a*^{b + (n * λ(m))} (mod *m*)

where *a* is an integer, *n* is a non-negative integer, *m* is a positive integer, and *b* is an integer where *b* ≥ *e*_{max} of *m* under the prime factorization *m*. The basis statement is this:

P(0):

*a*^{b} ≡ *a*^{b + (0 * λ(m))} = *a*^{b} (mod *m*)

which shows that the basis statement is true. The induction hypothesis is this:

P(*k*):

*a*^{b} ≡ *a*^{b + (k * λ(m))} (mod *m*)

where *k* ≥ 0. The induction step is this:

P(*k* + 1):

*a*^{b + ((k + 1) * λ(m))} = *a*^{b + (k * λ(m)) + λ(m)}

If we substitute *f* for *b* + (*k* * λ(*m*)), we get:

*a*^{b + (k * λ(m)) + λ(m)} = *a*^{f + λ(m)}

Because *b* ≥ *e*_{max} of *m*, *k* ≥ 0, and λ(*m*) ≥ 1, we know that *f* ≥ *e*_{max} of *m*. Therefore:

*a*^{f} ≡ *a*^{f + λ(m)} (mod *m*)

We can make the same substitution in the induction hypothesis statement. Therefore, by the induction hypothesis:

*a*^{b} ≡ *a*^{b + (k * λ(m))} = *a*^{f} ≡ *a*^{f + λ(m)} (mod *m*)

which completes the proof.

We’ve shown that when *n* is positive that:

*a*^{b} ≡ *a*^{b + (n * λ(m))} (mod *m*)

However, if we require the additional stipulation that *b* + (*n* * λ(*m*)) ≥ *e*_{max} of *m*, then *n* can be any integer. We can therefore say that for the given integers, *a*, *b*, and *n*, and the positive integer *m*:

*a*^{b} ≡ *a*^{b + (n * λ(m))} (mod *m*)

where *b* ≥ *e*_{max} of *m*, and where *b* + (*n* * λ(*m*)) ≥ *e*_{max} of *m*.

If we define another integer, *c*, such that *c* = *b* + (*n* * λ(*m*)), what we’ve done is establish a modular congruence relationship between *b* and *c*, mod λ(*m*). We can show this relationship like so:

*b* ≡ *c* (mod λ(*m*))

We can now restate the earlier congruence in terms of *b* and *c*. Given the integers *a*, *b*, and *c*, and the positive integer, *m*:

*a*^{b} ≡ *a*^{c} (mod *m*)

if all of the following are also true:

*b*≥*e*_{max}of*m**c*≥*e*_{max}of*m**b*≡*c*(mod λ(*m*))

This final congruence and constraints are what I will call the *congruence of exponents*.

In my next post, I’ll use the congruence of exponents to show something interesting about recursive modular exponentiation.