In my last post, I described a concept which I called the *congruence of exponents*. The conclusion of that discussion was that the following congruence is true:

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

where *a*, *b*, and *c* are integers, and *m* is a positive integer, if all of the following statements are also true:

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

where λ is the Carmichael function, and *e*_{max} of *m* is the maximum exponent of *m* under prime factorization.

Next I’ll show how this congruence of exponents can be used to prove the following congruence:

*a*^{(2φ(φ(m)))} ≡ *a*^{(22φ(φ(m)))} (mod *m*)

where *a* is any integer, *m* is any positive integer, and φ is Euler’s totient function.

There’s a lot of letters and numbers and symbols in there. To summarize what this congruence says, *a* raised to the power of 2, raised to the power of φ(φ(*m*)), is congruent to *a* raised to the power of 2, raised to the power of twice φ(φ(*m*)), mod *m*.

Intuitively, if we start with *a*, and repeatedly square and reduce the result to a member of the least residue system, mod *m*, there are a finite number of possible such residues. We can perform this quadratic residue process indefinitely, therefore, the sequence of residues generated in this way must eventually form a cycle.

The surprising result of the congruence above to be proven here is that the length of that cycle always divides φ(φ(*m*)). This is certainly not intuitive!

#### emax(*m*)

For convenience of notation for the following discussion, I’ll define a shorthand notation for *e*_{max} of *m*. Throughout the discussion, I’ll use the following function:

emax(*m*) = *e*_{max} of *m*

where *e*_{max} of *m* is the largest exponent of the integer *m* under prime factorization. More specifically, emax(*m*) is the max function applied to the sequence of exponents in the prime factorization of *m*.

#### Euler’s totient function

Now let’s take a look at the definition of Euler’s totient function, denoted φ. Formally, Euler’s totient function, for a positive integer, *m*, counts the numbers between 1 and *m*, inclusive, which are relatively prime to *m*. For a power of a prime, *p*^{e}, Euler’s totient can be calculated like so:

φ(*p*^{e}) = *p*^{e} – *p*^{e – 1}

Additionally, Euler’s totient function can be computed through multiplication like so:

φ(*p*^{e}) = *p*^{e} * ((*p* – 1) / *p*) = *p*^{e} * (1 / *p*) * (*p* – 1) = *p*^{e – 1} * (*p* – 1)

Euler’s totient function is also multiplicative which means that for any two relatively prime integers, *p* and *q*:

φ(*p**q*) = φ(*p*)φ(*q*)

Therefore, if a positive integer, *m*, has *n* prime factors, {*p*_{1}, *p*_{2}, …, *p*_{n}}, with corresponding exponents, [*e*_{1}, *e*_{2}, …, *e*_{n}], such that:

*m* = *p*_{1}^{e1} * *p*_{2}^{e2} * … * *p*_{n}^{en}

then in the general case, Euler’s totient function can be computed from the prime factorization of *m* like so:

φ(*m*) = φ(*p*_{1}^{e1}) * φ(*p*_{2}^{e2}) * … * φ(*p*_{n}^{en})

= *p*_{1}^{e1 – 1} * (*p*_{1} – 1) * *p*_{2}^{e2 – 1} * (*p*_{2} – 1) * … * *p*_{n}^{en – 1} * (*p*_{n} – 1)

Note that the value of Euler’s totient function cannot be less than 1. More specifically, its value is limited thus:

1 ≤ φ(*m*) ≤ *m*

#### Carmichael function

Now let’s take a look at the definition of the Carmichael function, denoted λ. For powers of odd primes and for 2 and 4, the Carmichael function has the value of Euler’s totient function. For powers of 2 greater than or equal to 8, the Carmichael function has half the value of Euler’s totient function. For composite numbers, the Carmichael function has the value of the least common multiple of the Carmichael function applied to each of the prime factors. If a positive integer, *m*, has *n* prime factors, {*p*_{1}, *p*_{2}, …, *p*_{n}}, with corresponding exponents, [*e*_{1}, *e*_{2}, …, *e*_{n}], such that:

*m* = *p*_{1}^{e1} * *p*_{2}^{e2} * … * *p*_{n}^{en}

then in the general case, the Carmichael function can be computed from the prime factorization of *m* like so:

λ(*m*) = lcm(λ(*p*_{1}^{e1}), λ(*p*_{2}^{e2}), …, λ(*p*_{n}^{en}))

There are two important things to note about the divisibility of the Carmichael function. First for a given positive integer, *n*, λ(*n*) divides φ(*n*). Second, given two integers, *a* and *b*, if *a* divides *b* then λ(*a*) divides λ(*b*). We’ll use both of these divisibility properties in the proof of the above congruence.

### Intermediate results

To prove the above congruence, we’ll need some intermediate results. If you prefer, you may go straight to the proof and refer back to the intermediate results, to which I have provided links where they are used.

**Result 1**

*x*^{2} > *x* + 1, where *x* is an integer and *x* ≥ 2

We will use mathematical induction to show this. The basis case is this:

P(2):

2^{2} = 4 > 2 + 1 = 3

The induction hypothesis is this:

P(*k*):

*k*^{2} > *k* + 1, where *k* is an integer and *k* ≥ 2

Now the induction step:

P(*k* + 1):

(*k* + 1)^{2} = *k*^{2} + 2*k* + 1

By the induction hypothesis:

*k*^{2} + 2*k* + 1 > *k* + 1 + 2*k* + 1 = 2*k* + *k* + 2

Because 2*k* > 0, since *k* ≥ 2:

2*k* + *k* + 2 > *k* + 2 = (*k* + 1) + 1

**Result 1.5**

*x*^{n} ≥ 1, where *x* is an integer and *x* ≥ 1, and where *n* is an integer and *n* ≥ 0

We will show this by mathematical induction using the exponent, *n*, as the induction variable. The basis statement is this:

P(0):

*x*^{0} = 1

The induction hypothesis is this:

P(*k*):

*x*^{k} ≥ 1, where *k* is an integer and *k* ≥ 0

The induction step is this:

P(*k* + 1):

*x*^{k + 1} = *x* * *x*^{k}

Because *x* ≥ 1, and by the induction hypothesis, *x*^{k} ≥ 1, it follows that:

*x* * *x*^{k} ≥ 1

**Result 2**

*x*^{n} ≥ *x*^{m}, where *x* is an integer and *x* ≥ 1, and where *n* and *m* are integers and *n* ≥ *m* ≥ 0

By result 1.5, since *n* – *m* is an integer and *n* – *m* ≥ 0, given that *n* and *m* are integers and *n* ≥ *m*, and since *x* is an integer and *x* ≥ 1, it follows that:

*x*^{n – m} ≥ 1

By result 1.5, since *m* is an integer and *m* ≥ 0 and *x* is an integer and *x* ≥ 1, it follows that *x*^{m} ≥ 1 > 0. We can, therefore, multiply both sides of the inequality above by *x*^{m} without reversing the inequality. Therefore:

*x*^{n – m} * *x*^{m} ≥ 1 * *x*^{m}

This simplifies to:

*x*^{n} ≥ *x*^{m}

**Result 3**

*x*^{n} ≥ *y*^{n}, where *x* and *y* are integers and *x* ≥ *y* ≥ 1, and where *n* is an integer and *n* ≥ 0

If *n* = 0, *x*^{0} = 1 = *y*^{0}.

If *n* = 1, *x*^{1} = *x* ≥ *y* = *y*^{1}, which matches the precondition of *x* ≥ *y*.

If *x* = *y*, *x*^{n} = *y*^{n}.

The proof for cases when *n* ≥ 2 and when *x* > *y* will rely on the binomial expansion of (*y* + (*x* – *y*))^{n}. Because *x* > *y*, we know that *x* – *y* > 0 and we can rewrite *x* in terms of *y* and the difference between *x* and *y* as *x* = *y* + (*x* – *y*). Thus, we will solve this inequality:

*x*^{n} = (*y* + (*x* – *y*))^{n} ≥ *y*^{n}

By the binomial theorem:

(y + (x - y))^n = \sum_{k=0}^n\binom{n}{k}y^{n-k}(x - y)^k

When n is greater than 1, we can pull out the first and last terms from the summation:

= \binom{n}{0}y^{n-0}(x - y)^{n-n} + \binom{n}{n}y^{n-n}(x - y)^{n-0} + \sum_{k=1}^{n-1}\binom{n}{k}y^{n-k}(x - y)^k

Note that \binom{n}{0} = \binom{n}{n} = 1, so we can simplify this last sequence of terms like so:

= 1*y^n*(x - y)^0 + 1*y^0*(x - y)^n + \sum_{k=1}^{n-1}\binom{n}{k}y^{n-k}(x - y)^k

= y^n*1 + 1*(x - y)^n + \sum_{k=1}^{n-1}\binom{n}{k}y^{n-k}(x - y)^k

= y^n + (x - y)^n + \sum_{k=1}^{n-1}\binom{n}{k}y^{n-k}(x - y)^k

Note that the binomial coefficient represented by \binom{n}{k} is a positive integer. By result 1.5, *y*^{n – k} ≥ 1, since *y* is an integer and *y* ≥ 1 and *n* – *k* ≥ 1, given that *n* and *k* are integers and *n* – 1 ≥ *k*. Also, by result 1.5, (*x* – *y*)^{k} ≥ 1, since *k* is an integer and *k* ≥ 1, and since *x* – *y* is an integer and *x* – *y* ≥ 1, given that *x* and *y* are integers and *x* > *y*. Therefore, each of the terms summed by \sum_{k=1}^{n-1}\binom{n}{k}y^{n-k}(x - y)^k is positive and therefore their sum is positive. Therefore:

y^n + (x - y)^n + \sum_{k=1}^{n-1}\binom{n}{k}y^{n-k}(x - y)^k > y^n + (x - y)^n

By result 1.5, (*x* – *y*)^{n} ≥ 1, since *x* – *y* is an integer and *x* – *y* ≥ 1, given that *x* and *y* are integers and *x* > *y*, and since *n* is an integer and *n* ≥ 2. Therefore:

*x*^{n} > *y*^{n} + (*x* – *y*)^{n} > *y*^{n}

**Result 3.5**

*x*^{n} is an integer, where *x* is an integer, and where *n* is an integer and *n* ≥ 0, and where *x* ≠ 0 if *n* = 0

If *n* = 0, because any non-zero integer raised to the power of 0 is 1, and given that *x* is an integer and that *x* ≠ 0 when *n* = 0, *x*^{n} = *x*^{0} = 1, which is an integer.

If *n* ≥ 1, we will show the result by mathematical induction using the exponent, *n*, as the induction variable. The basis statement is this:

P(1):

*x*^{1} = *x*

It was given that *x* is an integer, therefore *x*^{1} is an integer.

The induction hypothesis is this:

P(*k*):

*x*^{k} is an integer, where *k* is an integer and *k* ≥ 1

The induction step is this:

P(*k* + 1):

*x*^{k + 1} = *x* * *x*^{k}

It was given that *x* is an integer and by the induction hypothesis, *x*^{k} is an integer. Therefore, *x* * *x*^{k} is an integer because it is the product of two integers.

**Result 4**

2^{(pe – 2)} ≥ *e*, where *p* is a prime integer, and where *e* is an integer and *e* ≥ 2

By result 3, since *p* is a prime integer and therefore *p* ≥ 2 > 1, and since *e* – 2 is an integer and *e* – 2 ≥ 0, given that *e* is an integer and *e* ≥ 2, it follows that:

*p*^{e – 2} ≥ 2^{e – 2}

Given that *p* is a prime integer, it follows that *p* ≥ 2. Because *p* ≥ 2 > 1 and since *e* – 2 is an integer and *e* – 2 ≥ 0, given that *e* is an integer and *e* ≥ 2, it follows from result 3.5 that *p*^{e – 2} is an integer and 2^{e – 2} is an integer, and it follows from result 1.5 that *p*^{e – 2} ≥ 1 and that 2^{e – 2} ≥ 1. Therefore, by result 2, it follows that:

2^{(pe – 2)} ≥ 2^{(2e – 2)}

We will show that the following is true by mathematical induction:

2^{(2e – 2)} ≥ *e*

The basis statement is this:

P(2):

2^{(22 – 2)} = 2^{(20)} = 2^{1} = 2

The induction hypothesis is this:

P(*k*):

2^{(2k – 2)} ≥ *k*, where *k* is an integer and *k* ≥ 2

Now induction step:

P(*k* + 1):

2^{(2(k + 1) – 2)} = 2^{(2k – 1)}

Because 2^{k – 1} = 2*2^{k – 2}, it follows that:

2^{(2k – 1)} = 2^{(2*2k – 2)}

By the exponent rule:

2^{(2*2k – 2)} = (2^{(2k – 2)})^{2}

Because *k* is an integer and *k* ≥ 2, it follows that *k* – 2 is an integer and *k* – 2 ≥ 0. Therefore, by result 1.5, 2^{k – 2} ≥ 1 and by result 3.5, 2^{k – 2} is an integer. Therefore, also by result 3.5, 2^{(2k – 2)} is an integer. By the induction hypothesis, 2^{(2k – 2)} ≥ *k* and *k* ≥ 2. Therefore, by result 3, it follows that:

(2^{(2k – 2)})^{2} ≥ *k*^{2}

By result 1, since *k* is an integer and *k* ≥ 2:

*k*^{2} ≥ *k* + 1

**Result 5**

If an integer, *a*, divides an integer, *b*, and *b* divides an integer, *c*, *a* divides *c*.

If *a* divides *b* then *b* = *a***d*, where *d* is another integer. If *b* divides *c* then *c* = *b***e*, where *e* is another integer. We can then form the following equality by combining the two equalities:

*c* = *a***d***e*

We can divide both sides of the above equality by *a* which gives us:

*c* / *a* = (*a***d***e*) / *a* = *d***e*

The product *d***e* must be an integer because *d* and *e* are both integers. Therefore, *c* / *a* must also be an integer, which means that *a* divides *c*.

**Result 6**

λ(λ(*m*)) divides φ(φ(*m*)), where λ is the Carmichael function and φ is Euler’s totient function and *m* is an integer and *m* ≥ 1

This is quite easy to show based on the two facts about the divisibility of the Carmichael function stated earlier.

Because λ(*n*) divides φ(*n*) for a positive integer, *n*, and because φ(*m*) is an integer and φ(*m*) ≥ 1, given that *m* is an integer and *m* ≥ 1, it follows that:

λ(φ(*m*)) divides φ(φ(*m*))

which is clear if we substitute *n* for φ(*m*) in the above statement.

Because λ(*a*) divides λ(*b*) for positive integers, *a* and *b*, where *a* divides *b* and because λ(*n*) divides φ(*n*) for a given positive integer, *n*, and because λ(*m*) and φ(*m*) are integers and λ(*m*) ≥ 1 and φ(*m*) ≥ 1, given that *m* is an integer and *m* ≥ 1, it follows that:

λ(λ(*m*)) divides λ(φ(*m*))

which is clear by substituting *a* for λ(*m*) and *b* for φ(*m*) in the above statement.

Because λ(λ(*m*)) divides λ(φ(*m*)) and λ(φ(*m*)) divides φ(φ(*m*)), by result 5, λ(λ(*m*)) also divides φ(φ(*m*)).

**Result 7**

*x*^{n – 1} ≥ *n*, where *x* is an integer and *x* ≥ 2, and *n* is an integer and *n* ≥ 1

Given that *x* is an integer and *x* ≥ 2, and since *n* – 1 is an integer and *n* – 1 ≥ 0, given that *n* is an integer and *n* ≥ 1, by result 3, it follows that:

*x*^{n – 1} ≥ 2^{n – 1}

We will show that this is true by mathematical induction using *n* as the induction variable:

The basis case is this:

P(1):

2^{1 – 1} = 2^{0} = 1

The induction hypothesis is this:

P(*k*):

2^{k – 1} ≥ *k*, where *k* is an integer and *k* ≥ 1

Now the induction step:

P(*k* + 1):

2^{(k + 1) – 1} = 2^{k} = 2*2^{k – 1}

By the induction hypothesis, since *k* ≥ 1:

2*2^{k – 1} ≥ 2*k* = *k* + *k*

Because k ≥ 1:

*k* + *k* ≥ *k* + 1

We’re now ready to prove:

*a*^{(2φ(φ(m)))} ≡ *a*^{(22φ(φ(m)))} (mod *m*)

where *a* is an integer, *m* is an integer and *m* ≥ 1, and φ is Euler’s totient function.

First, if *m* = 1, since all integers are congruent with all other integers, mod 1, we need only show that *a*^{(2φ(φ(m)))} and *a*^{(22φ(φ(m)))} are integers. Because *m* is an integer, and *m* ≥ 1, φ(*m*) is an integer and φ(*m*) ≥ 1, and therefore, φ(φ(*m*)) and 2φ(φ(*m*)) are integers and 2φ(φ(*m*)) ≥ φ(φ(*m*)) ≥ 1. Therefore, by result 3.5, 2^{φ(φ(m))} and 2^{2φ(φ(m))} are integers and by result 1.5, 2^{φ(φ(m))} ≥ 1 and 2^{2φ(φ(m))} ≥ 1. Therefore, by result 3.5, *a*^{(2φ(φ(m)))} and *a*^{(22φ(φ(m)))} are integers, and it follows that they are congruent, mod 1.

If *m* ≥ 2, we will rely on the congruence of exponents. In order to prove the above congruence using the congruence of exponents, it is necessary to show that all of the following are true:

- 2
^{φ(φ(m))} ≥ emax(*m*)
- 2
^{2φ(φ(m))} ≥ emax(*m*)
- 2
^{φ(φ(m))} ≡ 2^{2φ(φ(m))} (mod λ(*m*))

Note that when *m* ≥ 2, *m* has a non-empty prime factorization such that emax(*m*) ≥ 1.

#### Part 1

Let’s consider, first, the case when emax(*m*) = 1. Because φ(φ(*m*)) ≥ 1 and φ(φ(*m*)) is an integer, since φ(*m*) ≥ 1 and φ(*m*) is an integer, given that *m* is an integer and *m* ≥ 1, it follows from result 1.5 that:

2^{φ(φ(m))} ≥ 1

Now let’s consider the case when emax(*m*) ≥ 2. If *m* is composed of the set of *n* prime factors, {*p*_{1}, *p*_{2}, …, *p*_{n}}, with corresponding exponents, [*e*_{1}, *e*_{2}, …, *e*_{n}], then we can represent *m* like so:

*m* = *p*_{1}^{e1} * *p*_{2}^{e2} * … * *p*_{n}^{en}

We can then use this representation to define φ(*m*):

φ(*m*) = φ(*p*_{1}^{e1}) * φ(*p*_{2}^{e2}) * … * φ(*p*_{n}^{en})

Based on how we defined emax(*m*), there must be at least one prime factor, *p*_{i}, of *m* such that the corresponding exponent, *e*_{i}, is equal to emax(*m*), where *i* is an integer and 1 ≤ *i* ≤ *n*. As a reminder, and to clarify for the notation used here, emax(*m*) is defined like so:

emax(*m*) = max(*e*_{1}, *e*_{2}, …, *e*_{n})

Let’s look now more closely at φ(*m*) and its relationship to *p*_{i}.

φ(*m*) = φ(*p*_{1}^{e1}) * φ(*p*_{2}^{e2}) * … * φ(*p*_{i}^{ei}) * … * φ(*p*_{n}^{en})

= *p*_{1}^{e1 – 1} * (*p*_{1} – 1) * *p*_{2}^{e2 – 1} * (*p*_{2} – 1) * … * *p*_{i}^{ei – 1} * (*p*_{i} – 1) * … * *p*_{n}^{en – 1} * (*p*_{n} – 1)

Because *e*_{i} = emax(*m*) ≥ 2, *e*_{i} – 1 ≥ 1. From this, it is clear that *p*_{i} is one of the prime factors of φ(*m*) and that the exponent of *p*_{i} in the prime factorization of φ(*m*) is at least *e*_{i} – 1. Note that the exponent of *p*_{i} in the prime factorization of φ(*m*) may be more than *e*_{i} – 1 if *p*_{i} happens to be a factor of one less than one of the other prime factors of *m*. This does not change the result, as will be shown below.

Now let’s consider the prime factorization of φ(*m*) so that we can use it to generate a representation of φ(φ(*m*)). If φ(*m*) is composed of the set of n’ prime factors, {*p’*_{1}, *p’*_{2}, …, *p*_{i}, …, *p’*_{n’}}, with corresponding exponents, [*e’*_{1}, *e’*_{2}, …, *e’*_{i}, …, *e’*_{n’}] such that *e’*_{i} ≥ *e*_{i} – 1 ≥ 1, then φ(*m*) can be represented like so:

φ(*m*) = *p’*_{1}^{e’1} * *p’*_{2}^{e’2} * … * *p*_{i}^{e’i} * … * *p’*_{n’}^{e’n’}

We can then use this representation to calculate φ(φ(*m*)) using the prime factorization of φ(*m*):

φ(φ(*m*)) = φ(*p’*_{1}^{e’1}) * φ(*p’*_{2}^{e’2}) * … * φ(*p*_{i}^{e’i}) * … * φ(*p’*_{n’}^{e’n’})

Note that φ(φ(*m*)) is composed of the products of the totients of each of the prime factors of φ(*m*). Because the prime factors of φ(*m*) are integer powers of prime integers, by result 3.5, the prime factors of φ(*m*) are all integers and, by result 1.5, they are all at least 1. Therefore, φ(φ(*m*)) cannot be less than the totient of any of the prime factors of φ(*m*). Therefore:

φ(φ(*m*)) ≥ φ(*p*_{i}^{e’i}) = *p*_{i}^{e’i – 1} * (*p*_{i} – 1)

Because *p*_{i} is a prime integer, *p*_{i} ≥ 2 and, therefore, *p*_{i} – 1 ≥ 1. Because *e’*_{i} is an integer and *e’*_{i} ≥ *e*_{i} – 1 and *e*_{i} = emax(*m*) ≥ 2, it follows that *e’*_{i} – 1 ≥ 0 and *e’*_{i} – 1 is an integer. Therefore, by result 1.5, *p*_{i}^{e’i – 1} ≥ 1. Therefore:

φ(φ(*m*)) ≥ *p*_{i}^{e’i – 1} * (*p*_{i} – 1) ≥ *p*_{i}^{e’i – 1}

Because *e’*_{i} ≥ *e*_{i} – 1, it follows that *e’*_{i} – 1 ≥ *e*_{i} – 2. Because *e’*_{i} and *e*_{i} are integers, it follows that *e’*_{i} – 1 and *e*_{i} – 2 are both integers. Because *e*_{i} = emax(*m*) ≥ 2, it follows that *e*_{i} – 1 ≥ *e*_{i} – 2 ≥ 0. Because *p*_{i} is a prime integer, *p*_{i} ≥ 2. Therefore, by result 2, it follows that:

φ(φ(*m*)) ≥ *p*_{i}^{e’i – 1} ≥ *p*_{i}^{ei – 2}

Because *p*_{i} is a prime integer, *p*_{i} ≥ 2. Therefore, because *e*_{i} – 2 is an integer and *e*_{i} – 2 ≥ 0, by result 1.5, it follows that *p*_{i}^{ei – 2} is an integer, and it follows from result 3.5, that *p*_{i}^{ei – 2} ≥ 1. Because φ(φ(*m*)) is an integer and φ(φ(*m*)) ≥ *p*_{i}^{ei – 2}, by result 2, it follows that:

2^{φ(φ(m))} ≥ 2^{piei – 2}

By result 4, since *p*_{i} is a prime integer and *e*_{i} is an integer and *e*_{i} ≥ 2, it follows that:

2^{piei – 2} ≥ *e*_{i} = emax(*m*)

It is possible that there may be more than one prime factor of *m* with an exponent equal to emax(*m*) such that:

*p*_{i} = *p*_{j} = emax(*m*), where *i* and *j* are integers and 1 ≤ *i* ≤ *n* and 1 ≤ *i* ≤ *n* and *i* ≠ *j*

In that case, the above argument applies to each such prime, individually, and independently of the others. The presence of multiple such primes in the prime factorization of *m* therefore does not change the result.

#### Part 2

Next we need to show that 2^{2φ(φ(m))} ≥ emax(*m*). This is quite easy to do now that we’ve shown the result of part 1.

As shown in part 1, φ(φ(*m*)) ≥ 1, and it follows that 2φ(φ(*m*)) ≥ φ(φ(*m*)). It was also shown in part 1 that φ(φ(*m*)) is an integer, and it follows that 2φ(φ(*m*)) is also an integer. Therefore, by result 2:

2^{2φ(φ(m))} ≥ 2^{φ(φ(m))} ≥ emax(*m*)

#### Part 3

We now need to show that 2^{φ(φ(m))} ≡ 2^{2φ(φ(m))} (mod λ(*m*)). For this, we will use the congruence of exponents a second time. In order to use the congruence of exponents here, we need to show that all of the following are true:

- φ(φ(
*m*)) ≥ emax(λ(*m*))
- 2φ(φ(
*m*)) ≥ emax(λ(*m*))
- φ(φ(
*m*)) ≡ 2φ(φ(*m*)) (mod λ(λ(*m*)))

