Mathematics, Number Theory

Numbers that are their own modular square root

In a previous post, I followed up on a method I described to obtain non-trivial modular square roots to show something that followed from the proof of that method was that certain numbers could be shown to be their own modular square roots. In particular, what I showed was that if m is an odd integer greater than 2, and d and e are coprime divisors of m such that de = m, and both d and e are greater than 1 and less than m, then the the product of d and the multiplicative modular inverse of d, mod e, is its own square root, mod m. To be more precise, given these constraints:

m = de
2 ∤ m
1 < d < m
1 < e < m
gcd(d, e) = 1
i ≡ d-1 (mod e)

then this is true:

d2i2di (mod m)

I showed this by deriving it from this congruence when x = 1:

2idx(2idx – 2x) ≡ 0 (mod m)

However, there is a more straightforward way to show that di is its own modular square root, mod m, and it doesn’t rely on m not being divisible by 2.

Let’s start with this congruence, which we know to be true from the reflexive rule:

ii (mod e)

Now if we multiply the left hand side by di, which we can do because i is the inverse of d, mod e, and thus their product is 1, we get this:

di2i (mod e)

Now because gcd(d, e) = 1, we can multiply both sides by d as well as the modulus, which gives us this:

d2i2di (mod de)

Of course, m = de, so we can now convert the modulus to m:

d2i2di (mod m)

It turns out we can also lift the restriction that d and e are greater than 1 and less than m. Because gcd(m, 1) = 1, we can also apply this to the case when d = 1 and e = m, and vice versa. It turns out these cases give us di ≡ 1 and di ≡ 0, mod m, respectively, which are clearly their own square roots, even when m is prime.

Mathematics, Number Theory

Wilson’s Theorem

Wilson’s Theorem states that for an integer, n, where n is greater than 1, the product of the positive integers less than n is congruent with -1, mod n, if and only if n is a prime. The theorem is often stated like so:

(n – 1)! ≡ -1 (mod n)

The case when n is compound is easiest to prove. If n is compound then either n is the product of two unequal integers greater than 1 and less than n, or else n is the square of a prime integer.

It is clearly true that if n has more than one distinct prime factor that n is the product of two unequal integers greater than 1 and less than n, since if n has the prime factors p and q then n is the product of p and n/p, and n/p cannot be equal to p since n/p must be divisible by q. Likewise, if n is the power of a prime integer, p, with exponent e, and e is greater than 2, then n is the product of p and pe – 1, which are unequal because e > 2 and therefore e – 1 > 1.

If n is the product of two unequal integers greater than 1 and less than n, which we can call a and b, then both of those integers will occur in the sequence of positive integers less than n. Therefore, (n – 1)! will be product of a and b and the remaining positive integers less than n. Because n is the product of a and b, n must divide (n – 1)!, from which we can conclude that (n – 1)! ≡ 0 (mod n) in this case.

If n is the square of a prime integer, p, then either p is 2 and n is 4, in which case (4 – 1)! ≡ 2 (mod 4), or else 2p < p2, which means that 2, p and 2p will occur in the sequence of positive integers less than n. Therefore, 2p2 will divide (n – 1)!, from which we can conclude that with the exception of when n is 4, (n – 1)! ≡ 0 (mod n) in this case.

The case of when n is prime is also fairly simple to prove using Legrange’s Theorem which states that if p is a prime integer and f(x) is a polynomial with integer coefficients, then either every coefficient of f(x) is divisible by p, or else f(x) ≡ 0, mod p, has at most deg f(x) incongruent solutions.

Lagrange’s Theorem is relevant because we can use it to show that there are exactly two quadratic roots of 1, mod n, when n is prime. It is perhaps not clear why that’s relevant but I’ll get to that. If it’s not obvious why Lagrange’s Theorem means that there are exactly two quadratic roots of 1, mod n, I’ll explain. If a is a quadratic root of 1, mod n, a will satisfy this congruence:

a2 ≡ 1 (mod n)

We can subtract 1 from both sides which gives us this:

a2 – 1 ≡ 0 (mod n)

Now we can use Legrange’s Theorem to known that there can be at most 2 solutions to this congruence, given that n is a prime integer. Since we know that 12 is congruent with 1, mod n, and that -12 is congruent with 1, mod n, and n is prime, Legrange’s Theorem allows us to be certain that these are the only two quadratic roots of 1, mod n.

It happens that given a positive integer, m, the quadratic roots of 1, mod m, are exactly those integers that are congruent with their own modular multiplicative inverses, mod m. A modular multiplicative inverse of an integer, a, relatively prime to m, is defined such that the product of a and its inverse is congruent with 1, mod m. Furthermore, a can only have an inverse, mod m, if it is relatively prime to m. Given that the square of a is 1, mod m, we can conclude both that a is relatively prime to m and that a is its own inverse.

Another way of thinking about this is that if we start with this:

a2 ≡ 1 (mod m)

And then we multiply both sides of the congruence by the modular multiplicative inverse of a, mod m, we get this:

aa-1 (mod m)

So now we know, because of Legrange’s Theorem, that when n is a prime integer, only the integers congruent with 1 and -1, mod n, have inverses congruent with themselves, mod n. Let’s look now at why it is important to the proof of Wilson’s Theorem. First, while -1 is not in the set of positive integers less than n, n – 1 is in the set of positive integers less than n and n – 1 is congruent with -1, mod n.

If we examine the set of positive integers less than n, given that in this case n is a prime integer, all the positive numbers less than n are relatively prime to n and therefore each has an modular multiplicative inverse, mod n. Because the set of positive integers less than n represents exactly the reduced residue system, mod n, all of the positive integers less than n which are not congruent with their own inverse, mod n, are paired with exactly one other integer in the same set. Because the product of an integer and its inverse is 1, mod n, the product of all of these pairs is 1. Therefore, the product of all the positive integers less than n is congruent with the product of the two integers which are not paired with their inverse because they are congruent with their own inverse, those integers being 1 and n – 1. The product of these two integers is n – 1, which is congruent with -1, mod n. Thus for the case when n is prime:

(n – 1)! ≡ 1 * (n – 1) = n – 1 ≡ -1 (mod n)

Mathematics, Number Theory

Sum of powers modulo a prime

In number theory, if n is a positive integer and a is a an integer relatively prime to n, we say that the order of a with respect to n is the smallest positive integer, k, where:

ak ≡ 1 (mod n)

It is interesting to note that the order of a with respect to n divides φ(n), where φ is Euler’s Totient Function. This is because each element in the sequence of positive powers of a, mod n, is completely dependent on the previous element, except the first, which must be a. The residues, mod n, which are in this sequence must repeat with a period of k. Euler’s Theorem shows that:

aφ(n) ≡ 1 (mod n)

Therefore, φ(n) must be a multiple of k.

Here’s a fun fact: If p is an odd prime integer, and a is an integer relatively prime to p, and k is the order of a with respect to p, and k is greater than 1, the sum of the first k powers of a is congruent with 0, mod p. We can represent this statement like so:

\sum_{i=1}^{k}a^i \equiv 0 \pmod{p}

Let’s examine why this is true. First, let’s consider the case where k is even. It turns out this case is really easy to show. Because k is even, we know that k/2 is an integer. Let’s define j = k/2. Therefore:

ak = aj*aj ≡ 1 (mod p)

