Mathematics, Number Theory

Numbers that are their own modular square root

In a previous post, I followed up on a method I described to obtain non-trivial modular square roots to show something that followed from the proof of that method was that certain numbers could be shown to be their own modular square roots. In particular, what I showed was that if m is an odd integer greater than 2, and d and e are coprime divisors of m such that de = m, and both d and e are greater than 1 and less than m, then the the product of d and the multiplicative modular inverse of d, mod e, is its own square root, mod m. To be more precise, given these constraints:

m = de
2 ∤ m
1 < d < m
1 < e < m
gcd(d, e) = 1
i ≡ d-1 (mod e)

then this is true:

d2i2di (mod m)

I showed this by deriving it from this congruence when x = 1:

2idx(2idx – 2x) ≡ 0 (mod m)

However, there is a more straightforward way to show that di is its own modular square root, mod m, and it doesn’t rely on m not being divisible by 2.

Let’s start with this congruence, which we know to be true from the reflexive rule:

ii (mod e)

Now if we multiply the left hand side by di, which we can do because i is the inverse of d, mod e, and thus their product is 1, we get this:

di2i (mod e)

Now because gcd(d, e) = 1, we can multiply both sides by d as well as the modulus, which gives us this:

d2i2di (mod de)

Of course, m = de, so we can now convert the modulus to m:

d2i2di (mod m)

It turns out we can also lift the restriction that d and e are greater than 1 and less than m. Because gcd(m, 1) = 1, we can also apply this to the case when d = 1 and e = m, and vice versa. It turns out these cases give us di ≡ 1 and di ≡ 0, mod m, respectively, which are clearly their own square roots, even when m is prime.

Leave a Reply

Your email address will not be published. Required fields are marked *