##### Part 3a

If emax(λ(*m*)) = 1, it is clear that φ(φ(*m*)) ≥ emax(λ(*m*)), since we established in part 1 of the proof that φ(φ(*m*)) ≥ 1.

If emax(λ(*m*)) ≥ 2, we’ll need to be a little more clever.

Let’s look again at the way Euler’s totient function is calculated given the prime factorization of *m*. If *m* has the set of *n* prime factors, {*p*_{1}, *p*_{2}, …, *p*_{n}}, with corresponding exponents, [*e*_{1}, *e*_{2}, …, *e*_{n}], φ(*m*) is defined like so:

φ(*m*) = φ(*p*_{1}^{e1}) * φ(*p*_{2}^{e2}) * … * φ(*p*_{n}^{en})

Now let’s look again at the way the Carmichael function is calculated given the prime factorization of *m*. λ(*m*) is defined like so:

λ(*m*) = lcm(λ(*p*_{1}^{e1}), λ(*p*_{2}^{e2}), …, λ(*p*_{n}^{en}))

Let’s take a minute to examine what these definitions imply for the prime factorization of φ(*m*) and λ(*m*). One way of calculating the result of the least common multiple function is for each prime in the set which is the union of all primes in the prime factorization of the parameters to the function, take the max exponent of that prime in the prime factorization of the parameters to the function. Thus for a sequence of numbers, [*a*, *b*, *c*, …], where *a*_{p} is the exponent of the prime *p* in the prime factorization of *a*, lcm(*a*, *b*, *c*, …) can be defined like so:

lcm(a, b, c, ...) = \prod_p p^{max(a_p, b_p, c_p, ...)}

It should be clear from this and the fact that λ(*n*) divides φ(*n*) that every prime factor of λ(*m*) will also be a prime factor of φ(*m*) but that the exponent of a given prime factor of λ(*m*) may be less than the corresponding exponent of the same prime factor of φ(*m*). In fact, this is the very reason that λ(*n*) divides φ(*n*) and is also implied by divisibility. In order for λ(*m*) to divide φ(*m*), λ(*m*) cannot have any prime factors that φ(*m*) does not also have and the exponent of every prime factor of λ(*m*) must be less than or equal to the corresponding prime factor of φ(*m*).

If we consider now emax(λ(*m*)), there must be some prime factor, *p*_{i}, of λ(*m*) such that its exponent, *e*_{i} = emax(λ(*m*)), where *i* is an integer and 1 ≤ *i* ≤ *n*. Given the above discussion, we know that the same prime factor, *p*_{i}, is also present in the prime factorization of φ(*m*) and that the exponent of that prime factor in the prime factorization of φ(*m*) is greater than or equal to *e*_{i}.

Given that, let’s examine φ(φ(*m*)). If we represent the prime factorization of φ(*m*) as the set of *n’* prime integer factors that contains *p*_{i}, {*p’*_{1}, *p’*_{2}, …, *p*_{i}, …, *p’*_{n’}}, with corresponding exponents, [*e’*_{1}, *e’*_{2}, …, *e’*_{i}, …, *e’*_{n’}], where *e’*_{i} ≥ *e*_{i}, then φ(φ(*m*)) is defined like so:

φ(φ(*m*)) = φ(*p’*_{1}^{e’1}) * φ(*p’*_{2}^{e’2}) * … * φ(*p*_{i}^{e’i}) * … * φ(*p’*_{n’}^{e’n’})

Because all the prime factors of φ(*m*) are non-negative powers of prime integers, by result 3.5, they are integers, and by result 1.5, they are at least 1. Therefore, the totients of the prime factors of φ(*m*) are at least 1. Therefore:

φ(φ(*m*)) ≥ φ(*p*_{i}^{e’i}) = *p*_{i}^{e’i – 1} * (*p*_{i} – 1)

Because *p*_{i} is a prime integer, it follows that *p*_{i} ≥ 2 and *p*_{i} – 1 ≥ 1. Because *e’*_{i} ≥ *e*_{i} ≥ 2, it follows that *e’*_{i} – 1 ≥ 1. Because *e’*_{i} is an integer, it follows that *e’*_{i} – 1 is an integer. Therefore, by result 1.5, it follows that *p*_{i}^{e’i – 1} ≥ 1. Therefore:

φ(φ(*m*)) ≥ *p*_{i}^{e’i – 1}

Because *e’*_{i} – 1 ≥ 1 and *e’*_{i} – 1 is an integer, and because *p*_{i} ≥ 2 since *p*_{i} is a prime integer, by result 7, it follows that:

*p*_{i}^{e’i – 1} ≥ *e’*_{i}

##### Part 3b

It was shown in part 1 that φ(φ(*m*)) ≥ 1 and it was shown in part 3a that φ(φ(*m*)) ≥ emax(λ(*m*)). Therefore:

2φ(φ(*m*)) ≥ φ(φ(*m*)) ≥ emax(λ(*m*))

##### Part 3c

The final thing we need to show for the proof is that φ(φ(*m*)) ≡ 2φ(φ(*m*)) (mod λ(λ(*m*))). Because *m* is an integer and *m* ≥ 1, by result 6, it follows that λ(λ(*m*)) divides φ(φ(*m*)), which means that φ(φ(*m*)) is an integer multiple of λ(λ(*m*)). Therefore:

φ(φ(*m*)) ≡ 2φ(φ(*m*)) ≡ 0 (mod λ(λ(*m*)))

## First generalization

There is a generalization of the above congruence that is quite easy to show using just a very small change to the proof. It happens that the following congruence is also true:

*a*^{(dφ(φ(m)))} ≡ *a*^{(d2φ(φ(m)))} (mod *m*)

where *a* is an integer, and where *d* is an integer and *d* ≥ 0, and where *m* is an integer and *m* ≥ 1, and φ is Euler’s totient function, and where if *a* = 0 then *d* ≠ 0

The generalization here is that *d* replaces 2 as the intermediate exponent shown in the first proof.

## Proof

If *m* = 1, then we need only show that *a*^{(dφ(φ(m)))} and *a*^{(d2φ(φ(m)))} are integers since all integers are congruent with all other integers, mod 1. *a*^{(dφ(φ(m)))} and *a*^{(d2φ(φ(m)))} are integers for the same reason that *a*^{(2φ(φ(m)))} and *a*^{(22φ(φ(m)))} are integers, and it follows that they are congruent, mod 1.

If *m* ≥ 2 and *d* = 0, and therefore *a* ≠ 0 the result is trivial because all positive powers of 0 are equal to 0 and any number other than 0 raised to the power of 0 is equal to 1, and as shown in parts 1 and 2 of the first proof, 2φ(φ(*m*)) ≥ φ(φ(*m*)) ≥ 1. Thus, the congruence becomes this:

*a*^{(0φ(φ(m)))} = *a*^{0} = 1 ≡ *a*^{(02φ(φ(m)))} = *a*^{0} = 1 (mod *m*)

If *m* ≥ 2 and *d* = 1, the result is also trivial because 1 raised to any power is 1 and any number raised to the power of 1 is that number. Thus, the congruence becomes this:

*a*^{(1φ(φ(m)))} = *a*^{1} = *a* ≡ *a*^{(12φ(φ(m)))} = *a*^{1} = *a* (mod *m*)

If *m* ≥ 2 and *d* ≥ 2, we will rely again on the congruence of exponents. In order to prove the above congruence using the congruence of exponents, it is necessary to show that the following are true:

*d*^{φ(φ(m))} ≥ emax(*m*)
*d*^{2φ(φ(m))} ≥ emax(*m*)
*d*^{φ(φ(m))} ≡ *d*^{2φ(φ(m))} (mod λ(*m*))

Note, again, that when *m* ≥ 2, *m* has a non-empty prime factorization and emax(*m*) ≥ 1.

#### Part 1

To show that *d*^{φ(φ(m))} ≥ emax(*m*), we will rely on part 1 of the earlier proof where it was shown that:

2^{φ(φ(m))} ≥ emax(*m*)

Because *d* is an integer and *d* ≥ 2, and as shown in part 1 of the first proof, φ(φ(*m*)) ≥ 1 and φ(φ(*m*)) is an integer, by result 3, it follows that:

*d*^{φ(φ(m))} ≥ 2^{φ(φ(m))} ≥ emax(*m*)

#### Part 2

Because *d* is an integer and *d* ≥ 2, and because 2φ(φ(*m*)) ≥ φ(φ(*m*)), since φ(φ(*m*)) ≥ 1, and because φ(φ(*m*)) and 2φ(φ(*m*)) are integers, by result 2, it follows that:

*d*^{2φ(φ(m))} ≥ *d*^{φ(φ(m))} ≥ emax(*m*)

#### Part 3

The argument as to why *d*^{φ(φ(m))} ≡ *d*^{2φ(φ(m))} (mod λ(*m*)) is exactly the same as the argument in part 3 of the earlier proof. Remember that in part 3 of the earlier proof we used the congruence of exponents to show that:

2^{φ(φ(m))} ≡ 2^{2φ(φ(m))} (mod λ(*m*))

The only difference here is that here we have *d* in place of 2. The rule of the congruence of exponents says that:

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

where *a* is any integer, *b* and *c* are integers greater than or equal to emax(*m*), *m* is any positive integer, and *b* ≡ *c* (mod λ(*m*)), where λ is the Carmichael function. In the earlier proof, *a* in the congruence of exponents corresponded to 2, whereas here, *a* in the congruence of exponents corresponds to *d*. Because 2 and *d* are both integers, the arguments given in part 3 of the earlier proof apply equally here.

## Recursive congruence of exponents

It turns out that we can generalize this further by extending the depth with which we recurse to exponential powers and apply Euler’s totient function and by using any positive multipliers to the recursive totient function. It’s likely not clear what I mean by this so let me explain.

So far we’ve shown this:

*a*^{(2φ(φ(m)))} ≡ *a*^{(22φ(φ(m)))} (mod *m*)

and this:

*a*^{(dφ(φ(m)))} ≡ *a*^{(d2φ(φ(m)))} (mod *m*)

What I mean with this generalization is this:

*a*_{1}^{(a2(…anbφ(φ(…(φ(m))))))} ≡ *a*_{1}^{(a2(…ancφ(φ(…(φ(m))))))} (mod *m*)

where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where *n* > 0, and where *b*, *c*, and *m* are integers and *b* ≥ 1 and *c* ≥ 1 and *m* ≥ 1, and where if *n* > 1 then *a*_{i} ≥ 0 where *i* is an integer in the range 2 ≤ *i* ≤ *n*, and where no two consecutive elements of *A* are 0, and where φ(φ(…(φ(*m*)))) is Eueler’s totient function recursively applied to *m*, *n* times

To prove this, it will be convenient to define some notation.

#### Recursive Euler’s totient function

First, we’ll define a recursive version of Euler’s totient function, denoted by φ_{n}, which will be defined for an integer, *n*, where *n* ≥ 0, and an integer, *m*, where *m* ≥ 1, like so:

\phi_n(m) = \left\{ \begin{array}{ll} m & \text{if } n = 0 \\ \phi(\phi_{n - 1}(m)) & \text{if } n > 1 \end{array} \right.

As an example, φ_{2}(*m*) = φ(φ(*m*).

#### Recursive Carmichael function

Next, we’ll define a recursive version of the Carmichael function, denoted by λ_{n}, which will be defined for an integer, *n*, where *n* ≥ 0, and an integer, *m*, where *m* ≥ 1, like so:

\lambda_n(m) = \left\{ \begin{array}{ll} m & \text{if } n = 0 \\ \lambda(\lambda_{n - 1}(m)) & \text{if } n > 1 \end{array} \right.

Again, as an example, λ_{2}(*m*) = λ(λ(*m*).

#### O(*A*)

It will be useful to have a way of denoting the length of a given finite sequence. For a given finite sequence with *n* elements, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], I will use the notation O(*A*) to denote the number of elements in *A*. For the sequence, *A*, with *n* elements:

O(*A*) = *n*

#### Leading and trailing sub-sequences

It will be useful to have a way of denoting the trailing sub-sequence of a given finite sequence. For a given finite sequence with *n* elements, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], I will use the notation A_{i} to denote the sub-sequence of *A* beginning with the *i*^{th} element to the *n*^{th} element, in the same order as they occur in *A*, where *i* is an integer in the range 1 ≤ *i* ≤ *n*, using 1-based indexing.

Additionally, for the leading sub-sequence of *A* from the 1^{st} element to the *i*^{th} element in the same order as they occur in *A*, I will use the notation *A*_{–i}, where *i* is an integer in the range 1 ≤ *i* ≤ *n*, using 1-based indexing.

The following identities follow from these definitions:

*A*_{1} = *A*

O(*A*_{1}) = O(*A*)

O(*A*_{O(A)}) = 1

O(*A*_{-1}) = 1

O(*A*_{-O(A)}) = O(*A*)

O(*A*_{i}) = O(*A*) – (*i* – 1)

O(*A*_{–i}) = *i*

#### Sequence concatenation

It will also be useful to have a way of denoting concatenation of two finite sequences. Given a finite sequence, *A*, with *n* elements, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and a second finite sequence, *B*, with *m* elements, *B* = [*b*_{1}, *b*_{2}, …, *b*_{m}], I will use the notation *C* = *A* ++ *B* to indicate that *C* is the finite sequence with *n* + *m* elements, [*c*_{1}, *c*_{2}, …, *c*_{n}, *c*_{n + 1}, *c*_{n + 2}, …, *c*_{n + m}], where *c*_{i} = *a*_{i} for all integers, *i*, in the range 1 ≤ *i* ≤ *n* and *c*_{n + j} = *b*_{j} for all integers, *j*, in the range 1 ≤ *j* ≤ *m*.

For convenience, I will use the notation [*x*] to represent a finite sequence containing just one element with value *x*. Thus, given a finite sequence, *A*, with *n* elements, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], the term *D* = *A* ++ [*x*] indicates that *D* is the finite sequence with *n* + 1 elements, *D* = [*d*_{1}, *d*_{2}, …, *d*_{n}, *d*_{n + 1}], where *d*_{i} = *a*_{i} for all integers, *i*, in the range 1 ≤ *i* ≤ *n*, and *d*_{n + 1} = *x*.

#### Recursive exponentiation

It will be useful to have a function that performs recursive exponentiation. This function will operate on a non-empty finite sequence, *A*, of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}]. I will use the notation ρ, which will be defined like so:

\rho(A) = \left\{ \begin{array}{ll} a_1^{\rho(A_2)} & \text{if } O(A) \gt 1 \\ a_1 & \text{if } O(A) = 1 \end{array} \right.

Note that the function ρ performs exponentiation of each element of the sequence using the ρ function applied to the remainder of the sequence, if there is one, and evaluates to just the value of the one element if it is the last element. For example, for a finite sequence with 3 elements, *A* = [*a*_{1}, *a*_{2}, *a*_{3}], where *a*_{2} ≠ 0:

ρ(*A*) = *a*_{1}^{(ρ(A2))} = *a*_{1}^{(a2(ρ(A3)))} = *a*_{1}^{(a2(a3))}

Note that for a finite sequence, *A*, of *n* integers, ρ(*A*) being defined implies that ρ(*A*_{i}) is also defined for all integers, *i*, in the range 1 ≤ *i* ≤ *n*. For a finite sequence, *A*, of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], where *n* > 0, if for some integer *i* where 1 ≤ *i* < *n*, *a*_{i} = 0 and ρ(*A*_{i + 1}) ≤ 0, ρ(*A*) is undefined because ρ(*A*_{i}) is undefined because ρ(*A*_{i}) is 0 raised to a non-positive power, which is undefined.

#### Recursive exponentiation and totient

Finally, it will also be useful to have an additional recursive exponentiation function that will combine the ρ function we just defined with the recursive version of Euler’s totient function. This function will operate a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], where ρ(*A*) is defined, but will first raise the final element of *A*, being *a*_{n}, using the product of φ_{n}(*m*), for some positive integer, *m*, and a given integer, *s*. I will use the notation ψ for this function, which will be defined like so:

\psi(A, s, m) = \left\{ \begin{array}{ll} a_1^{\psi(A_2, s, \phi(m))} & \text{if } O(A) \gt 1 \\ a_1^{s\phi(m)} & \text{if } O(A) = 1 \end{array} \right.

As an example, for a sequence, *A*, of 2 integers, *A* = [*a*_{1}, *a*_{2}], and integer, *s*, and positive integer, *m*, ψ(*A*, *s*, *m*) evaluates to this:

ψ(*A*, *s*, *m*) = *a*_{1}^{(a2(sφ(φ(m))))})

Note that the following identity follows from the definition of ψ. For a given finite sequence, *A*, of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], an integer, *s*, and a positive integer, *m*, where *n* ≥ 1:

ψ(*A*, *s*, *m*) = ρ(*A* ++ [*s*φ_{n}(*m*)])

#### Redefining the recursive congruence of exponents

Using the ψ function, we can now declare the congruence relationship that we intend to prove more precisely. We will rewrite the congruence above like so:

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], where ρ(*A*) is defined, and where if *n* > 1 then *a*_{i} ≥ 0 for each integer, *i*, in the range 2 ≤ *i* ≤ *n*, and where *b*, *c*, and *m* are integers, and *b* ≥ 1 and *c* ≥ 1 and *m* ≥ 1

### More intermediate results

To prove the recursive congruence of exponents, we’ll need some additional intermediate results. If you wish, you may skip directly to the proof and refer back to the intermediate results, to which I’ve provided links.

**Result 8**

ρ(*A*) = 0, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *a*_{1} = 0

If O(*A*) = 1, ρ(*A*) = *a*_{1} = 0.

If O(*A*) > 1, because ρ(*A*) is defined, we know that ρ(*A*_{2}) is defined, and we know that ρ(*A*_{2}) > 0, since *a*_{1} = 0. Because 0 raised to any positive power is 0, it follows that:

ρ(*A*) = *a*_{1}^{ρ(A2)} = 0^{ρ(A2)} = 0

**Result 9**

*x* * *y* ≥ *x* + *y*, where *x* ≥ 2, and where *y* ≥ 2

Because *x* – 1 ≥ 1 and *y* – 1 ≥ 1, given that *x* ≥ 2 and *y* ≥ 2, it follows that:

(*x* – 1) * (*y* – 1) ≥ 1

If we multiply out on the left hand side, we get:

(*x* * *y*) – *x* – *y* + 1 ≥ 1

If we now add *x* + *y* – 1 to both sides we get:

*x* * *y* ≥ *x* + *y*

**Result 10**

ρ(*A*) ≥ 1, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *a*_{1} ≥ 1, and if *n* > 1, where *a*_{i} ≥ 0 for all integers, *i*, in the range 2 ≤ *i* ≤ *n*

If *n* = 1, then ρ(*A*) = *a*_{1} ≥ 1.

If *n* > 1, then ρ(*A*) = *a*_{1}^{ρ(A2)}. Because ρ(*A*_{2}) is defined, given that ρ(*A*) is defined, and given that all elements of *A*_{2} are integers and are at least 0, by result 16, ρ(*A*_{2}) is an integer and ρ(*A*_{2}) ≥ 0. Given that *a*_{1} is an integer and that *a*_{1} ≥ 1, by result 2, it follows that:

*a*_{1}^{ρ(A2)} ≥ *a*_{1}^{0} = 1

**Result 11**

ρ(*A*) is defined, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where *n* > 0, and where *a*_{i} ≥ 0 for all integers, *i*, in the range 1 ≤ *i* ≤ *n*, and where no two consecutive elements of *A* are 0

If *n* = 1, then ρ(*A*) is defined because ρ(*A*) = *a*_{1}.

If *n* > 1, then we will show that ρ(*A*) is defined by mathematical induction using the length of the trailing sub-sequence of *A* as the induction variable. The basis statement is this:

P(1):

When the length of the trailing sub-sequence of *A* is 1 then we are referring to *A*_{n}. In this case, ρ(*A*_{n}) is defined because ρ(*A*_{n}) = *a*_{n}.

The induction hypothesis is this:

P(*k*):

ρ(*A*_{n – (k – 1)}) is defined, where *k* is an integer and 1 ≤ *k* < *n*

Note that when *k* = 1, the induction hypothesis reduces to the basis statement, since *n* = *n* – (1 – 1).

Now the induction step:

P(*k* + 1):

ρ(*A*_{n – ((k + 1) – 1)}) = ρ(*A*_{n – k}) = *a*_{n – k}^{ρ(A(n – k) + 1)} = *a*_{n – k}^{ρ(An – (k – 1))}

If *a*_{n – k} = 0, then it is given that *a*_{n – (k – 1)} ≥ 1. Therefore, by result 10, ρ(*A*_{n – (k – 1)}) ≥ 1, since by the induction hypothesis, ρ(*A*_{n – (k – 1)}) is defined, and given that all elements of *A*_{n – (k – 1)} are integers that are at least 0. Therefore, ρ(*A*_{n – k}) is defined because is it 0 raised to a positive power.

If *a*_{n – k} ≥ 1, then ρ(*A*_{n – k}) is defined because, by the induction hypothesis, ρ(*A*_{n – (k – 1)}) is defined.

This implies that the result is true when *k* = *n* – 1, which is when *A*_{n – k} = *A*_{1} = *A*. Therefore, ρ(*A*) is defined.

**Result 12**

ρ(*A*) = 1, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], where ρ(*A*) is defined, and where *a*_{1} = 1

If O(*A*) = 1, ρ(*A*) = *a*_{1} = 1.

If O(*A*) > 1, because ρ(*A*) is defined, ρ(*A*_{2}) must also be defined. Because 1 raised to any power is 1:

ρ(*A*) = *a*_{1}^{ρ(A2)} = 1

**Result 13**

ρ(*A*) = ρ(*B*), where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *B* is a finite sequence of *m* integers, *B* = [*b*_{1}, *b*_{2}, …, *b*_{m}], and where there is some element, *a*_{i}, where *i* is an integer and 1 ≤ *i* ≤ *n* and 1 ≤ *i* ≤ *m*, where *a*_{j} = *b*_{j} for each integer, *j*, in the range 1 ≤ *j* < *i*, and where ρ(*A*_{i}) = ρ(*B*_{i})

If *i* = 1, the result follows directly from the identity of ρ(*A*) and ρ(*B*):

ρ(*A*) = ρ(*A*_{1}) = ρ(*B*_{1}) = ρ(*B*)

If *i* > 1, the result can be shown using mathematical induction using the length of the sub-sequences from *A* and *B* prior to *i*. First, the basis statement:

P(0):

When the length of the trailing sub-sequences of *A* and *B* prior to *i* is 0, we are referring to *A*_{i} and *B*_{i}.

ρ(*A*_{i}) = ρ(*B*_{i})

This induction hypothesis is this:

P(*k*):

ρ(*A*_{i – k}) = ρ(*B*_{i – k}), where *k* is an integer and where 0 ≤ *k* < *i*

Note that when *k* = 0, the induction hypothesis reduces to the basis statement because *i* = *i* – 0.

The induction step is this:

P(*k* + 1):

ρ(*A*_{i – (k + 1)}) = ρ(*A*_{(i – k) – 1}) = *a*_{(i – k) – 1}^{ρ(A(i – k) – 1 + 1)} = *a*_{(i – k) – 1}^{ρ(Ai – k)}

ρ(*B*_{i – (k + 1)}) = ρ(*B*_{(i – k) – 1}) = *b*_{(i – k) – 1}^{ρ(B(i – k) – 1 + 1)} = *b*_{(i – k) – 1}^{ρ(Bi – k)}

One of the original given conditions was that all elements of *A* and *B* prior to *i* are equal. Because *k* ≥ 0, it follows that (*i* – *k*) – 1 < *i*. Therefore:

*a*_{(i – k) – 1} = *b*_{(i – k) – 1}

Since, by the induction hypothesis, ρ(*A*_{i – k}) = ρ(*B*_{i – k}), it follows that:

*a*_{(i – k) – 1}^{ρ(Ai – k)} = *b*_{(i – k) – 1}^{ρ(Bi – k)}

This implies that ρ(*A*_{i – k}) = ρ(*B*_{i – k}) when *k* = *i* – 1 and *i* – *k* = 1. Therefore:

ρ(*A*) = ρ(*A*_{1}) = ρ(*B*_{1}) = ρ(*B*)

**Result 14**

ρ(*A*) = ρ(*A*_{–i}), where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *a*_{i} = 1 for some integer, *i*, where 1 ≤ *i* ≤ *n*

If *B* = *A*_{–i}, where *B* = [*b*_{1}, *b*_{2}, …, *b*_{i}], then *b*_{j} = *a*_{j} for each *j* in the range 1 ≤ *j* ≤ *i*. Since *a*_{i} = *b*_{i} = 1, by result 12, ρ(*A*_{i}) = ρ(*B*_{i}) = 1. Therefore, by result 13, since ρ(*A*) is defined, it follows that:

ρ(*A*) = ρ(*B*) = ρ(*A*_{–i})

**Result 15**

ρ(*A*) = ρ(*A*_{–i}), where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *a*_{i} = 0 for some integer, *i*, where 1 ≤ *i* ≤ *n*