Thus, aj is the modular square root of 1, mod p. Because p is prime, then by Legrange’s Theorem, we know that each quadratic residue of p has at most 2 modular square roots. The modular square roots of 1, mod a prime integer, are those integers congruent with 1 and -1, mod that prime integer. We know that aj cannot be congruent with 1, mod p, because if that were true, then k would not be the least positive integer such that ak is congruent with 1, mod p. Since we defined k to be the order of a with respect to p we can conclude that:

aj ≡ -1 (mod p)

Let’s take a look at what that means for the elements of the sequence of powers of a from 1 to k. Let A represent this sequence such that A = {a, a2, …, ak-1, ak}. Now let B be the first half of the sequence A, and let C be the second half of the sequence A. There are exactly j positive powers of a in the sequence B = {a1, a2, …, aj} and there are also j positive powers of a in the sequence {aj+1, aj+2, …, ak}. From this it should be clear that the sum of the elements in B is:

\sum_{i=1}^{j}a^i

and that the sum of the elements in C is:

\sum_{i=j+1}^{k}a^i

and because A is the union of these two sequences:

\sum_{i=1}^{k}a^i = \sum_{i=1}^{j}a^i + \sum_{i=j+1}^{k}a^i

Because aj is congruent with -1, mod p, and aj+1 is the product of a and aj, aj+1 must be congruent with –a. And because aj+1 is congruent with –a, and aj+2 is the product of a and aj+1, aj+2 is congruent with -(a2). We can continue in this way to conclude that all positive powers of a are congruent with -1 times the same power of a plus j, mod p. Put another way, if i is a positive integer, then:

ai+j = ai*aj

and because:

aj ≡ -1 (mod p)

it follows that:

ai+jai * -1 (mod p)

Now let’s look again at the sum of the elements of C. We said that the sum of the elements of C was this:

\sum_{i=j+1}^{k}a^i

Each element of C is a power of a greater than j. We can, therefore, factor out aj from each element in C so that the sum of the elements in C becomes this:

a^j * \sum_{i=1}^{j}a^i

We have now expressed the sum of the elements of C in terms of the sum of the elements in B. And because aj is congruent with -1, mod p, we can now say this about the sum of the elements in C:

a^j * \sum_{i=1}^{j}a^i \equiv -1 * \sum_{i=1}^{j}a^i \pmod{p}

Now if we substitute this for the sum of the elements of C in the equation for the sum of the elements in A, we get this:

\sum_{i=1}^{k}a^i \equiv \sum_{i=1}^{j}a^i - \sum_{i=1}^{j}a^i \equiv 0 \pmod{p}

We have now shown that the sum of the sequence of powers of a from 1 to the order of a with respect to p is congruent with 0, mod p, when the order of a is even. We have not yet discussed the case when the order of a is odd.

Note that we made a special exception for when the order of a is 1. When the order of a with respect to p is 1, the sum is 1, not 0. Only numbers congruent with 1, mod p, have order 1. No integer congruent with 1, mod another integer, is congruent with 0, mod that same other integer, except in the special case when the modulus is 1. However, we have specified that the modulus is a prime, and 1 is not prime. No integer can be congruent with 1, mod a prime, and also be congruent with 0, mod that same prime.

So let’s consider the case when the order of a is odd and greater than 1.

First, notice that we don’t need to consider any primes smaller than 7 since we defined p to be an odd prime which means it cannot be 2, and the totient of 3 is 2 and the totient of 5 is 4 and neither 2 nor 4 are divisible by odd integers greater than 1.

Next, notice that all prime numbers greater than 2 are odd and the totient of any odd prime number is an even number because:

p ≡ 1 (mod 2)

therefore:

φ(p) = p – 1 ≡ 1 – 1 ≡ 0 (mod 2)

Now, considering when p is an odd prime integer, because the totient of p is even, if k, being the order of a with respect to p, is odd, it must be the case that 2k divides φ(p).

Furthermore, though I won’t attempt to show that this is the case here, it is well known that for any divisor, d, of φ(p), where p is a prime integer, there are exactly φ(d) positive integers less than p and relatively prime to p that have order d with respect to p. Therefore, there must be φ(k) positive integers less than p and relatively prime to p with order k and φ(2k) positive integers less than p and relatively prime to p with order 2k. But because Euler’s totient function is multiplicative and 2 does not divide k and so 2 is relatively prime to k, φ(k) is equal to φ(2k), because φ(2) is 1 and φ(2k) = φ(2) * φ(k). Therefore, there are as many positive integers relatively prime to p and less than p having the order 2k with respect to p as there are having the order k with respect to p.

For the remainder of the discussion, I will redefine a to be an integer relatively prime to p and less than p having the order 2k with respect to p, where k is an odd integer. Given this, a2 has order k. This is easy to show. First, let’s re-state what we know about a:

a2k ≡ 1 (mod p)

And now let’s see what happens when we raise a2 to the k power. First, we have this:

(a2)k

Using the power rule, we can multiply the exponents, giving us 2k and we already know that a2k is congruent with 1, mod p:

(a2)k = a2k ≡ 1 (mod p)

This shows that the order of a2 is at most k, but can it be less? It cannot. All of the powers of a2 are even powers of a, meaning if i is a positive integer less than or equal to k, (a2)i = a2i, again by the power rule. That means that if the order of a2 is less than k, the order of a would have to be less than 2k. Therefore, the order of a2 is k.

Now we must show the following:

\sum_{i=1}^{k}a^{2i} \equiv 0 \pmod{p}

You will see why in a moment, but let’s briefly examine which of the values of 2i are less than k+1 and which are greater than or equal to k+1 as i goes from 1 to k. 2i is equal to k+1 when i is equal to (k+1)/2. k is odd, so k+1 is even and so (k+1)/2 is an integer. Therefore, for values of i less than (k+1)/2, 2i will be less than k+1 and for values of i greater than or equal to (k+1)/2, 2i will be greater than or equal to k+1. We can now rewrite the congruence of the sum of powers of a2:

\sum_{i=1}^{k}a^{2i} = \sum_{i=1}^{(k-1)/2}a^{2i} + \sum_{i=(k+1)/2}^{k}a^{2i}

This is important because as we have already found, the numbers in the second half of the sequence of powers of a from 1 to 2k are congruent with the negation of the numbers in the first half of that sequence with an offset of k. Therefore, for each of the powers of a2 from (k+1)/2 to 2k, we can reduce the power of that element by k and multiply by -1 when evaluating the sum. We can now rewrite the above statement as a congruence:

\sum_{i=1}^{(k-1)/2}a^{2i} + \sum_{i=(k+1)/2}^{k}a^{2i} \equiv \sum_{i=1}^{(k-1)/2}a^{2i} - \sum_{i=(k+1)/2}^{k}a^{2i-k} \pmod{p}

We can simplify the second term on the right hand side of this congruence:

\sum_{i=(k+1)/2}^{k}a^{2i-k} = \sum_{i=1}^{(k+1)/2}a^{2i-1}

This gives us:

\sum_{i=1}^{(k-1)/2}a^{2i} + \sum_{i=(k+1)/2}^{k}a^{2i} \equiv \sum_{i=1}^{(k-1)/2}a^{2i} - \sum_{i=1}^{(k+1)/2}a^{2i-1} \pmod{p}

What this shows us is that the sum of first k powers of a2 is congruent with the sum of the first k powers of a, mod p, except that the odd powers are subtracted rather than added. In case this isn’t clear, let’s briefly look at the case when k is 5 and 2k is 10. The sum of the first 10 powers of a is:

a + a2 + a3 + a4 + a5 + a6 + a7 + a8 + a9 + a10

And the sum of the first 5 powers of a2 is:

a2 + a4 + a6 + a8 + a10

But because a6 ≡ –a and a8 ≡ -(a3) and a10 ≡ -(a5), mod p, we can do this:

a2 + a4 + a6 + a8 + a10 ≡ –a + a2a3 + a4a5 (mod p)

So you can see that the sum of first 5 powers of a2 is congruent with the sum of the first 5 powers of a, mod p, but with the odd powers of a within that range negated.

Because -1 raised to an odd power is -1 and -1 raised to an even power is 1, we can restate the sum of the first k powers of a2 like this:

\sum_{i=1}^{k}a^{2i} \equiv \sum_{i=1}^{k}(-1)^i*a^i \pmod{p}

Let’s look now if we shift the range of powers up by 1, meaning rather than summing the first k powers of a with odd powers negated, we will sum the k powers of a from a2 to ak+1. Because ak+1 is congruent with –a, and because k+1 is even, we will wind up removing the subtraction of a at the beginning but we will at the same time be adding –a at the end. The result is that the sum of this sequence is also congruent the sum of the first k powers of a2. We can continue increasing both the start and ending sequence positions as many times as we wish and the sum will always be congruent with the sum of the first k powers of a2, mod p. Therefore, if n is a non-negative integer:

\sum_{i=1}^{k}a^{2i} \equiv \sum_{i=n+1}^{n+k}(-1)^i*a^i \pmod{p}

Let’s consider specifically the case when n = k. When n = k, we have this:

\sum_{i=1}^{k}a^{2i} \equiv \sum_{i=k+1}^{2k}(-1)^i*a^i \pmod{p}

But remember, again, that ak+x is congruent with -(ax), mod p, where x is a positive integer. Therefore:

\sum_{i=k+1}^{2k}(-1)^i*a^i \equiv \sum_{i=1}^{k}(-1)*(-1)^i*a^i \pmod{p}

We can factor out the -1 from the terms in the sum on the right hand side of this congruence which gives us this:

\sum_{i=k+1}^{2k}(-1)^i*a^i \equiv -\sum_{i=1}^{k}(-1)^i*a^i \pmod{p}

Now if we define h to be:

h = \sum_{i=1}^{k}(-1)^i*a^i

We can combine the two congruences we have for the sum of the first k powers of a2:

\sum_{i=1}^{k}a^{2i} \equiv h \equiv -h \pmod{p}

Let’s examine this congruence:

h ≡ -h (mod p)

We can add h to both sides which gives us this:

2h ≡ 0 (mod p)

And now because we know that p is not divisible by 2, we can divide both sides of the congruence by 2:

h ≡ 0 (mod p)

Therefore:

\sum_{i=1}^{k}a^{2i} \equiv 0 \pmod{p}

Now let’s look at a concrete example where p is the prime integer 191, and a is 7. The order of 7 with respect to 191 is 10 and the order of 72 = 49 with respect to 191 is 5. The sum of first 10 powers of 7, mod 191, is:

7 + 49 + 152 + 109 + 190 + 184 + 142 + 39 + 82 + 1 ≡ 0 (mod 191)

Notice that the second half of the sequence of the first 10 powers of 7, mod 191, are the negated values of the first half in the same order, because 184 = 191 – 7, 142 = 191 – 49, 39 = 191 – 152, 82 = 191 – 109, and 1 = 191 – 190. Also notice that the 5th element of the sequence is 190, which is congruent with -1, mod 191. We can rewrite the sum of the first 10 powers of 7, mod 191, like this:

7 + 49 + 152 + 109 + 190 – 7 – 49 – 152 – 109 – 190 ≡ 0 (mod 191)

The sum of the first 5 powers of 49, mod 191, is:

49 + 109 + 184 + 39 + 1 ≡ 0 (mod 191)

If you compare this to the sequence of the first 10 powers of 7, mod 191, you will see that the first 5 powers of 49, mod 191, are the same as the 2nd, 4th, 6th, 8th, and 10th powers of 7, mod 191. The 6th, 8th, and 10th powers 7 of, mod 191, are the negated values of the 1st, 3rd, and 5th powers of 7, mod 191, so we can rewrite this congruence like so:

49 + 109 – 7 – 152 – 190 ≡ 0 (mod 191)

Or, if you want to see an expression that is truly amazing:

74 – 73 + 72 – 71 + 70 ≡ 0 (mod 191)

Mathematics, Number Theory

Modular square roots of compound integers revisited

In my last post, I described a method for finding the non-trivial modular square roots for a compound modulus.

I would like to follow up with a very interesting result which follows from that discussion. For review, we had a compound integer, m, with at least 2 distinct prime factors, and we said that d was an integer divisor of m greater than 1 and less than m, and e was equal to m/d, and that d and e were coprime. In summary we have:

m = de
d | m
e | m
1 < d < m
1 < e < m
gcd(d, e) = 1

We then defined id-1 (mod e) and this was used to show that:

yx – 2idx (mod m)

where y is a non-trivial solution to the congruence:

y2x2 (mod m)

Part of the proof focused on the statement that:

2idx(2idx – 2x) ≡ 0 (mod m)

Let’s take a look a little closer at this because it leads directly to the observation I want to make here. If we multiply out the terms on the left, we get this:

4i2d2x2 – 4idx2 ≡ 0 (mod m)

If we add 4idx2 to both sides, we get this:

4i2d2x2 ≡ 4idx2 (mod m)

If we now introduce an additional constraint that m is not divisible by 2 which implies that neither d nor e are divisible by 2, and we assign 1 to x, we can divide both sides of the congruence by 4 since 4 divides both sides evenly but not m, and we can remove the x2 from both sides because those evaluate to 1. This gives us:

i2d2id (mod m)

Notice now that id is its own square-root, mod m. It is trivial to find numbers which are their own square root because this is true of 0 and 1 not just in modular systems but in the set of Integers and the set of Real numbers as well.

However, id can be congruent with neither 0 nor 1, mod m. Because d is a divisor of m and greater than 1 and less than m and e = m/d, id can only be congruent with 0, mod m, if i is a multiple of e. But because i is the modular multiplicative inverse of d, mod e, i must not a multiple of e. Therefore, id is not congruent with 0, mod m.

If i could be the multiplicative inverse of d, mod m, then it would be possible for id to be congruent with 1, mod m. However, because d evenly divides m and is greater than 1, gcd(d, m) = d, therefore d does not have an multiplicative inverse, mod m, and id is not congruent with 1, mod m.

Therefore, id non-trivially has the property that it is its own square root, mod m. Of course, by the same reasoning, if j is the modular multiplicative inverse of e, mod d, then je also non-trivially has this property as well.

Mathematics, Number Theory

Modular square roots of compound integers

The title of this post might be misleading. While solving the following congruence for x is an interesting problem:

x2a (mod m)

this is not the objective of this post.

Instead, my goal is to show a method to find, for a given solution x to the above congruence, where x and a are positive integers, where m is an odd positive integer, and where x is coprime with m, what other solutions also exist.

It should already be fairly obvious that for a value of x that is a solution to the above congruence, -x is also a solution because x2 = –x2. This solution is trivial.

First, let’s consider when m is prime. For this case, we will use p instead of m to show that p is prime. If we have the following congruence:

x2a (mod p)

then x and -x are the only modular square roots of a, mod p.

