Mathematics, Number Theory

Recursive congruence of exponents

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:

abac (mod m)

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

  • bc (mod λ(m))
  • bemax of m
  • cemax of m

where λ is the Carmichael function, and emax 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 emax of m. Throughout the discussion, I’ll use the following function:

emax(m) = emax of m

where emax 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, pe, Euler’s totient can be calculated like so:

φ(pe) = pepe – 1

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

φ(pe) = pe * ((p – 1) / p) = pe * (1 / p) * (p – 1) = pe – 1 * (p – 1)

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

φ(pq) = φ(p)φ(q)

Therefore, if a positive integer, m, has n prime factors, {p1, p2, …, pn}, with corresponding exponents, [e1, e2, …, en], such that:

m = p1e1 * p2e2 * … * pnen

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

φ(m) = φ(p1e1) * φ(p2e2) * … * φ(pnen)
= p1e1 – 1 * (p1 – 1) * p2e2 – 1 * (p2 – 1) * … * pnen – 1 * (pn – 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, {p1, p2, …, pn}, with corresponding exponents, [e1, e2, …, en], such that:

m = p1e1 * p2e2 * … * pnen

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

λ(m) = lcm(λ(p1e1), λ(p2e2), …, λ(pnen))

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

x2 > 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):

22 = 4 > 2 + 1 = 3

The induction hypothesis is this:

P(k):

k2 > k + 1, where k is an integer and k ≥ 2

Now the induction step:

P(k + 1):

(k + 1)2 = k2 + 2k + 1

By the induction hypothesis:

k2 + 2k + 1 > k + 1 + 2k + 1 = 2k + k + 2

Because 2k > 0, since k ≥ 2:

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

Result 1.5

xn ≥ 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):

x0 = 1

The induction hypothesis is this:

P(k):

xk ≥ 1, where k is an integer and k ≥ 0

The induction step is this:

P(k + 1):

xk + 1 = x * xk

Because x ≥ 1, and by the induction hypothesis, xk ≥ 1, it follows that:

x * xk ≥ 1

Result 2

xnxm, where x is an integer and x ≥ 1, and where n and m are integers and nm ≥ 0

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

xnm ≥ 1

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

xnm * xm ≥ 1 * xm

This simplifies to:

xnxm

Result 3

xnyn, where x and y are integers and xy ≥ 1, and where n is an integer and n ≥ 0

If n = 0, x0 = 1 = y0.

If n = 1, x1 = xy = y1, which matches the precondition of xy.

If x = y, xn = yn.

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

xn = (y + (xy))nyn

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, ynk ≥ 1, since y is an integer and y ≥ 1 and nk ≥ 1, given that n and k are integers and n – 1 ≥ k. Also, by result 1.5, (xy)k ≥ 1, since k is an integer and k ≥ 1, and since xy is an integer and xy ≥ 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, (xy)n ≥ 1, since xy is an integer and xy ≥ 1, given that x and y are integers and x > y, and since n is an integer and n ≥ 2. Therefore:

xn > yn + (xy)n > yn

Result 3.5

xn 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, xn = x0 = 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):

x1 = x

It was given that x is an integer, therefore x1 is an integer.

The induction hypothesis is this:

P(k):

xk is an integer, where k is an integer and k ≥ 1

The induction step is this:

P(k + 1):

xk + 1 = x * xk

It was given that x is an integer and by the induction hypothesis, xk is an integer. Therefore, x * xk 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:

pe – 2 ≥ 2e – 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 pe – 2 is an integer and 2e – 2 is an integer, and it follows from result 1.5 that pe – 2 ≥ 1 and that 2e – 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) = 21 = 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 2k – 1 = 2*2k – 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, 2k – 2 ≥ 1 and by result 3.5, 2k – 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))2k2

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

k2k + 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

xn – 1n, 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:

xn – 1 ≥ 2n – 1

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

The basis case is this:

P(1):

21 – 1 = 20 = 1

The induction hypothesis is this:

P(k):

2k – 1k, where k is an integer and k ≥ 1

Now the induction step:

P(k + 1):

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

By the induction hypothesis, since k ≥ 1:

2*2k – 1 ≥ 2k = k + k

Because k ≥ 1:

k + kk + 1

