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 **i** ≡ **d**^{-1} (mod **e**) and this was used to show that:

**y** ≡ **x** – 2**idx** (mod **m**)

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

**y**^{2} ≡ **x**^{2} (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:

4**i**^{2}**d**^{2}**x**^{2} – 4**id****x**^{2} ≡ 0 (mod **m**)

If we add 4**id****x**^{2} to both sides, we get this:

4**i**^{2}**d**^{2}**x**^{2} ≡ 4**id****x**^{2} (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 **x**^{2} from both sides because those evaluate to 1. This gives us:

**i**^{2}**d**^{2} ≡ **id** (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.