Now, let’s consider the case when m is compound. If m is an odd compound integer with at least 2 distinct prime factors, and d is an integer divisor of m greater than 1 and less than m, and if we say that e = m/d, then e is also a an integer divisor of m and e is greater than 1 and less than m. We will now restrict the selection of d such that d and e must be coprime. We will see shortly why this is necessary.

In summary, we now have:
1 < d < m
1 < e < m
d | m
e | m
gcd(d, e) = 1
m = de

The Chinese Remainder Theorem will show that the only solution for the following system of linear congruences:

yx (mod d)
yx (mod e)

is this congruence:

yx (mod m)

Now, watch what happens when we solve the following system of linear congruences:

yx (mod d)
y-x (mod e)

The solution to this system of linear congruences is slightly more complicated. Let’s use the Chinese Remainder Theorem to solve this, but we’ll write out the steps so that the result is clear. First, we’ll transform the first congruence into an equation:

y = td + x

where t is some integer. Now we can substitute the value of y into the second congruence:

td + x ≡ –x (mod e)

We can subtract x from both sides, which gives us this:

td ≡ -2x (mod e)

Now, if we define i = d-1 (mod e) and multiply both sides of the congruence by i, we get this:

t ≡ -2ix (mod e)

We can now transform this congruence into an equation:

t = se – 2ix

Where s is some integer. Now if we substitute the value of t into the earlier equation, we get this:

y = d(se – 2ix) + x
= sde – 2idx + x
= sm – 2idx + x
= sm + x – 2idx

Now we can transform this back into a congruence, mod m:

yx – 2idx (mod m)

Let’s now see what we get when we evaluate y2, mod m:

y2 ≡ (x – 2idx)2 (mod m)

If we multiply out the expression on the right hand side of this congruence we get this:

y2x2 – 4idx2 + 4i2d2x2 (mod m)

From the second and third terms of the expression on the right hand side of this congruence, we can factor out 2idx:

y2x2 + 2idx(2idx – 2x) (mod m)

Let’s focus on the second term of the expression on the right hand side of this congruence. Clearly, because d is part of the term outside the parenthesis, the entire term is an integer multiple of d. Let’s look carefully at the terms inside the parenthesis. Remember that i is the modular multiplicative inverse of d, mod e. Therefore, if we evaluate these terms, mod e, we get this congruence:

z ≡ 2idx – 2x (mod e)

Because i is the multiplicative inverse of d, mod e, id is congruent with 1, mod e, so we can eliminate the id from this congruence. Therefore we have this:

z ≡ 2x – 2x (mod e)

And from this we can conclude:

z ≡ 0 (mod e)

This means that 2idx – 2x is an integer multiple of e.

Let’s look again at the congruence above. Because the term outside the parenthesis is an integer multiple of d and the terms on the inside the parenthesis evaluate to an integer multiple of e, we can conclude that the product of 2idx(2idx – 2x) is an integer multiple of m, which means that entire term is congruent with 0, mod m, and it can be removed from the congruence. Finally, we have this:

y2x2 (mod m)

Now to show that y is a non-trivial modular square root of a, it only remains to show that y ≢ ±x, mod m. Remember that this is the congruence that defines y, mod m:

yx – 2idx (mod m)

To show that yx, mod m, it is sufficient to show that 2idx ≢ 0, mod m. To show this, we will first assume that 2idx is congruent with 0, mod m, and then show that this leads to a conclusion that is impossible. Our assumption is this:

2idx ≡ 0 (mod m)

Because 2x divides both sides of the congruence and because m is odd and x is coprime with m, we can divide both sides of the congruence by 2x, which gives us this:

id ≡ 0 (mod m)

Now, because d divides both sides of the congruence and d divides m, we can divide it out of both sides of the congruence and the modulus, which gives us this:

i ≡ 0 (mod e)

However, this is impossible because i is the modular multiplicative inverse of d, mod e. If i ≡ 0, mod e, then di ≡ 0, mod e. However, by definition, di ≡ 1, mod e, which means that i ≢ 0, mod e. Therefore, we can conclude that yx, mod m.

To show that y ≢ –x, mod m, it is sufficient to show that 2idx ≢ -2x, mod m. To show this we will again begin by assuming that this congruence exists and show that it leads to a conclusion that is impossible. Our assumption is this:

2idx ≡ -2x (mod m)

Because we have defined m as an odd integer, m is not divisible by 2, and because we defined x and m to be coprime, we can divide both sides of the congruence by 2x, which gives us this:

id ≡ -1 (mod m)

However, we know that m is divisible by d and we know that d > 1, because that’s how we defined d to begin with. Given that, there is no multiple of d that could be 1 less than m. Therefore, we must reject the assumption we made and we can say that 2idx ≢ -2x, mod m. We can conclude from this that y ≢ ±x, mod m.

Let’s follow this discussion with a concrete example. As an example, I will use my favorite semi-prime, 66659, which is the product of the primes 191 and 349. In my last several posts, I described methods for finding the non-trivial modular square roots of 1, so why not use the value 1 for x? If x is 1, obviously a is also 1. We will define the terms like so:

m = 66659
d = 349
e = 191
x = 1
a = 1

Now, let’s solve for y. The only really complicated part of finding y is calculating the modular square root of d, mod e. Notice that this doesn’t involve x. Once we find the non-trivial modular square roots of 1, mod m, we can find all others corresponding to the pair of divisors of m which are d and e just by multiplying the result by x. For this example, the multiplicative modular inverse of 349, mod 191, is 81. Therefore, the non-trivial modular square roots of 1 are:

y ≡ 1 – (2*81*349*1) (mod 66659)
y ≡ (2*81*349*1) – 1 (mod 66659)

which evaluates to:

y ≡ 10122 (mod 66659)
y ≡ 56537 (mod 66659)

Let’s check our work. Let’s find out if 101222 and 565372 are congruent with 1, mod 66659.

101222 = 102454884 ≡ 1 (mod 66659)
565372 = 3196432369 ≡ 1 (mod 66659)

This confirms that 10122 and 56537 are non-trivial modular square roots of 1, mod 66659.

Let’s try a different value for x, to confirm that the other non-trivial modular square roots, mod 66659, are just multiples of the non-trivial modular square roots of 1. Let’s try the value x = 947. Now we have:

m = 66659
d = 349
e = 191
x = 947
a = 30242

y ≡ 947 – (2*81*349*947) (mod 66659)
y ≡ (2*81*349*947) – 947 (mod 66659)

which evaluates to:

y ≡ 53297 (mod 66659)
y ≡ 13362 (mod 66659)

Let’s check our work again.

532972 = 2840570209 ≡ 30242 (mod 66659)
133622 = 178543044 ≡ 30242 (mod 66659)

This confirms that 53297 and 13362 are non-trivial modular square roots of 30242, mod 66659.

Recall that we defined d such that it must be coprime with e. This is necessary because if we choose a divisor, d, of m that is not coprime with e = m/d, then the modular multiplicative inverse of d, mod e, would not exist, and vice-versa.

Speaking of vice-versa, we solved for y using the Chinese Remainder Theorem from this system of linear congruences:

yx (mod d)
y-x (mod e)

What happens if we switch x and –x, like so:

y-x (mod d)
yx (mod e)

The result is we get the same result, but negated:

y ≡ 2idxx (mod m)
yx – 2idx (mod m)