If *B* = *A*_{–i}, where *B* = [*b*_{1}, *b*_{2}, …, *b*_{i}], then *b*_{j} = *a*_{j} for each *j* in the range 1 ≤ *j* ≤ *i*. Since *a*_{i} = *b*_{i} = 0, by result 8, ρ(*A*_{i}) = ρ(*B*_{i}) = 0. Therefore, by result 13, given that ρ(*A*) is defined, it follows that:

ρ(*A*) = ρ(*B*) = ρ(*A*_{–i})

**Result 16**

ρ(*A*) is an integer and ρ(*A*) ≥ 0, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *a*_{i} ≥ 0, for each integer, *i*, in the range 1 ≤ *i* ≤ *n*

If O(*A*) = 1, ρ(*A*) = *a*_{1}. Because *a*_{1} is an integer and *a*_{1} ≥ 0, ρ(*A*) is an integer and ρ(*A*) ≥ 0.

If O(*A*) > 1, the result can be shown by mathematical induction using the length of the trailing sub-sequence of *A* as the induction variable. The basis statement is this:

P(1):

In the case where the length of the trailing sub-sequence is 1, the sub-sequence in question is *A*_{n}.

ρ(*A*_{n}) = *a*_{n}

*a*_{n} is an integer and *a*_{n} ≥ 0, which shows that the basis statement is true.

The induction hypothesis is this:

P(*k*):

ρ(*A*_{n – (k – 1)}) is an integer and ρ(*A*_{n – (k – 1)}) ≥ 0, where *k* is an integer and 1 ≤ *k* ≤ *n*

Note that the induction hypothesis simplifies to the basis statement when *k* = 1, since *n* = *n* – (1 – 1).

The induction step is this:

P(*k* + 1):

