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 – 2idx (mod m)
where y is a non-trivial solution to the congruence:
y2 ≡ x2 (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:
i2d2 ≡ 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.