The same is also true if we solve for y in terms of e rather than d. If we say that j is the modular multiplicative inverse of e, mod d, then the following congruences can both be derived by solving for y in terms of e:

yx – 2jex (mod m)
y ≡ 2jexx (mod m)

Mathematics, Number Theory

Semi-prime modular square root of 1 revisited again

In my last post, I described a way to use the matrix, M, corresponding to the coefficients u and v that can be used to generate a primitive Pythagorean triple, to find the non-trivial modular square root of 1 for the odd leg of the triple. For reference, we have this:

m = pq = u2v2

where p and q are odd prime integers and p > q. Knowing the values of p and q, we can easily obtain u and v like so:

u = (p + q) / 2
v = (pq) / 2

We can trivially identify that

±12 ≡ 1 (mod m)

But given that m is the product of p and q, there should be two other modular square roots of 1. In my last post, I showed how, given the matrix that will generate the coefficients u and v, we can calculate the non-trivial modular square roots of 1, mod m, using two of the coefficients of that matrix. In the post prior to that, I described how to obtain the matrix from the factorization of m by following the path to the corresponding triple in the tree of primitive Pythagorean triples. I showed that if the matrix, M, is this:

M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}

then the non-trivial modular square root of 1, mod m, can be obtained easily like so:

r2 = m(a2c2) + 1

and so the non-trivial modular square roots of 1, mod m, are r and -r.

I’d like to revisit this once again to show that it is not necessary to obtain the complete matrix, M, to determine the values of the two matrix coefficients, a and c, that can be used to obtain the non-trivial modular square root of 1, mod m. I’d like to thank Nikhilesh Chamarthi for providing me with this solution. As Nikhilesh pointed out to me, the coefficients u and v can be generated by multiplying the vector [2, 1] by the matrix M, which gives us this:

u = 2a + b
v = 2c + d

If we solve these equations for b and d, respectively, we get this:

b = u – 2a
d = v – 2c

We know that the determinant of the matrix, M, is either 1 or -1, which gives us this:

adbc = ±1

If we substitute the values for b and d here, we get this:

a(v – 2c) – c(u – 2a) = ±1

If we multiply out across the parenthesis, we get this:

av – 2accu + 2ac = ±1

which can then be simplified to this:

avcu = ±1

Now what we have is a linear Diophantine equation which can easily be solved using Bézout’s identity via the extended Euclidean algorithm, given that u and v are coprime.

In practice, this is a significant improvement over the method I proposed of finding the path to the matrix M by traversing the tree of Pythagorean triples to its root using u and v. While the path will typically have a depth that is logarithmic with respect to m, the path could have a depth that approaches m. Using the extended Euclidean algorithm instead is strictly better. Because we know the values of u and v, we can easily solve for a and c without traversing the path to M through the tree. In fact, once we have the values of a and c, we can easily calculate b from a and u and we can easily calculate d from v and c.

While we might assume that we have to solve Bézout’s identity twice, once for the case where the determinant is 1 and once for the case where the determinant is -1, this isn’t necessary. It turns out that if we get it wrong, both coefficients will be negated. Since the method for finding the non-trivial modular square root of 1, mod m, involves squaring both a and c, it doesn’t matter if we get their signs correct.

Thanks again, Nikhilesh, for this insight.

Mathematics, Number Theory

Semi-prime modular square root of 1 revisited

In my last post I described a method for obtaining the modular square root of 1 for a semi-prime integer using the Tree of Pythagorean Triples. At the time, I presented the method as conjecture. However, now I have a proof, although the proof is not quite of the exact method I described. In fact, the method I’ll prove here is actually slightly easier than the one I presented previously.

In that post, I described how each odd semi-prime with distinct prime factors corresponds to a unique primitive Pythagorean triple and how using the path from the root of that tree, two of the coefficients of the 2×2 matrix generated using the reverse path could be used to find the modular square root of 1, mod the semi-prime in question. In fact, it is not necessary to reverse the path. Two of the coefficients of the 2×2 matrix used to obtain the primitive Pythagorean triple for which the semi-prime is the odd leg can be used directly to find the modular square root of 1, mod that semi-prime integer.

Let’s begin again with some definitions. We’ll consider two odd prime integers, p and q, such that the following is true:

p > q > 2

Now we’ll define m as the product of p and q. Because m has exactly two prime factors, it is a semi-prime.

As I showed in my last post, there exists a primitive Pythagorean triple where the semi-prime m is the length of the odd leg of the triangle. This triple can be generated using the coefficients u and v, which are obtained from p and q like so:

u = (p + q) / 2
v = (pq) / 2

As I showed in my last post, u and v are coprime, and have opposite parity. The primitive Pythagorean triple, x, y, z, with odd leg, x, equal to m is generated like so:

x = u2v2
y = 2uv
z = u2 + v2

Given that the integers x, y, and z form a primitive Pythagorean triple, this triple exists somewhere in the tree of primitive Pythagorean triples and therefore there exists a path from the root of the tree, being the triple 3, 4, 5, to the triple x, y, z. The coefficients used to generate each triple in the tree can be generated from the coefficients of its parent triple by pre-multiplying them with one of these 2×2 matrices:

A = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}, B = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}, C = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}

A 2×2 matrix can be generated corresponding to each primitive Pythangorean triple using matrix multiplication on the sequence of matrices following the path to that triple from the root of the tree. The Pythagorean triple can be obtained by pre-multiplying the coefficients of the root of the tree [2, 1] as a column vector by that 2×2 matrix to obtain the coefficients, u and v, that will generate that primitive Pythagorean triple.

Note, that the matrices A and C, above, have a determinant of 1 and that the matrix B, above, has a determinant of -1. Because the determinant of a product of two equal sized square matrices is the product of the determinants of the two matrices, any combination of only the matrices A, B, and C by matrix multiplication will also have a determinant of either 1 or -1. That means that the 2×2 matrix that can be used to generate the coefficients of a primitive Pythagorean triple has a determinant of 1 or -1 because it can be generated using matrix multiplication of some combination of the matrices A, B, and C. To be more precise, if a matrix, M, is composed with matrix multiplication using only the matrices A, B, and C, then the determinant of M will have a value defined like so:

det(M) = 1MA * -1MB * 1MC

where MA is the number of times A is multiplied to obtain M, MB is the number of times B is multiplied to obtain M, and MC is the number of times C is multiplied to obtain M. Because 1 raised to any power is still 1, this equation can be reduced to this:

det(M) = 1 * -1MB * 1 = -1MB

The determinant of a matrix, M, used to generate the coefficients u and v which will produce a given primitive Pythagorean triple is therefore 1 if the number of times the matrix B appears in the path from the root of the tree to that triple is even and it is -1 if the number of times the matrix B appears in the path from the root of the tree to that triple is odd.

Let’s define the coefficients of the 2×2 matrix M that will generate a primitive Pythagorean triple like so:

M = \begin{bmatrix} a & b \\ c & d \end{bmatrix}

Now let’s talk about the modular square root of 1, mod m. We know that 1 is quadratic residue of any modulus greater than 1 since 1 = 12. Since m is the product of p and q, both of which are distinct odd primes, m cannot be less than 15. Therefore 1 is quadratic residue of m. Because m is a semi-prime integer, any integer that is quadratic residue of m must have 4 distinct modular square roots. There are 2 modular square roots of 1, mod m, that are trivial to obtain which are 1 and -1. The other two are non-trivial roots. Let’s call the non-trivial modular square roots of 1, mod m, r and –r. We know that r exists and its square is congruent with 1, mod m, which gives us this:

r2 ≡ 1 (mod m)

Which by the definition of modular congruence is equivalent to the following:

r2 = tm + 1

where t is some non-negative integer. I will now show that the following is true:

t = a2c2

where a and c are the top left and bottom left coefficients of the 2×2 matrix, M, used to generate the coefficients, u and v, corresponding to the primitive Pythagorean triple, x, y, and z, where x = m.

To show this, I will begin by assuming that this is true and then I will show that doing so leads to an equation which we already know is true. I could go in the opposite direction but the algebraic manipulations would appear random and doing so would be less clear.

First, let’s rewrite a2c2 in a slightly different way. Since this is a difference of squares, we can construct the following equality:

a2c2 = (a + c)(ac)

Note also that m is the product of p and q. Remember how we defined u and v from p and q and also note how we can generate u and v from the 2×2 matrix, M, with coefficients a, b, c, and d. By pre-multiplying the column vector [2, 1] with this 2×2 matrix we will obtain u and v like so:

u = 2a + b
v = 2c + d

We can obtain p and q from u and v like so:

p = u + v
q = uv

and using substitution we can define p and q in terms of a, b, c, and d:

p = 2a + b + 2c + d
q = 2a + b – 2cd

Because m is the product of p and q, we have the following equation:

m = (2a + b + 2c + d)(2a + b – 2cd)

Now we can substitute into the equation for r2 above using this equation for m and the one that I mentioned was going to be our assumption and we have this:

r2 = (a + c)(ac)(2a + b + 2c + d)(2a + b – 2cd) + 1

By subtracting 1 from both sides we have this:

r2 – 1 = (a + c)(ac)(2a + b + 2c + d)(2a + b – 2cd)

Notice now on the left we have a difference of squares which we can factor, giving us this:

(r + 1)(r – 1) = (a + c)(ac)(2a + b + 2c + d)(2a + b – 2cd)

Now I’m going to refine the assumption to be something slightly more specific. In the case where the determinant of the matrix M is 1, the assumption will become these equations:

r + 1 = (ac)p
r – 1 = (a + c)q

and in the case where the determinant of the matrix M is -1, the assumption will become these equations:

r – 1 = (ac)p
r + 1 = (a + c)q

Substituting in these equations for p and q we get these equations for the case when the determinant of M is 1:

r + 1 = (ac)(2a + b + 2c + d)
r – 1 = (a + c)(2a + b – 2cd)

and we get these equations for the case when the determinant of M is -1:

r – 1 = (ac)(2a + b + 2c + d)
r + 1 = (a + c)(2a + b – 2cd)

It should be clear that for both cases the equation above is the just these two equations for each case multiplied together.

We will first examine the case when the determinant of M is 1. We can subtract 1 from both sides of the first equation and add 1 to both sides of the second equation which gives us this:

r = (ac)(2a + b + 2c + d) – 1
r = (a + c)(2a + b – 2cd) + 1

Now if we multiply out the products in these equations, we get these:

r = 2a2 + ab + 2ac + ad – 2acbc – 2c2cd – 1
r = 2a2 + ab – 2acad + 2ac + bc – 2c2cd + 1

These equations can be already simplified since both contain the terms 2ac and -2ac:

r = 2a2 + ab + adbc – 2c2cd – 1
r = 2a2 + abad + bc – 2c2cd + 1

Now since the left hand side of both equations is r, the right hand side must also be equal so we can combine these equations like so:

2a2 + ab + adbc – 2c2cd – 1 = 2a2 + abad + bc – 2c2cd + 1

Now if we subtract 2a2 + ab and we add 2c2 + cd to both sides of this equation, we get this:

adbc – 1 = bcad + 1

Now if we subtract bc from both sides and we add ad + 1 to both sides we get this:

2ad – 2bc = 2

Now if we divide both sides by 2, we get this:

adbc = 1

This is precisely the equation for the determinant of the matrix M which we have already stipulated is 1 for this case. Therefore, when the determinant of the matrix M is 1, the modular square root of 1, mod m, can be obtained like so:

r2 = m(a2c2) + 1

Now let’s consider the case when the determinant of the matrix M is -1, which we will handle very similarly. If we add 1 to both sides of the first equation we assumed to be true for this case and we subtract 1 from both sides of the second equation, we obtain this:

r = (ac)(2a + b + 2c + d) + 1
r = (a + c)(2a + b – 2cd) – 1

If we multiply out the products in these equations, we get this:

r = 2a2 + ab + 2ac + ad – 2acbc – 2c2cd + 1
r = 2a2 + ab – 2acad + 2ac + bc – 2c2cd – 1

These equations can be simplified since they both contain the terms 2ac and -2ac:

r = 2a2 + ab + adbc – 2c2cd + 1
r = 2a2 + abad + bc – 2c2cd – 1

Now, since r appears on the left hand side of both equations, the right hand sides must be equal as well which gives us this:

2a2 + ab + adbc – 2c2cd + 1 = 2a2 + abad + bc – 2c2cd – 1

Now if we subtract 2a2 + ab and we add 2c2 + cd to both sides of this equation, we get this:

adbc + 1 = bcad – 1

Now if we subtract bc + 1 from both sides and we add ad to both sides we get this:

2ad – 2bc = -2

Now if we divide both sides by 2, we get this:

adbc = -1

This is, again, precisely the equation for the determinant of the matrix M which we have already stipulated is -1 for this case. Therefore, when the determinant of the matrix M is -1, the modular square root of 1, mod m, can be obtained like so:

r2 = m(a2c2) + 1

Mathematics, Number Theory

Semiprime modular square root of 1

There is already a well-known efficient algorithm to find the modular square root of a number that is quadratic residue when the factorization of the modulus is known. I believe I’ve found a new way of finding the modular square root for the special case when the quadratic residue is 1 and the modulus is an odd semiprime with a known factorization of two distinct odd primes. The interesting thing about this method is not that it’s possible to find the modular square root of 1 but in how this method works.

Note that for a semiprime, there will always be exactly four modular square roots of 1. Since 1 is already the square of itself, there are two square roots of 1 that are trivial, being 1 and -1. The challenge is to find the other two. Since 1 is square and less than any semiprime, it is quadratic residue. Therefore, there must be two other modular square roots of 1, mod m.

In fact, I don’t have a proof to show that the method described here works in all cases, but I’ve verified that it works for thousands of cases and haven’t yet found a counter-example. I’d love to someday find a proof but I don’t expect that it will be worth my time to search for one.

The basis for this method is the tree of primitive Pythagorean triples. The entire tree can be generated from arbitrary combinations of the following 2×2 matrices:

A = \begin{bmatrix} 2 & -1 \\ 1 & 0 \end{bmatrix}, B = \begin{bmatrix} 2 & 1 \\ 1 & 0 \end{bmatrix}, C = \begin{bmatrix} 1 & 2 \\ 0 & 1 \end{bmatrix}

Every primitive Pythagorean triple in the tree can be generated using a pair of coefficients, u and v, where u and v are coprime and have opposite parity, meaning one is even and the other is odd, and where u > v. Every possible pair of positive integers meeting these criteria will generate a unique Pythagorean triple with sides a, b, and c using the following equations:

a = u2v2
b = 2uv
c = u2 + v2

The root of the tree is the well known primitive Pythagorean triple 3, 4, 5, and is generated using the coefficients u = 2 and v = 1.

