Mathematics, Number Theory

Congruence of exponents

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:

abab + λ(m) (mod m)

where a is an integer, m is a positive integer, b is an integer such that bemax of m, and where emax 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 emax of m. Let’s say that c = b + λ(m). It follows that cemax of m, since bemax of m and λ(m) ≥ 1. Therefore:

acac + λ(m) (mod m)

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

abab + λ(m) = acac + λ(m) (mod m)

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

ac + λ(m) = ab + λ(m) + λ(m) = ab + (2 * λ(m))

So now we have:

abab + λ(m)ab + (2 * λ(m)) (mod m)

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

abab + λ(m)ab + (2 * λ(m))ab + (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:

abab + (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 bemax of m under the prime factorization m. The basis statement is this:

P(0):

abab + (0 * λ(m)) = ab (mod m)

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

P(k):

abab + (k * λ(m)) (mod m)

where k ≥ 0. The induction step is this:

P(k + 1):

ab + ((k + 1) * λ(m)) = ab + (k * λ(m)) + λ(m)

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

ab + (k * λ(m)) + λ(m) = af + λ(m)

Because bemax of m, k ≥ 0, and λ(m) ≥ 1, we know that femax of m. Therefore:

afaf + λ(m) (mod m)

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

abab + (k * λ(m)) = afaf + λ(m) (mod m)

which completes the proof.

We’ve shown that when n is positive that:

abab + (n * λ(m)) (mod m)

However, if we require the additional stipulation that b + (n * λ(m)) ≥ emax 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:

abab + (n * λ(m)) (mod m)

where bemax of m, and where b + (n * λ(m)) ≥ emax 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:

bc (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:

abac (mod m)

if all of the following are also true:

  • bemax of m
  • cemax of m
  • bc (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.