ρ(*A*_{n – ((k + 1) – 1)}) = ρ(*A*_{n – k}) = *a*_{n – k}^{ρ(A(n – k) + 1)} = *a*_{n – k}^{ρ(A(n – (k – 1))}

If *a*_{n – k} = 0, then, because ρ(*A*) is defined, ρ(*A*_{n – (k – 1)}) > 0. Therefore, *a*_{n – k}^{ρ(A(n – (k – 1))} = 0 because it is 0 raised to a positive power.

If *a*_{n – k} ≠ 0, then it is an integer ant it is at least 1. By the induction hypothesis, ρ(*A*_{(n – (k – 1)}) is an integer and ρ(*A*_{(n – (k – 1)}) ≥ 0. Therefore, by result 1.5, it follows that *a*_{n – k}^{ρ(A(n – (k – 1))} ≥ 1, and by result 3.5, *a*_{n – k}^{ρ(A(n – (k – 1))} is an integer.

This implies that ρ(*A*_{(n – k)}) is an integer and ρ(*A*_{(n – k)}) ≥ 0 when *k* = *n* – 1, which is ρ(*A*_{1}). Therefore, ρ(*A*) is an integer and ρ(*A*) ≥ 0 because ρ(*A*) = ρ(*A*_{1}).

**Result 17**

φ_{n}(*m*) ≥ 1 and φ_{n}(*m*) is an integer, where *m* is an integer and *m* ≥ 1, and where *n* is an integer and *n* ≥ 0

We will show this by mathematical induction using *n* as the induction variable. The basis case is this:

P(0):

φ_{0}(*m*) = *m*

Because *m* is an integer and *m* ≥ 1, this shows the basis case.

The induction hypothesis is this:

P(*k*):

φ_{k}(*m*) ≥ 1 and φ_{k}(*m*) is an integer, where *k* is an integer and *k* ≥ 0

The induction step is this:

P(*k* + 1):

φ_{k + 1}(*m*) = φ(φ_{k}(*m*))

If we substitute *m’* for φ_{k}(*m*), we get this:

φ(φ_{k}(*m*)) = φ(*m’*)

By the induction hypothesis, *m’* ≥ 1 and *m’* is an integer. For a positive integer, *m’*, the result of Euler’s totient is an integer such that 1 ≤ φ(*m’*) ≤ *m’*. Therefore:

φ_{k + 1}(*m*) ≥ 1 and φ_{k + 1}(*m*) is an integer

**Result 18**

*x*^{n} ≥ *xn*, where *x* is an integer and *x* ≥ 2, and *n* is an integer and *n* ≥ 1

Because *x* > 0, we can divide both sides of the inequality by *x* without changing the direction of the inequality. Thus:

(*x*^{n} / *x*) ≥ (*xn* / *x*)

which simplifies to:

*x*^{n – 1} ≥ *n*

which is true by result 7, since *x* is an integer and *x* ≥ 2, and since *n* – 1 is an integer and *n* – 1 ≥ 0, given that *n* is an integer and *n* ≥ 1.

**Result 19**

ρ(*A* ++ [*x*]) ≥ *x* * ρ(*A*), where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and *a*_{i} ≥ 2 for all integers, *i*, in the range 1 ≤ *i* ≤ *n*, and where *x* is an integer and *x* ≥ 1

If O(*A*) = 1:

ρ(*A* ++ [*x*]) = *a*_{1}^{x}

By result 18, given that *a*_{1} is an integer and *a*_{1} ≥ 2, and given that *x* is an integer and *x* ≥ 1, it follows that:

*a*_{1}^{x} ≥ *x* * *a*_{1} = *x* * ρ(*A*)

If O(*A*) > 1, and *x* = 1, it follows that *x* * *a*_{n} = *a*_{n} = *a*_{n}^{x} and that ρ(*A*_{n}) = ρ(*A*_{n} ++ [*x*]). Therefore, by result 13, it follows that:

ρ(*A*) = ρ(*A* ++ [*x*])

If O(*A*) > 1, and *x* ≥ 2, we will show the result by mathematical induction using the length of the trailing sub-sequence of *A* as the induction variable. The basis statement is this:

P(1):

When the length of the trailing sub-sequence is 1, we are referring to *A*_{n}.

ρ(*A*_{n} ++ [*x*]) = *a*_{n}^{x}

By result 18, given that *x* is an integer and *x* ≥ 1, and given that *a*_{n} is an integer and *a*_{n} ≥ 2:

*a*_{n}^{x} ≥ *x* * *a*_{n} = *x* * ρ(*A*_{n})

which shows the basis statement is true. Now the induction hypothesis:

P(*k*):

The trailing sub-sequence of *A* with length *k* is *A*_{n – (k – 1)}.

ρ(*A*_{n – (k – 1)} ++ [*x*]) ≥ *x* * ρ(*A*_{n – (k – 1)}), where *k* is an integer and 1 ≤ *k* ≤ *n*

Note that the induction hypothesis simplifies to the basis statement when *k* = 1, since in that case *n* = *n* – (1 – 1).

Now the induction step:

P(*k* + 1):

ρ(*A*_{n – ((k + 1) – 1)} ++ [*x*]) = ρ(*A*_{n – k} ++ [*x*]) = *a*_{n – k}^{ρ(A(n – k) + 1 ++ [x])} = *a*_{n – k}^{ρ(An – (k – 1) ++ [x])}

By result 16, ρ(*A*_{n – (k – 1)}) and ρ(*A*_{n – (k – 1)} ++ [*x*]) are integers, given that all elements of *A* are integers that are at least 2 and since *x* ≥ 2, and by result 20, they are at least 2. By the induction hypothesis, ρ(*A*_{n – (k – 1)} ++ [*x*]) ≥ *x* * ρ(*A*_{n – (k – 1)}), therefore, by result 2, given that *a*_{n – k} is an integer and that *a*_{n – k} ≥ 2 > 1:

*a*_{n – k}^{ρ(An – (k – 1) ++ [x])} ≥ *a*_{n – k}^{(x * ρ(An – (k – 1)))}

By result 20, ρ(*A*_{n – (k – 1)}) ≥ 2, given that all elements of *A* are integers that are at least 2. Therefore, by result 9, since *x* ≥ 2, it follows that:

*x* * ρ(*A*_{n – (k – 1)}) ≥ *x* + ρ(*A*_{n – (k – 1)})

Given that *x* is an integer, and by result 16, ρ(*A*_{n – (k – 1)}) is an integer, it follows that *x* + ρ(*A*_{n – (k – 1)}) is an integer. Because *x* ≥ 2, and by result 20, given that all elements of *A* are integers that are at least 2, ρ(*A*_{n – (k – 1)}) ≥ 2, and it follows that *x* + ρ(*A*_{n – (k – 1)}) > 0. Therefore, given that *a*_{n – k} ≥ 2, by result 2, it follows that:

*a*_{n – k}^{(x * ρ(An – (k – 1)))} ≥ *a*_{n – k}^{(x + ρ(An – (k – 1)))} = *a*_{n – k}^{x} * *a*_{n – k}^{ρ(An – (k – 1))} = *a*_{n – k}^{x} * ρ(*A*_{n – k})

By result 2, since *x* – 1 is an integer and *x* – 1 ≥ 1, given that *x* is an integer and since *x* ≥ 2, and since *a*_{n – k} is an integer and *a*_{n – k} ≥ 2, it follows that:

*a*_{n – k}^{x} ≥ *a*_{n – k}^{x – 1}

By result 7, given that *x* is an integer and since *x* ≥ 2, and given that *a*_{n – k} is an integer and *a*_{n – k} ≥ 2, it follows that:

*a*_{n – k}^{x – 1} ≥ *x*

By result 20, ρ(*A*_{n – k}) ≥ 2, given that all elements of *A* are integers and at least 2. Therefore, since *x* ≥ 2:

*a*_{n – k}^{x} * ρ(*A*_{n – k}) ≥ *x* * ρ(*A*_{n – k})

This implies that the result is true when *k* = *n* – 1, which is when *A*_{n – k} = *A*_{1} = *A*. Therefore, ρ(*A* ++ [*x*]) ≥ *x* * ρ(*A*).

**Result 20**

ρ(*A*) ≥ 2, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and *a*_{i} ≥ 2 for all integers, *i*, in the range 1 ≤ *i* ≤ *n*

If O(*A*) = 1, ρ(*A*) = *a*_{1} ≥ 2.

If O(*A*) > 1, we will show the result by mathematical induction using the length of the trailing sub-sequence of *A* as the induction variable. The basis statement is this:

P(1):

The trailing sub-sequence of *A* with length 1 is *A*_{n}.

ρ(*A*_{n}) = *a*_{n} ≥ 2

The induction hypothesis is this:

P(*k*):

The trailing sub-sequence of *A* of length *k* is *A*_{n – (k – 1)}.

ρ(*A*_{n – (k – 1)}) ≥ 2, where *k* is an integer and 1 ≤ *k* < *n*

Note that the induction hypothesis simplifies to the basis statement when *k* = 1, since in that case *n* = *n* – (1 – 1).

The induction step is this:

P(*k* + 1):

ρ(*A*_{n – ((k + 1) – 1)}) = ρ(*A*_{n – k}) = *a*_{n – k}^{ρ(A(n – k) + 1)} = *a*_{n – k}^{ρ(An – (k – 1))}

By result 16, given that all elements of *A* are integers that are at least 2, it follows that ρ(*A*_{n – (k – 1)}) is an integer and ρ(*A*_{n – (k – 1)}) ≥ 0. Therefore, by result 3 since *a*_{n – k} ≥ 2 > 1:

*a*_{n – k}^{ρ(An – (k – 1))} ≥ 2^{ρ(An – (k – 1))}

By result 2, since ρ(*A*_{n – (k – 1)}) ≥ 2 by the induction hypothesis, therefore:

2^{(ρ(An – (k – 1)))} ≥ 2^{2} = 4 > 2

This implies that the result is true when *k* = *n* – 1, which is when *A*_{n – k} = *A*_{1} = *A*. Therefore, ρ(*A*) ≥ 2.

**Result 21**

ρ(*A*) ≥ 2^{n}, where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *a*_{i} ≥ 2 for all integers, *i*, in the range 1 ≤ *i* ≤ *n*

If O(*A*) = 1, ρ(*A*) = *a*_{1} ≥ 2 = 2^{1}

If O(*A*) > 1, we will show the result by mathematical induction using the length of the trailing sub-sequence of *A* as the induction variable. The basis statement is this:

P(1):

When the length of the trailing sub-sequence of *A* is 1, we are referring to *A*_{n}.

ρ(*A*_{n}) = *a*_{n} ≥ 2 = 2^{1}

The induction hypothesis is this:

P(*k*):

The trailing sub-sequence of *A* of length *k* is *A*_{n – (k – 1)}.

ρ(*A*_{n – (k – 1)}) ≥ 2^{k}, where *k* is an integer and 1 ≤ *k* < *n*

Note that the induction hypothesis simplifies to the basis statement when *k* = 1, since in that case *n* = *n* – (1 – 1).

The induction step is this:

P(*k* + 1):

ρ(*A*_{n – ((k + 1) – 1)}) = ρ(*A*_{n – k}) = *a*_{n – k}^{ρ(A(n – k) + 1))} = *a*_{n – k}^{ρ(An – (k – 1)))}

By result 16, ρ(*A*_{n – (k – 1)}) is an integer, given that all elements of *A* are integers that are at least 2. Given that *k* is an integer and *k* ≥ 1, by result 1.5, 2^{k} ≥ 1, and by result 3.5, 2^{k}is an integer. Given that *a*_{n – k} is an integer and *a*_{n – k} ≥ 2, and by the induction hypothesis, ρ(*A*_{n – (k – 1)}) ≥ 2^{k}, by result 2, it follows that:

*a*_{n – k}^{ρ(An – (k – 1)))} ≥ *a*_{n – k}^{(2k)}

Given that *a*_{n – k} is an integer and *a*_{n – k} ≥ 2, and given that *k* is an integer and *k* ≥ 1, by result 1.5, 2^{k} ≥ 1, and by result 3.5, 2^{k}is an integer. By result 3, it follows that:

*a*_{n – k}^{(2k)} ≥ 2^{(2k)}

Given that *k* is an integer and *k* ≥ 1, by result 1.5, 2^{k} ≥ 1, and by result 3.5, 2^{k}is an integer. By result 18, therefore:

2^{(2k)} ≥ 2 * 2^{k} = 2^{k + 1}

This implies that the result is true when *k* = *n* – 1, which is when *A*_{n – (k – 1)} = *A*_{1} = *A*. Therefore, ρ(*A*) ≥ 2^{n}.

**Result 23**

φ(*m*) ≥ *p*_{i}^{ei – 1} and *p*_{i}^{ei – 1} divides φ(*m*), where *m* is an integer and *m* ≥ 2, and where *p*_{i} is the *i*^{th} prime factor and *e*_{i} is the exponent corresponding to *p*_{i} in the prime factorization of *m*

Given that *m* is an integer and *m* ≥ 2, we know that *m* has a non-empty prime factorization. If we consider the prime factorization of a *m* to be the set of *n* prime integers, {*p*_{1}, *p*_{2}, …, *p*_{n}}, with corresponding exponents, [*e*_{1}, *e*_{2}, …, *e*_{n}], such that:

*m* = *p*_{1}^{e1} * *p*_{2}^{e2} * … * *p*_{n}^{en}

then we know that φ(*m*) is defined like so:

φ(*m*) = φ(*p*_{1}^{e1}) * φ(*p*_{2}^{e2}) * … * φ(*p*_{n}^{en})

Since the prime factors of *m* are positive integer powers of positive integers, by result 3.5, they are integers, and by result 1.5, they are at least 1. Because the totient of a positive integer is an integer and at least 1, it follows that the totient of the prime factors of *m* are integers and they are at least 1. Therefore, if we choose the *i*^{th} prime factor from the set of prime integer factors of *m*, where 1 ≤ *i* ≤ *n*, it follows that:

φ(*m*) ≥ φ(*p*_{i}^{ei}) = *p*_{i}^{ei – 1} * (*p*_{i} – 1)

Because *p*_{i} is a prime integer, *p*_{i} – 1 ≥ 1, since *p*_{i} ≥ 2, and it follows that:

φ(*m*) ≥ *p*_{i}^{ei – 1}

Because φ(*p*_{i}^{ei}) must appear as one of the terms on the right side of the equation where we calculated φ(*m*), and because φ(*p*_{i}^{ei}) = *p*_{i}^{ei – 1} * (*p*_{i} – 1), we can divide both sides by *p*_{i}^{ei – 1} and we get this:

φ(*m*) / *p*_{i}^{ei – 1} = φ(*p*_{1}^{e1}) * φ(*p*_{2}^{e2}) * … * (*p*_{i} – 1) * … * φ(*p*_{n}^{en})

Because the totient of each of the prime factors of *m* is an integer, and *p*_{i} is an integer, and therefore *p*_{i} – 1 is an integer, it follows that the right hand side of the equation is an integer. The left hand side must also be an integer, and therefore *p*_{i}^{ei – 1} divides φ(*m*).

**Result 24**

ψ(*A*, *s*, φ(*m*)) ≥ emax(*m*), where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where ρ(*A*) is defined, and where *s* and *m* are integers and *s* ≥ 1 and *m* ≥ 1, and where *a*_{i} ≥ 2 for all integers, *i*, in the range 1 ≤ *i* ≤ *n*, and where *n* ≥ emax(*m*)

Remember from the definition of the ψ function that:

ψ(*A*, *s*, *m*) = ρ(*A* ++ [*s* * φ_{n}(*m*)])

Given that *m* is an integer and *m* ≥ 1, and since *n* is an integer and *n* ≥ 1, given that ρ(*A*) is defined, by result 17, it follows that φ_{n}(*m*) is an integer and φ_{n}(*m*) ≥ 1. Given that *s* is an integer and *s* ≥ 1, it follows that *s* * φ_{n}(*m*) is an integer and *s* * φ_{n}(*m*) ≥ 1. Therefore, given that ρ(*A*) is defined and all elements of *A* are integers that are at least 2, by result 19, it follows that:

ρ(*A* ++ [*s* * φ_{n}(*m*)]) ≥ *s* * φ_{n}(*m*) * ρ(*A*)

Given that ρ(*A*) is defined and that all elements of *A* are integers that are at least 2, by result 21, it follows that:

ρ(*A*) ≥ 2^{n}

By result 1.5, given that *n* is an integer and *n* ≥ 1 given that ρ(*A*) is defined, it follows that ρ(*A*) ≥ 2^{n} ≥ 1. Therefore:

*s* * φ_{n}(*m*) * ρ(*A*) ≥ ρ(*A*) ≥ 2^{n}

By result 2, given that *n* is an integer and *n* ≥ 1 given that ρ(*A*) is defined, it follows that:

2^{n} ≥ 2^{n – 1}

By result 7, given that *n* is an integer and *n* ≥ 1 given that ρ(*A*) is defined:

2^{n – 1} ≥ *n* ≥ emax(*m*)

**Result 25**

φ_{n}(*m*) ≥ *p*_{i}^{ei – n} and *p*_{i}^{ei – n} divides φ_{n}(*m*), where *m* is an integer and *m* ≥ 2, and where *n* is an integer, and where emax(*m*) > *n* ≥ 1, and where *p*_{i} is the *i*^{th} integer prime factor of *m* and *e*_{i} is the exponent corresponding to *p*_{i} in the prime factorization of *m*, and where *e*_{i} = emax(*m*)

We will show this by mathematical induction using *n* as the induction variable. The basis statement is this:

P(1):

By the definition of the recursive totient function:

φ_{1}(*m*) = φ(*m*)

By result 23, given that *m* is an integer and *m* ≥ 2, it follows that φ(*m*) ≥ *p*_{i}^{ei – 1} and *p*_{i}^{ei – 1} divides φ(*m*).

The induction hypothesis is this:

P(*k*):

φ_{k}(*m*) ≥ *p*_{i}^{ei – k} and *p*_{i}^{ei – k} divides φ_{k}(*m*), where *k* is an integer and 1 ≤ *k* ≤ *n* < emax(*m*)

The induction step is this:

P(*k* + 1):

By the definition of the recursive totient function:

φ_{k + 1}(*m*) = φ(φ_{k}(*m*))

By the induction hypothesis, *p*_{i}^{ei – k} divides φ_{k}(*m*). Therefore, *p*_{i} is one of the prime factors of φ_{k}(*m*) and the exponent of *p*_{i} in the prime factorization of φ_{k}(*m*) must be at least *e*_{i} – *k*. Because *e*_{i} = emax(*m*) > *n* ≥ *k*, we know that *e*_{i} – *k* > 1. Because *e*_{i} and *k* are both integers, *e*_{i} – *k* is an integer. Because *p*_{i} is a prime integer,*p*_{i} ≥ 2. Therefore, by result 2, it follows that:

*p*_{i}^{ei – k} ≥ 2^{1} = 2

Additionally, by result 3.5, *p*_{i}^{ei – k} is an integer. Therefore, by result 23, it follows that:

φ(φ_{k}(*m*)) ≥ *p*_{i}^{(ei – k) – 1} = *p*_{i}^{ei – (k + 1)} and *p*_{i}^{ei – (k + 1)} divides φ(φ_{k}(*m*))

This implies that the result is true when *k* = *n*. Therefore, φ_{n}(*m*) ≥ *p*_{i}^{ei – n} and *p*_{i}^{ei – n} divides φ_{n}(*m*).

**Result 26**

ψ(*A*, *s*, *m*) ≥ emax(*m*), where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], and where where ρ(*A*) is defined, and *s* and *m* are integers and *s* ≥ 1 and *m* ≥ 1, and where *a*_{i} ≥ 2 for all integers, *i*, in the range 1 ≤ *i* ≤ *n*, and where *n* < emax(*m*)

Remember from the definition of the ψ function that:

ψ(*A*, *s*, *m*) = ρ(*A* ++ [*s* * φ_{n}(*m*)])

Given that *m* is an integer and *m* ≥ 1, and since *n* is an integer and *n* ≥ 1, given that ρ(*A*) is defined, by result 17, it follows that φ_{n}(*m*) is an integer and φ_{n}(*m*) ≥ 1. Given that *s* is an integer and *s* ≥ 1, it follows that *s* * φ_{n}(*m*) is an integer and *s* * φ_{n}(*m*) ≥ 1. Therefore, given that ρ(*A*) is defined and all elements of *A* are integers that are at least 2, by result 19, it follows that:

ρ(*A* ++ [*s* * φ_{n}(*m*)]) ≥ *s* * φ_{n}(*m*) * ρ(*A*)

Given that ρ(*A*) is defined and that all elements of *A* are integers that are at least 2, by result 21, it follows that:

ρ(*A*) ≥ 2^{n}

By result 1.5, given that *n* is an integer and *n* ≥ 1 given that ρ(*A*) is defined, it follows that 2^{n} ≥ 1. Therefore:

*s* * φ_{n}(*m*) * ρ(*A*) ≥ φ_{n}(*m*) * ρ(*A*)

Because *n* is an integer and *n* ≥ 1, given that ρ(*A*) is defined, and since emax(*m*) > *n*, by result 25, it follows that:

φ_{n}(*m*) ≥ *p*_{i}^{ei – n}

where *p*_{i} is the *i*^{th} prime factor of *m*, in the prime factorization of *m* such that the corresponding exponent, *e*_{i} = emax(*m*).

Because *p*_{i} is a prime integer, *p*_{i} ≥ 2. Because *e*_{i} and *n* are integers and *e*_{i} > *n*, *e*_{i} – *n* is an integer and *e*_{i} – *n* > 0. Therefore, by result 3, it follows that:

*p*_{i}^{ei – n} ≥ 2^{ei – n}

Therefore:

φ_{n}(*m*) * ρ(*A*) ≥ 2^{ei – n} * 2^{n} = 2^{ei – n + n} = 2^{ei}

Because *e*_{i} – 1 is an integer and *e*_{i} – 1 > 0, since *e*_{i} is an integer and *e*_{i} > 1, by result 2, it follows that:

2^{ei} ≥ 2^{ei – 1}

Because *e*_{i} – 1 is an integer and *e*_{i} – 1 > 0, since *e*_{i} is an integer and *e*_{i} > 1, by result 7, it follows that:

2^{ei – 1} ≥ *e*_{i} = emax(*m*)

**Result 27**

*s* * φ(*m*) ≥ emax(*m*), where *m* is an integer and *m* ≥ 1, and where *s* is a an integer and *s* ≥ 1, and where emax(*m*) ≥ 2

Given that *m* is an integer and *m* ≥ 1, and given that emax(*m*) ≥ 2, we know that *m* has a non-empty prime factorization. If the prime factorization of *m* is the set of *n* prime integer factors, {*p*_{1}, *p*_{2}, …, *p*_{n}}, with corresponding exponents, [*e*_{1}, *e*_{2}, …, *e*_{n}], then *m* is composed of these prime factors like so:

*m* = *p*_{1}^{e1} * *p*_{2}^{e2} * … * *p*_{n}^{en}

There must be some prime factor of *m*, *p*_{i}, where *i* is an integer and 1 ≤ *i* ≤ *n*, such that the corresponding exponent *e*_{i} = emax(*m*). Because all of the prime factors of *m* are positive integer powers of positive integers, by result 3.5, they must be at least 1. Therefore:

*m* ≥ *p*_{i}^{ei}

Because *p*_{i} is a prime integer, *p*_{i} ≥ 2. Given that *e*_{i} is an integer and *e*_{i} = emax(*m*) ≥ 2, by result 3, it follows that:

*p*_{i}^{ei} ≥ 2^{ei}

Given that *e*_{i} is an integer and *e*_{i} = emax(*m*) ≥ 2, by result 3, it follows that:

2^{ei} ≥ 2^{2} = 4

Given that *m* is an integer and because *m* ≥ 4, by result 23, it follows that:

φ(*m*) ≥ *p*_{i}^{ei – 1}

where *p*_{i} is the *i*^{th} prime factor of *m* and *e*_{i} is the exponent corresponding to *p*_{i} in the prime factorization of *m*. If we choose *i* such that *e*_{i} = emax(*m*), then *e*_{i} is an integer and *e*_{i} = emax(*m*) ≥ 2. Therefore, by result 7, since *p*_{i} is a prime integer and therefore *p*_{i} ≥ 2, it follows that:

*p*_{i}^{ei – 1} ≥ *e*_{i} = emax(*m*)

Given that *s* ≥ 1, and because φ(*m*) ≥ emax(*m*) ≥ 2, it follows that:

*s* * φ(*m*) ≥ emax(*m*)

**Result 28**

*a* ≡ *b* (mod *c*), where *a*, *b*, *c*, and *d* are integers, and where *c* divides *d*, and where *a* ≡ *b* (mod *d*)

If *a* is congruent with *b*, mod *d*, then this means that there is some integer, *e* such that the following is true:

*a* = *b* + (*e* * *d*)

If *c* divides *d* then there is some integer *f* such that the following is true:

*d* = *f* * *c*

We can therefore substitute *f* * *c* for *d* in the first equation which gives us this:

*a* = *b* + (*e* * *f* * *c*)

If we say that *g* = *e* * *f*, we know that *g* is an integer because *e* and *f* are integers, and therefore, *g* is the product of two integers. We can then substitute *g* into this last equation which gives us this:

*a* = *b* + (*g* * *c*)

This is exactly the definition of congruence between *a* and *b*, mod *c*. Therefore:

*a* ≡ *b* (mod *c*)

**Result 29**

*a*^{n} ≡ *b*^{n} (mod *m*), where *a*, *b*, *n*, and *m* are integers, and where *a* ≥ 0, and where *n* ≥ 0, and *m* ≥ 1, and where *a* ≡ *b* (mod *m*), and where if *n* = 0 then *a* ≠ 0 and *b* ≠ 0

If *n* = 0, given that *a* ≠ 0 and *b* ≠ 0 in this case, the result is trivial because:

*a*^{n} = *a*^{0} = 1 = *b*^{0} = *b*^{n}

and it follows that:

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

If *n* > 0, then because *a* is congruent with *b*, mod *m*, then there exists some integer, *d*, such that:

*a* = *b* + (*d* * *m*)

If *b* = 0 then, because *n* > 0, *b*^{n} = 0^{n} = 0.

Furthermore:

*a* = 0 + (*d* * *m*) = *d* * *m*

Therefore:

*a*^{n} = (*d* * *m*)^{n} = *d*^{n} * *m*^{n}

If we divide *d*^{n} * *m*^{n} by *m*, we get:

(*d*^{n} * *m*^{n}) / *m* = *d*^{n} * *m*^{n – 1}

Because *d* is an integer, and since *n* is an integer and *n* > 0, by result 3.5, it follows that *d*^{n} is an integer. Given that *n* is an integer and because *n* > 0, *n* – 1 is an integer and *n* – 1 ≥ 0. Given that *m* is an integer and *m* ≥ 1, by result 3.5, it follows that *m*^{n – 1} is an integer. Therefore, *d*^{n} * *m*^{n – 1} is an integer, which means that *m* divides *a*^{n}. Therefore:

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

If *b* ≠ 0, we can show the result using the binomial expansion of *a*^{n}:

a^n = (b + (d*m))^n = \sum_{k=0}^n\binom{n}{k}b^{n-k}(d*m)^k

Because *n* > 0, we can pull the first term of the summation out, which gives us this:

\sum_{k=0}^n\binom{n}{k}b^{n-k}(d*m)^k = \binom{n}{0}b^{n-0}(d*m)^0 + \sum_{k=1}^n \binom{n}{k}b^{n-k}(d*m)^k

Because \binom{n}{0} = 1, and (d*m)^0 = 1, it follows that:

\binom{n}{0}b^{n-0}(d*m)^0 + \sum_{i=1}^n \binom{n}{k}b^{n-k}(d*m)^k

= 1 * b^n * 1 + \sum_{k=1}^n \binom{n}{k}b^{n-k}(d*m)^k

= b^n + \sum_{k=1}^n \binom{n}{k}b^{n-k}(d*m)^k

Given that *n* and *k* are integers and because *n* ≥ *k*, *n* – *k* ≥ 0. Therefore, given that *b* is an integer, by result 3.5, *b*^{n – k} is an integer. Because *d* is an integer and given that *m* is an integer, *d* * *m* is an integer. Therefore, since *k* ≥ 1, by result 3.5, (*d***m*)^{k} is an integer. Furthermore, (*d***m*)^{k} is a multiple of *m* because (*d***m*)^{k} = *d*^{k} * *m*^{k}, which is an integer multiple of a positive integer power of *m*. Note, also, that \binom{n}{k} is a positive integer. Therefore, all of the terms in the final summation, above, are integer multiples of *m*.

Because all of the terms in the final summation are integer multiples of *m*, there exists some integer, *e*, such that:

e * m = \sum_{i=1}^n \binom{n}{k}b^{n-k}(d*m)^k

Therefore:

*a*^{n} = *b*^{n} + (*e* * *m*)

This matches exactly the definition of congruence between *a*^{n} and *b*^{n}, mod *m*.

Therefore:

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

Now we’re ready to prove the recursive congruence of exponents.

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

where *A* is a finite sequence of *n* integers, *A* = [*a*_{1}, *a*_{2}, …, *a*_{n}], where *n* ≥ 1, and if *n* > 1 where *a*_{i} ≥ 0 for *i* in the range 2 ≤ *i* ≤ *n*, and no two consecutive elements of *A* are 0, and where *b*, *c*, and *m* are integers and *b* ≥ 1, and *c* ≥ 1, and *m* ≥ 1

We will first prove the above congruence assuming that all elements of *A* are non-negative, including *a*_{1}, and then show at the end that the result is the same when *a*_{1} < 0.

### When *a*_{1} ≥ 0

By result 17, φ_{n}(*m*) is an integer and φ_{n}(*m*) ≥ 1, given that *n* and *m* are integers and *n* ≥ 1 and *m* ≥ 1. Because *b* and *c* are both integers and that *b* ≥ 1 and *c* ≥ 1, *b* * φ_{n}(*m*) and *c* * φ_{n}(*m*) are both integers and *b* * φ_{n}(*m*) ≥ 1 and *c* * φ_{n}(*m*) ≥ 1. Given that all elements of *A* are integers that are at least 0, and that there are no two consecutive elements of *A* are 0, it follows that all elements of *A* ++ [*b* * φ_{n}(*m*)] and *A* ++ [*c* * φ_{n}(*m*)] are integers and that there are no two consecutive elements of either *A* ++ [*b* * φ_{n}(*m*)] or *A* ++ [*c* * φ_{n}(*m*)] that are 0. Therefore, by result 11, it follows that both ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are defined. Because ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are defined and all elements of *A* ++ [*b* * φ_{n}(*m*)] and *A* ++ [*c* * φ_{n}(*m*)] are integers that are at least 0, by result 16, ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are integers.

### ψ(*A*, *b*, *m*) and ψ(*A*, *c*, *m*) are defined

These equalities follow from the definition of the ψ function:

ψ(*A*, *b*, *m*) = ρ(*A* ++ [*b* * φ_{n}(*m*)])

ψ(*A*, *c*, *m*) = ρ(*A* ++ [*c* * φ_{n}(*m*)])

We’ve already shown that ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are defined. Therefore, both ψ(*A*, *b*, *m*) and ψ(*A*, *c*, *m*) are defined.

### When *m* = 1

The case when *m* = 1 is trivial. Because 1 divides all integers, all integers are congruent with all other integers, mod 1. These equalities follow from the definition of the ψ function:

ψ(*A*, *b*, *m*) = ρ(*A* ++ [*b* * φ_{n}(*m*)])

ψ(*A*, *c*, *m*) = ρ(*A* ++ [*c* * φ_{n}(*m*)])

We’ve already shown that ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are integers. Therefore, they are congruent with one another, mod 1.

*a*_{i} = 0

Remember from the definition of ψ that ψ(*A*, *s*, *m*) = ρ(*A* ++ [*s* * φ_{n}(*m*)]).

If there is some element of *A*, *a*_{i}, where *i* is an integer in the range 1 ≤ *i* ≤ *n*, and where *a*_{i} = 0, then by result 15, since ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are defined, it follows that:

ρ(*A* ++ [*b* * φ_{n}(*m*)]) = ρ(*A* ++ [*c* * φ_{n}(*m*)]) = ρ(*A*_{–i})

Therefore:

ψ(*A*, *b*, *m*) = ψ(*A*, *c*, *m*)

and it follows that:

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

### When *a*_{i} = 1

If there is some element of *A*, *a*_{i}, where *i* is an integer in the range 1 ≤ *i* ≤ *n*, and where *a*_{i} = 1, then by result 14, since ρ(*A* ++ [*b* * φ_{n}(*m*)]) and ρ(*A* ++ [*c* * φ_{n}(*m*)]) are defined, it follows that:

ρ(*A* ++ [*b* * φ_{n}(*m*)]) = ρ(*A* ++ [*c* * φ_{n}(*m*)]) = ρ(*A*_{–i})

Therefore:

ψ(*A*, *b*, *m*) = ψ(*A*, *c*, *m*)

and it follows that:

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

### When *b* = *c*

If *b* = *c*, then we again have a similar situation. In this case:

ρ(*A* ++ [*b* * φ_{n}(*m*)]) = ρ(*A* ++ [*c* * φ_{n}(*m*)])

and therefore:

ψ(*A*, *b*, *m*) = ψ(*A*, *c*, *m*)

and it follows that:

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

### When *a*_{i} ≥ 2, *b* ≠ *c*

For the case when *m* > 1, and when all elements of *A* are greater than or equal to 2 and when *b* ≠ *c*, we will use mathematical induction using the length of the trailing sub-sequence of *A* as the induction variable. The basis statement is this:

P(1):

Note that when the length of the trailing sub-sequence of *A* is 1, we are referring to *A*_{n}. Additionally, by the time we have traversed *A* recursively using the ψ function to reach *A*_{n}, we will have applied Euler’s totient function *n* – 1 times, since there are *n* – 1 elements of *A* before *a*_{n}. Therefore what we need to show for the basis case is this:

ψ(*A*_{n}, *b*, φ_{n – 1}(*m*)) ≡ ψ(*A*_{n}, *c*, φ_{n – 1}(*m*)) (mod φ_{n – 1}(*m*))

Based on the definition of the ψ function, this expands to:

*a*_{n}^{(b * φ(φn – 1(m)))} ≡ *a*_{n}^{(c * φ(φn – 1(m)))} (mod φ_{n – 1}(*m*))

If we substitute *m’* for φ_{n – 1}(*m*), the above congruence becomes:

*a*_{n}^{(b * φ(m’))} ≡ *a*_{n}^{(c * φ(m’))} (mod *m’*)

This will be shown using the congruence of exponents, which means we must show the following are all true:

*b* * φ(*m’*) ≥ emax(*m’*)
*c* * φ(*m’*) ≥ emax(*m’*)
*b* * φ(*m’*) ≡ *c* * φ(*m’*) (mod λ(*m’*))

Note that when *m* > 1, *m* has a non-empty prime factorization and therefore emax(*m*) ≥ 1.

Because *m’* = φ_{n – 1}(*m*), φ(*m’*) = φ_{n}(*m*). Given that *n* and *m* are integers and that *n* ≥ 1 and *m* ≥ 1, by result 17, it follows that φ(*m’*) is an integer and φ(*m’*) ≥ 1. Given that *b* and *c* are integers and that *b* ≥ 1 and that *c* ≥ 1, it follows that *b* * φ(*m’*) ≥ 1 and that *c* * φ(*m’*) ≥ 1.

If emax(*m’*) = 0 or emax(*m’*) = 1, then we already know that *b* * φ(*m’*) ≥ emax(*m’*) = 1 and *c* * φ(*m’*) ≥ emax(*m’*) = 1.

Given that *b* and *c* are integers and *b* ≥ 1 and *c* ≥ 1, and since φ(*m’*) is an integer and φ(*m’*) ≥ 1 and since emax(*m’*) ≥ 2, by result 27, it follows that:

*b* * φ(*m’*) ≥ emax(*m’*)

*c* * φ(*m’*) ≥ emax(*m’*)

Because λ(*m’*) divides φ(*m’*), since *m’* is an integer and *m’* ≥ 1, there exists some integer, *d*, such that:

φ(*m’*) = *d* * λ(*m’*)

If we multiply both sides of this equation by *b* or *c*, we get this:

*b* * φ(*m’*) = *b* * *d* * λ(*m’*)

*c* * φ(*m’*) = *c* * *d* * λ(*m’*)

We can add 0 to the right hand side of these equations and we get:

*b* * φ(*m’*) = 0 + (*b* * *d* * λ(*m’*))

*c* * φ(*m’*) = 0 + (*c* * *d* * λ(*m’*))

Because *b*, *c*, and *d* are integers and because λ(*m’*) is an integer, since *m’* is an integer and *m’* ≥ 1, it follows that *b* * *d* and *c* * *d* are integers. Therefore:

*b* * φ(*m’*) ≡ *c* * φ(*m’*) ≡ 0 (mod λ(*m’*))

The induction hypothesis is this:

P(*k*):

ψ(*A*_{n – (k – 1)}, *b*, φ_{n – k}(*m*)) ≡ ψ(*A*_{n – (k – 1)}, *c*, φ_{n – k}(*m*)) (mod φ_{n – k}(*m*)), where *k* is an integer and 1 ≤ *k* < *n*

Note that when *k* = 1, the induction hypothesis simplifies to the basis statement because *n* = *n* – (1 – 1).

The induction step is this:

P(*k* + 1):

In the induction step we must show that:

ψ(*A*_{n – ((k + 1) – 1)}, *b*, φ_{n – (k + 1)}(*m*)) ≡ ψ(*A*_{n – ((k + 1) – 1)}, *c*, φ_{n – (k + 1)}(*m*) (mod φ_{n – (k + 1)}(*m*))

Because *k* = (*k* + 1) – 1, this can be simplified to:

ψ(*A*_{n – k}, *b*, φ_{n – (k + 1)}(*m*)) ≡ ψ(*A*_{n – k}, *c*, φ_{(n – (k + 1)}(*m*)) (mod φ_{n – (k + 1)}(*m*))

Based on the definition of the ψ function, we can restate the above like so:

*a*_{n – k}^{ψ(A(n – k) + 1, b, φ(φ(n – (k + 1)(m)))} ≡ *a*_{n – k}^{ψ(A(n – k) + 1, c, φ(φn – (k + 1)(m)))} (mod φ_{n – (k + 1)}(*m*))

Because (*n* – *k*) + 1 = *n* – (*k* – 1), this is equivalent to:

*a*_{n – k}^{ψ(An – (k – 1), b, φ(φ(n – (k + 1)(m)))} ≡ *a*_{n – k}^{ψ(An – (k – 1), c, φ(φn – (k + 1)(m)))} (mod φ_{n – (k + 1)}(*m*))

If we substitute *m’* for φ_{(n – (k + 1))}(*m*) in the above congruence, we get something much more manageable:

*a*_{n – k}^{ψ(An – (k – 1), b, φ(m’)} ≡ *a*_{n – k}^{ψ(An – (k – 1), c, φ(m’)} (mod *m’*)

To show this congruence, we will use the congruence of exponents and we therefore need to show that all of the following are true:

- ψ(
*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≥ emax(*m’*)
- ψ(
*A*_{n – (k – 1)}, *c*, φ(*m’*)) ≥ emax(*m’*)
- ψ(
*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≡ ψ(*A*_{n – (k – 1)}, *c*, φ(*m’*)) (mod λ(*m’*))

It must be the case that either O(*A*_{n – (k – 1)}) ≥ emax(*m’*) or O(*A*_{n – (k – 1)}) < emax(*m’*).

In either case, since *k* = O(*A*_{n – (k – 1)}) and *k* ≥ 1, and since all elements of *A*_{n – (k – 1)} are integers and are at least 2, by result 11, ρ(*A*_{n – (k – 1)}) is defined.

Additionally, because *m’* = φ_{(n – (k + 1))}(*m*), given that *n*, *k*, and *m* are integers and that *n* – (*k* + 1) ≥ 0 given that *n* > *k*, by result 17, it follows that *m’* is an integer and *m’* ≥ 1.

If O(*A*_{n – (k – 1)}) ≥ emax(*m’*), since ρ(*A*_{n – (k – 1)}) is defined, and since all elements of *A*_{n – (k – 1)} are integers that are at least 2, and given that *b* and *c* are integers and *b* ≥ 1 and *c* ≥ 1, and since *m’* is an integer and *m’* ≥ 1, then by result 24, it follows that:

ψ(*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≥ emax(*m’*)

ψ(*A*_{n – (k – 1)}, *c*, φ(*m’*)) ≥ emax(*m’*)

If O(*A*_{n – (k – 1)}) < emax(*m’*), since ρ(*A*_{n – (k – 1)}) is defined, and since all elements of *A*_{n – (k – 1)} are integers that are at least 2, and given that *b* and *c* are integers and *b* ≥ 1 and *c* ≥ 1, and since *m’* is an integer and *m’* ≥ 1, then by result 26:

ψ(*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≥ emax(*m’*)

ψ(*A*_{n – (k – 1)}, *c*, φ(*m’*)) ≥ emax(*m’*)

We still need to show that the following is true:

ψ(*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≡ ψ(*A*_{n – (k – 1)}, *c*, φ(*m’*)) (mod λ(*m’*))

Remember how we defined *m’*:

*m’* = φ_{n – (k + 1)}(*m*)

This means that:

φ(*m’*) = φ(φ_{n – (k + 1)}(*m*)) = φ_{(n – (k + 1) + 1)}(*m*) = φ_{((n – k) – 1) + 1)}(*m*) = φ_{n – k}(*m*)

If we substitute *m’* for φ_{n – (k + 1)}(*m*) and φ(*m’*) for φ_{n – k}(*m*) in the induction hypothesis statement, we get this:

ψ(*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≡ ψ(*A*_{n – (k – 1)}, *c*, φ(*m’*)) (mod φ(*m’*))

The only difference, now, between what we need to show and the induction hypothesis is the modulus value. We’ve already shown that *m’* is an integer and *m’* ≥ 1. Therefore, λ(*m’*) divides φ(*m’*). Therefore, by result 28:

ψ(*A*_{n – (k – 1)}, *b*, φ(*m’*)) ≡ ψ(*A*_{n – (k – 1)}, *c*, φ(*m’*)) (mod λ(*m’*))

### When *a*_{1} < 0

So far we’ve shown the result is true for all positive values of *m*, and in all cases when the elements of *A* are non-negative. We haven’t yet shown the result is true when *a*_{1} < 0. Because *a*_{1} is never used as an exponent, it can be negative without us having to deal with non-integers.

If *a*_{1} < 0, there must exist some integer, *d*, where *d* > 0, such that:

*a*_{1} ≡ *d* (mod *m*)

If *n* = 1, then the definition of the ψ function gives us this:

ψ(*A*, *b*, *m*) = *a*_{1}^{b * φ(m)}

ψ(*A*, *c*, *m*) = *a*_{1}^{c * φ(m)}

Note that because *d* is an integer and *d* > 0, and given that *b*, *c*, and *m* are integers and *b* ≥ 1 and *c* ≥ 1 and *m* ≥ 1, we’ve already shown this to be true:

ψ([*d*], *b*, *m*) ≡ ψ([*d*], *c*, *m*) (mod *m*)

Given that *m* is an integer and *m* ≥ 1, φ(*m*) is an integer and φ(*m*) ≥ 1. Given that *b* and *c* are integers and that *b* ≥ 1 and that *c* ≥ 1, it follows that *b* * φ(*m*) and *c* * φ(*m*) are integers and that *b* * φ(*m*) ≥ 1 and that *c* * φ(*m*) ≥ 1. Given that *a*_{1} is an integer and *d* is an integer and *d* > 0, and given that *a*_{1} ≡ *d* (mod *m*), by result 29, it follows that:

*a*_{1}^{b * φ(m)} ≡ *d*^{b * φ(m)} (mod *m*)

*a*_{1}^{b * φ(m)} ≡ *d*^{c * φ(m)} (mod *m*)

Therefore:

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

If *n* > 1, then the definition of the ψ function gives us this:

ψ(*A*, *b*, *m*) = *a*_{1}^{ψ(A2, b, φ(m))}

ψ(*A*, *c*, *m*) = *a*_{1}^{ψ(A2, c, φ(m))}

Because *d* > 0 and the elements of *A*_{2} are integers that are at least 0, and no two consecutive elements of *A*_{2} are 0, and *b*, *c*, and *m* are integers and *b* ≥ 1 and *c* ≥ 1 and *m* ≥ 1, the following has already been shown to be true:

ψ([*d*] ++ *A*_{2}, *b*, *m*) ≡ ψ([*d*] ++ *A*_{2}, *c*, *m*) (mod *m*)

By the definition of the ψ function:

ψ([*d*] ++ *A*_{2}, *b*, *m*) = *d*^{ψ(A2, b, φ(m))}

ψ([*d*] ++ *A*_{2}, *c*, *m*) = *d*^{ψ(A2, c, φ(m))}

Also by the definition of the ψ function:

ψ(*A*_{2}, *b*, φ(*m*)) = ρ(*A*_{2} ++ [*b* * φ_{n – 1}(*m*)])

ψ(*A*_{2}, *c*, φ(*m*)) = ρ(*A*_{2} ++ [*c* * φ_{n – 1}(*m*)])

Given that *m* is an integer and *m* ≥ 1, and since *n* – 1 is an integer and *n* – 1 > 0, given that *n* is an integer and *n* > 1, by result 17, it follows that φ_{n – 1}(*m*) is an integer and φ_{n – 1}(*m*) ≥ 1. Given that *b* and *c* are integers and that *b* ≥ 1 and that *c* ≥ 1, it follows that *b* * φ_{n – 1}(*m*) and *c* * φ_{n – 1}(*m*) are integers and that *b* * φ_{n – 1}(*m*) ≥ 1 and that *c* * φ_{n – 1}(*m*) ≥ 1. Since all the elements of *A*_{2} are integers that are at least 0 and no two consecutive elements of *A*_{2} are 0, by result 11, ρ(*A*_{2} ++ [*b* * φ_{n – 1}(*m*)]) is defined and ρ(*A*_{2} ++ [*c* * φ_{n – 1}(*m*)]) is defined. Therefore, by result 16, ρ(*A*_{2} ++ [*b* * φ_{n – 1}(*m*)]) and ρ(*A*_{2} ++ [*c* * φ_{n – 1}(*m*)]) are integers and ρ(*A*_{2} ++ [*b* * φ_{n – 1}(*m*)]) ≥ 0 and ρ(*A*_{2} ++ [*c* * φ_{n – 1}(*m*)]) ≥ 0.

Because ψ(*A*_{2}, *b*, φ(*m*)) and ψ(*A*_{2}, *c*, φ(*m*)) are integers and ψ(*A*_{2}, *b*, φ(*m*)) ≥ 0 and ψ(*A*_{2}, *c*, φ(*m*)) ≥ 0, and given that *a*_{1} is an integer and *d* is an integer and *d* > 0, and given that *m* is an integer and *m* ≥ 1, and given that *a*_{1} ≡ *d* (mod *m*), by result 29, it follows that:

*a*_{1}^{ψ(A2, b, φ(m))} ≡ *d*^{ψ(A2, b, φ(m))} (mod *m*)

*a*_{1}^{ψ(A2, c, φ(m))} ≡ *d*^{ψ(A2, c, φ(m))} (mod *m*)

Therefore:

ψ(*A*, *b*, *m*) ≡ ψ(*A*, *c*, *m*) (mod *m*)

This completes the proof.

## Conclusion

If you’ve read this far, even if you’ve skipped some parts or skimmed others, I thank you for your attention to such a long-winded explanation. If you have any questions, please leave them in comments and I’d be happy to answer them or clarify anything that is confusing. Any relevant feedback is welcome!

I apologize if I’ve been more explicit than necessary or if I’ve expanded the verbosity of the proof here by repeating things already proven many other times. My goal was to reduce the proof as far as possible to basic axioms and not rely on external references that may or may not be available at a later time. Also, I had the goal of making the explanation accessible to people who are not very familiar with the subjects involved and yet have it also be complete and accurate. Keep in mind that I’m not a mathematician when offering criticism.

In my next post, I plan to show how the *recursive congruence of exponents* could possibly be used in integer factorization.