Given a semiprime, m, which is the product of two primes, p and q, where p > q, there exists a primitive Pythagorean triple where m is the length of the odd non-hypotenuse side of the triangle. In fact, there are exactly two such primitive Pythagorean triples. In general, for any positive odd number greater than 1, there is exactly one primitive Pythagorean triple with the odd non-hypotenuse side with that length for every distinct factorization pair, without respect to order, of that number where the two factors are coprime. Given this, there are exactly two primitive Pythagorean triples where the odd non-hypotenuse length is the semiprime m, corresponding to the two distinct pairs of factors of m, which are:

m = p * q
m = m * 1

For the case of m = m * 1, u = (m + 1) / 2 and v = (m – 1) / 2.

For the case of m = p * q, u = (p + q) / 2 and v = (pq) / 2. It is this case that will be useful to help us find the square root of 1, mod m.

To prove that u and v are, in fact, coefficients that will generate a primitive Pythagorean triple, it is necessary to show that u and v are both coprime and that they have opposite parity.

To show that u and v are coprime, let’s consider the case where there is some integer n that divides both u and v. We can then rewrite u and v like so:

u = s * n
v = t * n

where s and t are integers. We can then substitute these into the equations for u and v like so:

s * n = (p + q) / 2
t * n = (pq) / 2

If we solve the first equation for p we get this:

p = 2(s * n) – q

Now if we substitute that equation for p in the second equation, we can reduce the second equation to this:

q = n(st)

We know that n divides both sides of the equation, so therefore n must divide q. Because we defined q to be a prime integer, n can only be 1 or q. However, if we perform the substitutions in the opposite direction, we will arrive at this equation:

p = n(s + t)

Again, we know that n divides both sides of the equation, so therefore n must divide p. Because we defined p to be a prime integer, n can only be 1 or p. However, we’ve already established that n must be either 1 or q and we have defined p > q which means that n can not be both p and q so it must be neither. The only remaining possibility is that n is 1, which means that u and v are coprime.

To show that u and v are opposite parity is easy as well. First, we’ll demonstrate the u and v are both integers. Because p and q are both odd primes, they are both congruent with 1, mod 2. According to the rules of modular algebra, we know that these congruences are true:

p + q ≡ 1 + 1 ≡ 0 (mod 2)
pq ≡ 1 – 1 ≡ 0 (mod 2)

Therefore, both the sum and difference of p and q are even and therefore half their sum and difference are integers.

We’ll use the same technique to show that they have opposite parity. Because we know that p and q are odd integers, we know that they are both congruent with either 1 or 3, mod 4, because if they were congruent with 0 or 2, mod 4, they would not be odd. There are a limited number of possible combinations which I will enumerate here:

p + q ≡ 1 + 1 ≡ 2 (mod 4) and pq ≡ 1 – 1 ≡ 0 (mod 4) or
p + q ≡ 1 + 3 ≡ 0 (mod 4) and pq ≡ 1 – 3 ≡ 2 (mod 4) or
p + q ≡ 3 + 1 ≡ 0 (mod 4) and pq ≡ 3 – 1 ≡ 2 (mod 4) or
p + q ≡ 3 + 3 ≡ 2 (mod 4) and pq ≡ 3 – 3 ≡ 0 (mod 4)

In all four possible scenarios, either p + q is congruent with 2, mod 4, and pq is congruent with 0, mod 4, or else p + q is congruent with 0, mod 4, and pq is congruent with 2, mod 4. If p + q is congruent with 2, mod 4, then u is congruent with 1, mod 2, meaning u is odd. If p + q is congruent with 0, mod 4, then u is congruent with 0, mod 2, meaning u is even. The same logic applies to v. Since p + q and pq can’t both be congruent with 0, mod 4, and they can’t both be congruent with 2, mod 4, u and v can’t both be even and they can’t both be odd.

We’ve now established that u and v are coefficients that correspond to a primitive Pythagorean triple. To use this information to find the non-trivial modular square roots of 1, we want to find the path taken to find that primitive Pythagorean triple corresponding to u and v.

To do this, we will use the inverses of the matrices defined above which are these:

A^{-1} = \begin{bmatrix} 0 & 1 \\ -1 & 2 \end{bmatrix}, B^{-1} = \begin{bmatrix} 0 & 1 \\ 1 & -2 \end{bmatrix}, C^{-1} = \begin{bmatrix} 1 & -2 \\ 0 & 1 \end{bmatrix}

Starting with the coefficients u and v, we can try pre-multiplying the two coefficients as a column vector with each of the three inverse matrices. Two of the results will be invalid because they will have non-positive coefficients. The remaining one is the true parent along the path of the tree of Pythagorean triples leading to that pair of coefficients. Repeating this process will eventually lead to the root of the tree with the coefficients 2, 1. At that point, the complete path to the Pythagorean triple corresponding to m will have been found.

Now, if we follow the same path but in reverse, starting with the identity 2×2 matrix and pre-multiplying the corresponding matrix A, B, or C, above, we will arrive at a 2×2 matrix that will produce a different (in most cases) Pythagorean triple. The exception is when the path to the original Pythagorean triple is reflexive, for example the path ABCBA, in which case following the reverse path will lead to the original triple.

Now comes the trick. It turns out that the bottom two coefficients of this 2×2 matrix can be used to find the non-trivial modular square roots of 1, mod m. If we assign variables to the matrix coefficients like so:

\begin{bmatrix} w & x \\ y & z \end{bmatrix}

Then, like magic, we can calculate the two non-trivial modular square roots of 1, mod m, like so:

(m * (3y + z) * (y + z))2 ≡ 1 (mod m)

Let’s look at a concrete example, for which I will use my favorite semiprime, 66659, which is the product of the primes 349 and 191. Here are the coefficients we start with:

m = 66659
p = 349
q = 191
u = 270
v = 79

Using the method described above, we find that the path to the Pythagorean triple with odd non-hypotenuse leg of length 66659 is this:

CCBACAAC = \begin{bmatrix} 41 & 188 \\ 12 & 55 \end{bmatrix}

If we follow the reverse of this path, we arrive at this 2×2 matrix:

CAACABCC = \begin{bmatrix} 79 & 112 \\ 12 & 17 \end{bmatrix}

Using the bottom two coefficients in this matrix we can generate the two non-trivial modular square roots of 1, mod 66659:

(66659 * ((3 * 12) + 17) * (12 + 17))2 ≡ 101222 ≡ 1 (mod 66659)
(66659 – 10122)2 ≡ 565372 ≡ 1 (mod 66659)

It is interesting to note that the u coefficient obtained by the matrix resulting from following the reverse path of the original Pythagorean triple will be identical to the u coefficient corresponding to m. In this example, the u and v coefficients generated by the matrix generated using the reverse path are 270 and 41.

I don’t have a good explanation for why this method works, much less a proof. I can therefore, obviously, not be certain that it works for all semiprimes. Given that the problem of finding modular square roots is already known in the general case, this method is not particularly useful. The point of presenting this method is mostly just to illustrate an interesting relationship between semiprimes and the tree of Pythagorean triples.

Mathematics, Number Theory

Using the congruence of exponents in integer factorization

I hope that this post isn’t anti-climactic after my last post on the recursive congruence of exponents. I suggested that the recursive congruence of exponents could be used in integer factorization. While there is potential for this, I am not going to offer the holy grail of integer factorization because I don’t have one. What I do have is an explanation of how the recursive congruence of exponents could be used, assuming a few things that are not necessarily valid.

