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* = (*p* – *q*) / 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* = *u*^{2} – *v*^{2}

*y* = 2*uv*

*z* = *u*^{2} + *v*^{2}

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*) = 1^{MA} * -1^{MB} * 1^{MC}

where *M*_{A} is the number of times *A* is multiplied to obtain *M*, *M*_{B} is the number of times *B* is multiplied to obtain *M*, and *M*_{C} 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 * -1^{MB} * 1 = -1^{MB}

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 = 1^{2}. 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:

*r*^{2} ≡ 1 (mod *m*)

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

*r*^{2} = *tm* + 1

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

*t* = *a*^{2} – *c*^{2}

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 *a*^{2} – *c*^{2} in a slightly different way. Since this is a difference of squares, we can construct the following equality:

*a*^{2} – *c*^{2} = (*a* + *c*)(*a* – *c*)

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* = 2*a* + *b*

*v* = 2*c* + *d*

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

*p* = *u* + *v*

*q* = *u* – *v*

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

*p* = 2*a* + *b* + 2*c* + *d*

*q* = 2*a* + *b* – 2*c* – *d*

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

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

Now we can substitute into the equation for *r*^{2} above using this equation for *m* and the one that I mentioned was going to be our assumption and we have this:

*r*^{2} = (*a* + *c*)(*a* – *c*)(2*a* + *b* + 2*c* + *d*)(2*a* + *b* – 2*c* – *d*) + 1

By subtracting 1 from both sides we have this:

*r*^{2} – 1 = (*a* + *c*)(*a* – *c*)(2*a* + *b* + 2*c* + *d*)(2*a* + *b* – 2*c* – *d*)

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

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

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 = (*a* – *c*)*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 = (*a* – *c*)*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 = (*a* – *c*)(2*a* + *b* + 2*c* + *d*)

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

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

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

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

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* = (*a* – *c*)(2*a* + *b* + 2*c* + *d*) – 1

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

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

*r* = 2*a*^{2} + *ab* + 2*ac* + *ad* – 2*ac* – *bc* – 2*c*^{2} – *cd* – 1

*r* = 2*a*^{2} + *ab* – 2*ac* – *ad* + 2*ac* + *bc* – 2*c*^{2} – *cd* + 1

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

*r* = 2*a*^{2} + *ab* + *ad* – *bc* – 2*c*^{2} – *cd* – 1

*r* = 2*a*^{2} + *ab* – *ad* + *bc* – 2*c*^{2} – *cd* + 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:

2*a*^{2} + *ab* + *ad* – *bc* – 2*c*^{2} – *cd* – 1 = 2*a*^{2} + *ab* – *ad* + *bc* – 2*c*^{2} – *cd* + 1

Now if we subtract 2*a*^{2} + *ab* and we add 2*c*^{2} + *cd* to both sides of this equation, we get this:

*ad* – *bc* – 1 = *bc* – *ad* + 1

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

2*ad* – 2*bc* = 2

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

*ad* – *bc* = 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:

*r*^{2} = m(*a*^{2} – *c*^{2}) + 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* = (*a* – *c*)(2*a* + *b* + 2*c* + *d*) + 1

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

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

*r* = 2*a*^{2} + *ab* + 2*ac* + *ad* – 2*ac* – *bc* – 2*c*^{2} – *cd* + 1

*r* = 2*a*^{2} + *ab* – 2*ac* – *ad* + 2*ac* + *bc* – 2*c*^{2} – *cd* – 1

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

*r* = 2*a*^{2} + *ab* + *ad* – *bc* – 2*c*^{2} – *cd* + 1

*r* = 2*a*^{2} + *ab* – *ad* + *bc* – 2*c*^{2} – *cd* – 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:

2*a*^{2} + *ab* + *ad* – *bc* – 2*c*^{2} – *cd* + 1 = 2*a*^{2} + *ab* – *ad* + *bc* – 2*c*^{2} – *cd* – 1

Now if we subtract 2*a*^{2} + *ab* and we add 2*c*^{2} + *cd* to both sides of this equation, we get this:

*ad* – *bc* + 1 = *bc* – *ad* – 1

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

2*ad* – 2*bc* = -2

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

*ad* – *bc* = -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:

*r*^{2} = m(*a*^{2} – *c*^{2}) + 1

This is a great idea. I have an optimisation for your approach that can solve the problem in O(ln(max (p, q)) . I want to discuss it with you personally. Can u respond to my E-Mail for the same. Thank u.

I’m not quite sure what you mean. Having the matrix corresponding to m, the modular square root of m can be calculated in O(1) since it is just sqrt((m(a^2 – c^2)) + 1). Can you explain more?

We can solve the problem without explicitly obtaining that matrix. We can just use the Properties of the matrix you have proved and solve the problem with Extended Euclidean Algorithm. As you told we can obtain answer in O(1) once we have the corresponding matrix. But I don’t think complexity of obtaining that matrix is O(1) because right inverse doesn’t exist for 2 x 1 matrix. Correct me if I am wrong. What is the complexity of obtaining that matrix according to you?

If the factorization of m is known then the matrix can be obtained with O(log(n)) complexity using the algorithm described in the wikipedia article about the tree of Pythagorean triples: https://en.wikipedia.org/wiki/Tree_of_primitive_Pythagorean_triples. As I mentioned in my previous post about this subject, this is not necessarily the best way of finding the modular square root of 1, mod m, when the factorization of m is known. My objective was only to illustrate an interesting relationship between the tree of Pythagorean triples and modular square roots.