Proof

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 22φ(φ(m)) are integers and by result 1.5, 2φ(φ(m)) ≥ 1 and 22φ(φ(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)
  • 22φ(φ(m)) ≥ emax(m)
  • 2φ(φ(m)) ≡ 22φ(φ(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, {p1, p2, …, pn}, with corresponding exponents, [e1, e2, …, en], then we can represent m like so:

m = p1e1 * p2e2 * … * pnen

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

φ(m) = φ(p1e1) * φ(p2e2) * … * φ(pnen)

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

emax(m) = max(e1, e2, …, en)

Let’s look now more closely at φ(m) and its relationship to pi.

φ(m) = φ(p1e1) * φ(p2e2) * … * φ(piei) * … * φ(pnen)
= p1e1 – 1 * (p1 – 1) * p2e2 – 1 * (p2 – 1) * … * piei – 1 * (pi – 1) * … * pnen – 1 * (pn – 1)

Because ei = emax(m) ≥ 2, ei – 1 ≥ 1. From this, it is clear that pi is one of the prime factors of φ(m) and that the exponent of pi in the prime factorization of φ(m) is at least ei – 1. Note that the exponent of pi in the prime factorization of φ(m) may be more than ei – 1 if pi 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, …, pi, …, p’n’}, with corresponding exponents, [e’1, e’2, …, e’i, …, e’n’] such that e’iei – 1 ≥ 1, then φ(m) can be represented like so:

φ(m) = p’1e’1 * p’2e’2 * … * pie’i * … * p’n’e’n’

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

φ(φ(m)) = φ(p’1e’1) * φ(p’2e’2) * … * φ(pie’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)) ≥ φ(pie’i) = pie’i – 1 * (pi – 1)

Because pi is a prime integer, pi ≥ 2 and, therefore, pi – 1 ≥ 1. Because e’i is an integer and e’iei – 1 and ei = emax(m) ≥ 2, it follows that e’i – 1 ≥ 0 and e’i – 1 is an integer. Therefore, by result 1.5, pie’i – 1 ≥ 1. Therefore:

φ(φ(m)) ≥ pie’i – 1 * (pi – 1) ≥ pie’i – 1

Because e’iei – 1, it follows that e’i – 1 ≥ ei – 2. Because e’i and ei are integers, it follows that e’i – 1 and ei – 2 are both integers. Because ei = emax(m) ≥ 2, it follows that ei – 1 ≥ ei – 2 ≥ 0. Because pi is a prime integer, pi ≥ 2. Therefore, by result 2, it follows that:

φ(φ(m)) ≥ pie’i – 1piei – 2

Because pi is a prime integer, pi ≥ 2. Therefore, because ei – 2 is an integer and ei – 2 ≥ 0, by result 1.5, it follows that piei – 2 is an integer, and it follows from result 3.5, that piei – 2 ≥ 1. Because φ(φ(m)) is an integer and φ(φ(m)) ≥ piei – 2, by result 2, it follows that:

2φ(φ(m)) ≥ 2piei – 2

By result 4, since pi is a prime integer and ei is an integer and ei ≥ 2, it follows that:

2piei – 2ei = 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:

pi = pj = emax(m), where i and j are integers and 1 ≤ in and 1 ≤ in and ij

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 22φ(φ(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:

22φ(φ(m)) ≥ 2φ(φ(m)) ≥ emax(m)

Part 3

We now need to show that 2φ(φ(m)) ≡ 22φ(φ(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, {p1, p2, …, pn}, with corresponding exponents, [e1, e2, …, en], φ(m) is defined like so:

φ(m) = φ(p1e1) * φ(p2e2) * … * φ(pnen)

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(λ(p1e1), λ(p2e2), …, λ(pnen))

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 ap 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, pi, of λ(m) such that its exponent, ei = emax(λ(m)), where i is an integer and 1 ≤ in. Given the above discussion, we know that the same prime factor, pi, 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 ei.

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

φ(φ(m)) = φ(p’1e’1) * φ(p’2e’2) * … * φ(pie’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)) ≥ φ(pie’i) = pie’i – 1 * (pi – 1)

Because pi is a prime integer, it follows that pi ≥ 2 and pi – 1 ≥ 1. Because e’iei ≥ 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 pie’i – 1 ≥ 1. Therefore:

φ(φ(m)) ≥ pie’i – 1

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

pie’i – 1e’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))) = a0 = 1 ≡ a(02φ(φ(m))) = a0 = 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))) = a1 = aa(12φ(φ(m))) = a1 = 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)
  • d2φ(φ(m)) ≥ emax(m)
  • dφ(φ(m))d2φ(φ(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:

d2φ(φ(m))dφ(φ(m)) ≥ emax(m)

Part 3

The argument as to why dφ(φ(m))d2φ(φ(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)) ≡ 22φ(φ(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:

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

a1(a2(…anbφ(φ(…(φ(m))))))a1(a2(…ancφ(φ(…(φ(m)))))) (mod m)

where A is a finite sequence of n integers, A = [a1, a2, …, an], 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 ai ≥ 0 where i is an integer in the range 2 ≤ in, 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 = [a1, a2, …, an], 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 = [a1, a2, …, an], I will use the notation Ai to denote the sub-sequence of A beginning with the ith element to the nth element, in the same order as they occur in A, where i is an integer in the range 1 ≤ in, using 1-based indexing.

Additionally, for the leading sub-sequence of A from the 1st element to the ith element in the same order as they occur in A, I will use the notation Ai, where i is an integer in the range 1 ≤ in, using 1-based indexing.

The following identities follow from these definitions:

A1 = A
O(A1) = O(A)
O(AO(A)) = 1
O(A-1) = 1
O(A-O(A)) = O(A)
O(Ai) = O(A) – (i – 1)
O(Ai) = 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 = [a1, a2, …, an], and a second finite sequence, B, with m elements, B = [b1, b2, …, bm], I will use the notation C = A ++ B to indicate that C is the finite sequence with n + m elements, [c1, c2, …, cn, cn + 1, cn + 2, …, cn + m], where ci = ai for all integers, i, in the range 1 ≤ in and cn + j = bj for all integers, j, in the range 1 ≤ jm.

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 = [a1, a2, …, an], the term D = A ++ [x] indicates that D is the finite sequence with n + 1 elements, D = [d1, d2, …, dn, dn + 1], where di = ai for all integers, i, in the range 1 ≤ in, and dn + 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 = [a1, a2, …, an]. 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 = [a1, a2, a3], where a2 ≠ 0:

ρ(A) = a1(ρ(A2)) = a1(a2(ρ(A3))) = a1(a2(a3))

Note that for a finite sequence, A, of n integers, ρ(A) being defined implies that ρ(Ai) is also defined for all integers, i, in the range 1 ≤ in. For a finite sequence, A, of n integers, A = [a1, a2, …, an], where n > 0, if for some integer i where 1 ≤ i < n, ai = 0 and ρ(Ai + 1) ≤ 0, ρ(A) is undefined because ρ(Ai) is undefined because ρ(Ai) 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 = [a1, a2, …, an], where ρ(A) is defined, but will first raise the final element of A, being an, 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 = [a1, a2], and integer, s, and positive integer, m, ψ(A, s, m) evaluates to this:

ψ(A, s, m) = a1(a2(sφ(φ(m)))))

Note that the following identity follows from the definition of ψ. For a given finite sequence, A, of n integers, A = [a1, a2, …, an], 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 = [a1, a2, …, an], where ρ(A) is defined, and where if n > 1 then ai ≥ 0 for each integer, i, in the range 2 ≤ in, 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 = [a1, a2, …, an], and where ρ(A) is defined, and where a1 = 0

If O(A) = 1, ρ(A) = a1 = 0.

If O(A) > 1, because ρ(A) is defined, we know that ρ(A2) is defined, and we know that ρ(A2) > 0, since a1 = 0. Because 0 raised to any positive power is 0, it follows that:

ρ(A) = a1ρ(A2) = 0ρ(A2) = 0

Result 9

x * yx + 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) – xy + 1 ≥ 1

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

x * yx + y

Result 10

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

If n = 1, then ρ(A) = a1 ≥ 1.

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

a1ρ(A2)a10 = 1

Result 11

ρ(A) is defined, where A is a finite sequence of n integers, A = [a1, a2, …, an], and where n > 0, and where ai ≥ 0 for all integers, i, in the range 1 ≤ in, and where no two consecutive elements of A are 0

If n = 1, then ρ(A) is defined because ρ(A) = a1.

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 An. In this case, ρ(An) is defined because ρ(An) = an.

The induction hypothesis is this:

P(k):

ρ(An – (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):

ρ(An – ((k + 1) – 1)) = ρ(Ank) = ankρ(A(nk) + 1) = ankρ(An – (k – 1))

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

If ank ≥ 1, then ρ(Ank) is defined because, by the induction hypothesis, ρ(An – (k – 1)) is defined.

This implies that the result is true when k = n – 1, which is when Ank = A1 = A. Therefore, ρ(A) is defined.

Result 12

ρ(A) = 1, where A is a finite sequence of n integers, A = [a1, a2, …, an], where ρ(A) is defined, and where a1 = 1

If O(A) = 1, ρ(A) = a1 = 1.

If O(A) > 1, because ρ(A) is defined, ρ(A2) must also be defined. Because 1 raised to any power is 1:

ρ(A) = a1ρ(A2) = 1

Result 13

ρ(A) = ρ(B), where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and where B is a finite sequence of m integers, B = [b1, b2, …, bm], and where there is some element, ai, where i is an integer and 1 ≤ in and 1 ≤ im, where aj = bj for each integer, j, in the range 1 ≤ j < i, and where ρ(Ai) = ρ(Bi)

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

ρ(A) = ρ(A1) = ρ(B1) = ρ(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 Ai and Bi.

ρ(Ai) = ρ(Bi)

This induction hypothesis is this:

P(k):

ρ(Aik) = ρ(Bik), 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):

ρ(Ai – (k + 1)) = ρ(A(ik) – 1) = a(ik) – 1ρ(A(ik) – 1 + 1) = a(ik) – 1ρ(Aik)
ρ(Bi – (k + 1)) = ρ(B(ik) – 1) = b(ik) – 1ρ(B(ik) – 1 + 1) = b(ik) – 1ρ(Bik)

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 (ik) – 1 < i. Therefore:

a(ik) – 1 = b(ik) – 1

Since, by the induction hypothesis, ρ(Aik) = ρ(Bik), it follows that:

a(ik) – 1ρ(Aik) = b(ik) – 1ρ(Bik)

This implies that ρ(Aik) = ρ(Bik) when k = i – 1 and ik = 1. Therefore:

ρ(A) = ρ(A1) = ρ(B1) = ρ(B)

Result 14

ρ(A) = ρ(Ai), where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and where ai = 1 for some integer, i, where 1 ≤ in

If B = Ai, where B = [b1, b2, …, bi], then bj = aj for each j in the range 1 ≤ ji. Since ai = bi = 1, by result 12, ρ(Ai) = ρ(Bi) = 1. Therefore, by result 13, since ρ(A) is defined, it follows that:

ρ(A) = ρ(B) = ρ(Ai)

Result 15

ρ(A) = ρ(Ai), where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and where ai = 0 for some integer, i, where 1 ≤ in

If B = Ai, where B = [b1, b2, …, bi], then bj = aj for each j in the range 1 ≤ ji. Since ai = bi = 0, by result 8, ρ(Ai) = ρ(Bi) = 0. Therefore, by result 13, given that ρ(A) is defined, it follows that:

ρ(A) = ρ(B) = ρ(Ai)

Result 16

ρ(A) is an integer and ρ(A) ≥ 0, where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and where ai ≥ 0, for each integer, i, in the range 1 ≤ in

If O(A) = 1, ρ(A) = a1. Because a1 is an integer and a1 ≥ 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 An.

ρ(An) = an

an is an integer and an ≥ 0, which shows that the basis statement is true.

The induction hypothesis is this:

P(k):

ρ(An – (k – 1)) is an integer and ρ(An – (k – 1)) ≥ 0, where k is an integer and 1 ≤ kn

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):

ρ(An – ((k + 1) – 1)) = ρ(Ank) = ankρ(A(nk) + 1) = ankρ(A(n – (k – 1))

If ank = 0, then, because ρ(A) is defined, ρ(An – (k – 1)) > 0. Therefore, ankρ(A(n – (k – 1)) = 0 because it is 0 raised to a positive power.

If ank ≠ 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 ankρ(A(n – (k – 1)) ≥ 1, and by result 3.5, ankρ(A(n – (k – 1)) is an integer.

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

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

xnxn, 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:

(xn / x) ≥ (xn / x)

which simplifies to:

xn – 1n

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 = [a1, a2, …, an], and where ρ(A) is defined, and ai ≥ 2 for all integers, i, in the range 1 ≤ in, and where x is an integer and x ≥ 1

If O(A) = 1:

ρ(A ++ [x]) = a1x

By result 18, given that a1 is an integer and a1 ≥ 2, and given that x is an integer and x ≥ 1, it follows that:

a1xx * a1 = x * ρ(A)

If O(A) > 1, and x = 1, it follows that x * an = an = anx and that ρ(An) = ρ(An ++ [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 An.

ρ(An ++ [x]) = anx

By result 18, given that x is an integer and x ≥ 1, and given that an is an integer and an ≥ 2:

anxx * an = x * ρ(An)

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

P(k):

The trailing sub-sequence of A with length k is An – (k – 1).

ρ(An – (k – 1) ++ [x]) ≥ x * ρ(An – (k – 1)), where k is an integer and 1 ≤ kn

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):

ρ(An – ((k + 1) – 1) ++ [x]) = ρ(Ank ++ [x]) = ankρ(A(nk) + 1 ++ [x]) = ankρ(An – (k – 1) ++ [x])

By result 16, ρ(An – (k – 1)) and ρ(An – (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, ρ(An – (k – 1) ++ [x]) ≥ x * ρ(An – (k – 1)), therefore, by result 2, given that ank is an integer and that ank ≥ 2 > 1:

ankρ(An – (k – 1) ++ [x])ank(x * ρ(An – (k – 1)))

By result 20, ρ(An – (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 * ρ(An – (k – 1)) ≥ x + ρ(An – (k – 1))

Given that x is an integer, and by result 16, ρ(An – (k – 1)) is an integer, it follows that x + ρ(An – (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, ρ(An – (k – 1)) ≥ 2, and it follows that x + ρ(An – (k – 1)) > 0. Therefore, given that ank ≥ 2, by result 2, it follows that:

ank(x * ρ(An – (k – 1)))ank(x + ρ(An – (k – 1))) = ankx * ankρ(An – (k – 1)) = ankx * ρ(Ank)

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 ank is an integer and ank ≥ 2, it follows that:

ankxankx – 1

By result 7, given that x is an integer and since x ≥ 2, and given that ank is an integer and ank ≥ 2, it follows that:

ankx – 1x

By result 20, ρ(Ank) ≥ 2, given that all elements of A are integers and at least 2. Therefore, since x ≥ 2:

ankx * ρ(Ank) ≥ x * ρ(Ank)

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

Result 20

ρ(A) ≥ 2, where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and ai ≥ 2 for all integers, i, in the range 1 ≤ in

If O(A) = 1, ρ(A) = a1 ≥ 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 An.

ρ(An) = an ≥ 2

The induction hypothesis is this:

P(k):

The trailing sub-sequence of A of length k is An – (k – 1).

ρ(An – (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):

ρ(An – ((k + 1) – 1)) = ρ(Ank) = ankρ(A(nk) + 1) = ankρ(An – (k – 1))

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

ankρ(An – (k – 1)) ≥ 2ρ(An – (k – 1))

By result 2, since ρ(An – (k – 1)) ≥ 2 by the induction hypothesis, therefore:

2(ρ(An – (k – 1))) ≥ 22 = 4 > 2

This implies that the result is true when k = n – 1, which is when Ank = A1 = A. Therefore, ρ(A) ≥ 2.

Result 21

ρ(A) ≥ 2n, where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and where ai ≥ 2 for all integers, i, in the range 1 ≤ in

If O(A) = 1, ρ(A) = a1 ≥ 2 = 21

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 An.

ρ(An) = an ≥ 2 = 21

The induction hypothesis is this:

P(k):

The trailing sub-sequence of A of length k is An – (k – 1).

ρ(An – (k – 1)) ≥ 2k, 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):

ρ(An – ((k + 1) – 1)) = ρ(Ank) = ankρ(A(nk) + 1)) = ankρ(An – (k – 1)))

By result 16, ρ(An – (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, 2k ≥ 1, and by result 3.5, 2kis an integer. Given that ank is an integer and ank ≥ 2, and by the induction hypothesis, ρ(An – (k – 1)) ≥ 2k, by result 2, it follows that:

ankρ(An – (k – 1)))ank(2k)

Given that ank is an integer and ank ≥ 2, and given that k is an integer and k ≥ 1, by result 1.5, 2k ≥ 1, and by result 3.5, 2kis an integer. By result 3, it follows that:

ank(2k) ≥ 2(2k)

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

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

This implies that the result is true when k = n – 1, which is when An – (k – 1) = A1 = A. Therefore, ρ(A) ≥ 2n.

Result 23

φ(m) ≥ piei – 1 and piei – 1 divides φ(m), where m is an integer and m ≥ 2, and where pi is the ith prime factor and ei is the exponent corresponding to pi 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, {p1, p2, …, pn}, with corresponding exponents, [e1, e2, …, en], such that:

m = p1e1 * p2e2 * … * pnen

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

φ(m) = φ(p1e1) * φ(p2e2) * … * φ(pnen)

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 ith prime factor from the set of prime integer factors of m, where 1 ≤ in, it follows that:

φ(m) ≥ φ(piei) = piei – 1 * (pi – 1)

Because pi is a prime integer, pi – 1 ≥ 1, since pi ≥ 2, and it follows that:

φ(m) ≥ piei – 1

Because φ(piei) must appear as one of the terms on the right side of the equation where we calculated φ(m), and because φ(piei) = piei – 1 * (pi – 1), we can divide both sides by piei – 1 and we get this:

φ(m) / piei – 1 = φ(p1e1) * φ(p2e2) * … * (pi – 1) * … * φ(pnen)

Because the totient of each of the prime factors of m is an integer, and pi is an integer, and therefore pi – 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 piei – 1 divides φ(m).

Result 24

ψ(A, s, φ(m)) ≥ emax(m), where A is a finite sequence of n integers, A = [a1, a2, …, an], and where ρ(A) is defined, and where s and m are integers and s ≥ 1 and m ≥ 1, and where ai ≥ 2 for all integers, i, in the range 1 ≤ in, 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) ≥ 2n

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

s * φn(m) * ρ(A) ≥ ρ(A) ≥ 2n

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

2n ≥ 2n – 1

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

2n – 1n ≥ emax(m)

Result 25

φn(m) ≥ piein and piein 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 pi is the ith integer prime factor of m and ei is the exponent corresponding to pi in the prime factorization of m, and where ei = 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) ≥ piei – 1 and piei – 1 divides φ(m).

The induction hypothesis is this:

P(k):

φk(m) ≥ pieik and pieik divides φk(m), where k is an integer and 1 ≤ kn < 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, pieik divides φk(m). Therefore, pi is one of the prime factors of φk(m) and the exponent of pi in the prime factorization of φk(m) must be at least eik. Because ei = emax(m) > nk, we know that eik > 1. Because ei and k are both integers, eik is an integer. Because pi is a prime integer,pi ≥ 2. Therefore, by result 2, it follows that:

pieik ≥ 21 = 2

Additionally, by result 3.5, pieik is an integer. Therefore, by result 23, it follows that:

φ(φk(m)) ≥ pi(eik) – 1 = piei – (k + 1) and piei – (k + 1) divides φ(φk(m))

This implies that the result is true when k = n. Therefore, φn(m) ≥ piein and piein divides φn(m).

Result 26

ψ(A, s, m) ≥ emax(m), where A is a finite sequence of n integers, A = [a1, a2, …, an], and where where ρ(A) is defined, and s and m are integers and s ≥ 1 and m ≥ 1, and where ai ≥ 2 for all integers, i, in the range 1 ≤ in, 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) ≥ 2n

By result 1.5, given that n is an integer and n ≥ 1 given that ρ(A) is defined, it follows that 2n ≥ 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) ≥ piein

where pi is the ith prime factor of m, in the prime factorization of m such that the corresponding exponent, ei = emax(m).

Because pi is a prime integer, pi ≥ 2. Because ei and n are integers and ei > n, ein is an integer and ein > 0. Therefore, by result 3, it follows that:

piein ≥ 2ein

Therefore:

φn(m) * ρ(A) ≥ 2ein * 2n = 2ein + n = 2ei

Because ei – 1 is an integer and ei – 1 > 0, since ei is an integer and ei > 1, by result 2, it follows that:

2ei ≥ 2ei – 1

Because ei – 1 is an integer and ei – 1 > 0, since ei is an integer and ei > 1, by result 7, it follows that:

2ei – 1ei = 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, {p1, p2, …, pn}, with corresponding exponents, [e1, e2, …, en], then m is composed of these prime factors like so:

m = p1e1 * p2e2 * … * pnen

There must be some prime factor of m, pi, where i is an integer and 1 ≤ in, such that the corresponding exponent ei = 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:

mpiei

Because pi is a prime integer, pi ≥ 2. Given that ei is an integer and ei = emax(m) ≥ 2, by result 3, it follows that:

piei ≥ 2ei

Given that ei is an integer and ei = emax(m) ≥ 2, by result 3, it follows that:

2ei ≥ 22 = 4

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

φ(m) ≥ piei – 1

where pi is the ith prime factor of m and ei is the exponent corresponding to pi in the prime factorization of m. If we choose i such that ei = emax(m), then ei is an integer and ei = emax(m) ≥ 2. Therefore, by result 7, since pi is a prime integer and therefore pi ≥ 2, it follows that:

piei – 1ei = emax(m)

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

s * φ(m) ≥ emax(m)

Result 28

ab (mod c), where a, b, c, and d are integers, and where c divides d, and where ab (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:

ab (mod c)

Result 29

anbn (mod m), where a, b, n, and m are integers, and where a ≥ 0, and where n ≥ 0, and m ≥ 1, and where ab (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:

an = a0 = 1 = b0 = bn

and it follows that:

anbn (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, bn = 0n = 0.

Furthermore:

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

Therefore:

an = (d * m)n = dn * mn

If we divide dn * mn by m, we get:

(dn * mn) / m = dn * mn – 1

Because d is an integer, and since n is an integer and n > 0, by result 3.5, it follows that dn 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 mn – 1 is an integer. Therefore, dn * mn – 1 is an integer, which means that m divides an. Therefore:

an ≡ 0 ≡ bn (mod m)

If b ≠ 0, we can show the result using the binomial expansion of an:

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 nk, nk ≥ 0. Therefore, given that b is an integer, by result 3.5, bnk 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 = dk * mk, 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:

an = bn + (e * m)

This matches exactly the definition of congruence between an and bn, mod m.

Therefore:

anbn (mod m)

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

Proof


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

where A is a finite sequence of n integers, A = [a1, a2, …, an], where n ≥ 1, and if n > 1 where ai ≥ 0 for i in the range 2 ≤ in, 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 a1, and then show at the end that the result is the same when a1 < 0.

When a1 ≥ 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.

ai = 0

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

If there is some element of A, ai, where i is an integer in the range 1 ≤ in, and where ai = 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)]) = ρ(Ai)

Therefore:

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

and it follows that:

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

When ai = 1

If there is some element of A, ai, where i is an integer in the range 1 ≤ in, and where ai = 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)]) = ρ(Ai)

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 ai ≥ 2, bc

For the case when m > 1, and when all elements of A are greater than or equal to 2 and when bc, 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 An. Additionally, by the time we have traversed A recursively using the ψ function to reach An, we will have applied Euler’s totient function n – 1 times, since there are n – 1 elements of A before an. Therefore what we need to show for the basis case is this:

ψ(An, b, φn – 1(m)) ≡ ψ(An, c, φn – 1(m)) (mod φn – 1(m))

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

an(b * φ(φn – 1(m)))an(c * φ(φn – 1(m))) (mod φn – 1(m))

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

an(b * φ(m’))an(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):

ψ(An – (k – 1), b, φnk(m)) ≡ ψ(An – (k – 1), c, φnk(m)) (mod φnk(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:

ψ(An – ((k + 1) – 1), b, φn – (k + 1)(m)) ≡ ψ(An – ((k + 1) – 1), c, φn – (k + 1)(m) (mod φn – (k + 1)(m))

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

ψ(Ank, b, φn – (k + 1)(m)) ≡ ψ(Ank, c, φ(n – (k + 1)(m)) (mod φn – (k + 1)(m))

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

ankψ(A(nk) + 1, b, φ(φ(n – (k + 1)(m)))ankψ(A(nk) + 1, c, φ(φn – (k + 1)(m))) (mod φn – (k + 1)(m))

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

ankψ(An – (k – 1), b, φ(φ(n – (k + 1)(m)))ankψ(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:

ankψ(An – (k – 1), b, φ(m’)ankψ(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:

  • ψ(An – (k – 1), b, φ(m’)) ≥ emax(m’)
  • ψ(An – (k – 1), c, φ(m’)) ≥ emax(m’)
  • ψ(An – (k – 1), b, φ(m’)) ≡ ψ(An – (k – 1), c, φ(m’)) (mod λ(m’))

It must be the case that either O(An – (k – 1)) ≥ emax(m’) or O(An – (k – 1)) < emax(m’).

In either case, since k = O(An – (k – 1)) and k ≥ 1, and since all elements of An – (k – 1) are integers and are at least 2, by result 11, ρ(An – (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(An – (k – 1)) ≥ emax(m’), since ρ(An – (k – 1)) is defined, and since all elements of An – (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:

ψ(An – (k – 1), b, φ(m’)) ≥ emax(m’)
ψ(An – (k – 1), c, φ(m’)) ≥ emax(m’)

If O(An – (k – 1)) < emax(m’), since ρ(An – (k – 1)) is defined, and since all elements of An – (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:

ψ(An – (k – 1), b, φ(m’)) ≥ emax(m’)
ψ(An – (k – 1), c, φ(m’)) ≥ emax(m’)

We still need to show that the following is true:

ψ(An – (k – 1), b, φ(m’)) ≡ ψ(An – (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) = φ((nk) – 1) + 1)(m) = φnk(m)

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

ψ(An – (k – 1), b, φ(m’)) ≡ ψ(An – (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:

ψ(An – (k – 1), b, φ(m’)) ≡ ψ(An – (k – 1), c, φ(m’)) (mod λ(m’))

When a1 < 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 a1 < 0. Because a1 is never used as an exponent, it can be negative without us having to deal with non-integers.

If a1 < 0, there must exist some integer, d, where d > 0, such that:

a1d (mod m)

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

ψ(A, b, m) = a1b * φ(m)
ψ(A, c, m) = a1c * φ(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 a1 is an integer and d is an integer and d > 0, and given that a1d (mod m), by result 29, it follows that:

a1b * φ(m)db * φ(m) (mod m)
a1b * φ(m)dc * φ(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) = a1ψ(A2, b, φ(m))
ψ(A, c, m) = a1ψ(A2, c, φ(m))

Because d > 0 and the elements of A2 are integers that are at least 0, and no two consecutive elements of A2 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] ++ A2, b, m) ≡ ψ([d] ++ A2, c, m) (mod m)

By the definition of the ψ function:

ψ([d] ++ A2, b, m) = dψ(A2, b, φ(m))
ψ([d] ++ A2, c, m) = dψ(A2, c, φ(m))

Also by the definition of the ψ function:

ψ(A2, b, φ(m)) = ρ(A2 ++ [b * φn – 1(m)])
ψ(A2, c, φ(m)) = ρ(A2 ++ [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 A2 are integers that are at least 0 and no two consecutive elements of A2 are 0, by result 11, ρ(A2 ++ [b * φn – 1(m)]) is defined and ρ(A2 ++ [c * φn – 1(m)]) is defined. Therefore, by result 16, ρ(A2 ++ [b * φn – 1(m)]) and ρ(A2 ++ [c * φn – 1(m)]) are integers and ρ(A2 ++ [b * φn – 1(m)]) ≥ 0 and ρ(A2 ++ [c * φn – 1(m)]) ≥ 0.

Because ψ(A2, b, φ(m)) and ψ(A2, c, φ(m)) are integers and ψ(A2, b, φ(m)) ≥ 0 and ψ(A2, c, φ(m)) ≥ 0, and given that a1 is an integer and d is an integer and d > 0, and given that m is an integer and m ≥ 1, and given that a1d (mod m), by result 29, it follows that:

a1ψ(A2, b, φ(m))dψ(A2, b, φ(m)) (mod m)
a1ψ(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.