Chasing the modular inverse

For years I've talked about the easy modular factorization with x² - Dy² = F.

Which is, when m² = D mod C, where C is some integer:

(x-my)(x+my) = x² - Dy² = F mod C

And then I'd use some residue r.

Where one way is: x - my = r mod C, then x+my = Fr^-1 mod C

Where for years have wondered about that modular inverse, and found myself pondering, can you use these equations to figure it out? So why now? I don't know. Just playing around.

Next thing I knew was looking at C = 111 = 3(37) where picked for easy. And noticed that a close square is 121, so got m = 11, and D = 10.

Then went for a prime for r, kind out of habit, and need one coprime to 111, wasn't going to use 2, so went with r = 5.

So had: x - 11(1) = 5 mod 111, so x = 16 mod 111

Then I calculated F, from x² - 10y² = F, and got F = 24 mod 111.

So had 16 + 11(1) = 24r^-1 mod 111, so 27 = 24r^-1 mod 111

Which didn't seem to get me anywhere. But I noted means: 5(27) = 24 mod 111

So I'm like, ok, why not use y = 2? And after same process got: 5(49) = 23 mod 111

And, I realized could subtract one from the other to get 5(27 - 49) = 5(-22) mod 111, so:

5(89) = 1 mod 111

So I got the modular inverse, but was that luck? And now finally decided to go more formal, so here is the full system:

 x² - Dy² = F, m² = D mod C, where C is some integer.

(x-my)(x+my) = x² - Dy² = F mod C,  x - my = r mod C, then x+my =Fr^-1 mod C

Solving for x, with x = my + r mod C, and substituting into x² - Dy² = F gets me:

r(r+2my) = F mod C

So I can look at a y₀ which will give an F₀, and a difference of d, such that:

y = y₀ + d

And played around enough to know I needed a variable n, where will just give what I got without explaining everything in detail. Is easy math though, so not hard to retrace.

nF₀ - F = r[(n-1)(r+2my₀) - 2md] mod C

And chasing after modular inverse, nF₀ - F = 1 mod C, would be nice, so have:

r[(n-1)(r+2my₀) - 2md] = 1 mod C

And then:

 r^-1 = (n-1)(r + 2my₀) - 2md mod C

Finally now then I have control equations with:

2mdF₀ = [F₀(n-1) - 1](r + 2my₀) mod C

and

F₀ = r(r+2my₀) mod C

So now I don't even see the original x² - Dy² = F or the other equations. Just see those three, but originals must be valid for it all to work! Must keep that in mind. First was thinking oh, they just went away. Nope. Math knows they are there.

Well now can see how n = 1, and d = 1 worked, with r = 5 mod 111.

So was just luck, huh? So you CAN just say, pick n, but then have potential of needing a modular inverse to calculate d, or vice versa. Oh yeah, m cannot equal r for this approach to work! Should note that as well.

Also may as well check my new equation since know n =1, works, and clips off the front too.

And: r^-1 = -2(11) = 89 mod 111, as we got above.

Went ahead and tried r = 41 mod 111, just to use something bigger, so again m = 11 and y₀ = 1. And got:

105d = 3n - 66 mod 111, where d = 1 will work with: n = 57

And that gives r^-1 = 65 mod 111, which works: 41(65) = 1 mod 111

And just playing around. So yes, can calculate a modular inverse this way, potentially. Definitely can get to another modular inverse to solve for n or d, but may not be necessary if can just figure them out like with my simple experiments. But who knows how often is that easy? I don't.

Wonder if could be proven.... Possibly something for some other time. These simple experiments have been rewarding and extremely interesting.

Glad did some experiments and some derivation.

Can be SO much fun to play with the math.


James Harris