First I’d like to discuss the objective of integer factorization. Integer factorization has very important real-world implications when you consider the RSA problem. The real challenge of integer factorization is the factorization of large semiprimes, which are, of course, the product of two large prime integers. There are no known methods of factoring large semiprimes in polynomial time.

However, given the recursive congruence of exponents, we know that repeated squaring of any integer and reducing to the least positive residue, mod n, results in a cycle. Further, the period of this cycle divides λ(λ(n)). How does this help us factor n?

Well, first consider that every quadratic residue, mod n, where n is a semi-prime, has exactly 4 modular square roots. These 4 modular square roots are always two pairs of modular opposites. For example -1 and 1 both square to 1, and 1 is a quadratic residue, mod n, for all positive values of n. If n is a semiprime, there will be some other modular square root of 1, mod n. If we call that value i, –i will also square to 1, mod n.

Let’s look at a concrete example. We’ll use my favorite semiprime, 66659, which happens to be 191 * 349. The modular square roots of 1, mod 66659, are 1, 10122, 56537, and 66658. 56537 is equal to 66659 – 10122 and 66658 is equal to 66659 – 1.

12 ≡ 1 (mod 66659)
101222 ≡ 1 (mod 66659)
565372 ≡ -101222 ≡ 1 (mod 66659)
666582 ≡ -12 ≡ 1 (mod 66659)

The reason this is useful in factoring is that if you can discover 2 non-opposite modular square roots of the same value, mod a semiprime n, then you can easily factor n. This is because the sum and difference of those 2 modular square roots will be a multiple of one of the factors of n. Because n is also a multiple of the factors of n, the factors of n are trivially obtained using the greatest common divisor function.

Let’s take a look at the example of 66659 again. We know that 1 and 10122 are both modular square roots of 1, mod 66659, and that they are not opposites, mod 66659. Therefore, their sum and difference are both multiples of the factors of 66659, which again, are 191 and 349.

10122 + 1 = 10123
10122 – 1 = 10121

gcd(10123, 66659) = 191
gcd(10121, 66659) = 349

How is this related to the recursive congruence of exponents? The relationship is that the cyclic nature of residues of repeated squaring means that we may be able to find two non-opposite modular square roots of the same value, mod n. Beginning with literally any integer, we can find a cycle. There are 3 integers which will never produce useful cycles, which are 0, 1, and -1. The cycles generated by starting with these numbers will always have length 1 so we can’t use them to find non-opposite modular square roots. However, roughly half of other starting points will give us 2 non-opposite modular square roots, and thus, allow us to factor n.

As is shown by the recursive congruence of exponents, repeated squaring will always yield a cycle and the length of the cycle will divide λ(λ(n)). For the special case of semiprimes, a cycle will be reached within 2 squares. This is because all starting points can be categorized as a quadratic residue that is a member of a cycle, a quadratic residue that is not a member of a cycle, or a quadratic non-residue. Roughly half of all starting points will be quadratic non-residues. All quadratic non-residues squared will be quadratic residues which will either be a member of a cycle of not a member. The square of a quadratic residue will always be a member of a cycle. If you can find a number, x, that is not a member of a cycle but whose square is a member of a cycle, mod n, then x and x2λ(λ(n)) will both be modular square roots of x2, mod n. For semiprimes, roughly 3 out of 4 starting points will either fall into this category or else their square will do so, though in half of the cases found, the modular square roots found in this way will be opposites.

There are, of course, some challenges to using this approach. For example, discovering λ(λ(n)) without knowing the factorization of n is not necessarily easy. In fact, if n is very large, it may be very difficult to calculate λ(λ(n)), even if you know the factorization of n. You can discover it by repeatedly squaring and looking for cycles, though there’s a roughly 5 in 8 chance that you will have to do this a second time. Additionally, λ(λ(n)) may be roughly similar in scale to the factors of n. Squaring repeatedly λ(λ(n)) times is therefore similar in time complexity as the long division factoring method, which is generally the slowest method. However, should there be a way to guess λ(λ(n)), given n, or at least guess some of the factors of λ(λ(n)), then it may, in fact, be useful. Also, while the length of all such cycles will divide λ(λ(n)), some will be much less.

Let’s take a look one more time at the example semiprime, 66659. λ(λ(66659)) is equal to 252. Squaring most integers will yield a cycle after 1 or 2 iterations that has length 252. However, take a look at the cycle formed from the starting point of 136:

1362 ≡ 18496 (mod 66659)
1849628028 (mod 66659)
80282 ≡ 56190 (mod 66659)
561902 ≡ 12565 (mod 66659)
125652 ≡ 30713 (mod 66659)
307132 ≡ 63519 (mod 66659)
635192 ≡ 60727 (mod 66659)
607272 ≡ 59331 (mod 66659)
593312 ≡ 39089 (mod 66659)
390892 ≡ 58982 (mod 66659)
589822 ≡ 9773 (mod 66659)
97732 ≡ 55841 (mod 66659)
558412 ≡ 42579 (mod 66659)
425792 ≡ 46418 (mod 66659)
464182 ≡ 11867 (mod 66659)
118672 ≡ 41881 (mod 66659)
418812 ≡ 19894 (mod 66659)
198942 ≡ 16753 (mod 66659)
167532 ≡ 28619 (mod 66659)
2861928028 (mod 66659)

From this sequence, we can see that 8028 has modular square roots of 18496 and 28619. Because 18496 and 28619 are not opposites, mod 66659, we can use their sum and difference to factor 66659:

gcd(28619 – 18496, 66659) = 191
gcd(28619 + 18496, 66659) = 349

Notice from this that our starting point, 136, is not a quadratic residue, mod 66659. Also, the first square in the sequence, 18496, while a quadratic residue, is not a member of the cycle, but its square is. Also, the length of this cycle is only 18, which both divides 252 and is far less than 252. However, generally only a small number of cycles will be so short. The fact that some cycles are much shorter than λ(λ(n)) does not mean that you are likely to find one.

While normally you would have to perform λ(λ(n)) repeated squarings to get the result of a cycle, if you know λ(λ(n)), you can take advantage of the congruence of exponents to reduce the amount of work required. To calculate modular exponents, there is an algorithm that will allow you to do so in logarithmic time with respect to the exponent value. For example, if you want to calculate:

ae (mod n)

then this algorithm will allow you to do so with O(log(e)) time complexity. Because what we are effectively calculating is a2e in this case, we can’t normally do so in less than O(e) time complexity. However, using the congruence of exponents, we know that the following congruence is true:

a2λ(λ(n))ab (mod n)

where

b ≡ 2λ(λ(n)) (mod λ(n))

Unfortunately, this means that we not only have to guess λ(λ(n)) but we also have to guess λ(n).

Let’s look at our example semiprime, 66659, again for this. λ(66659) is equal to 33060.

2252 ≡ 24796 (mod 33060)

184962252 ≡ 28619 (mod 66659)
1849624796 ≡ 28619 (mod 66659)

Remember that we found that 18496 is not a member of a cycle, mod 66659 but that its square is. To find another modular square root of 184962 by repeated squaring, we would need iterate 252 times. However, we can get the same result (28619) by just raising 18496 to the power of 24796, mod 66659, which we can do in log(24796) time complexity, or in 15 iterations.

Obviously, this is not actually a realistic factoring method. It’s interesting to see the congruence of exponents in use, however.

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.