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