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* = *u*^{2} – *v*^{2}

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* = (*p* – *q*) / 2

We can trivially identify that

±1^{2} ≡ 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:

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

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

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

*b* = *u* – 2*a*

*d* = *v* – 2*c*

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

*ad* – *bc* = ±1

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

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

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

*av* – 2*ac* – *cu* + 2*ac* = ±1

which can then be simplified to this:

*av* – *cu* = ±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.