Playing with modular solution

Great thing with number theory is playing with numbers, and I love watching them follow cool rules.

So, here's a post playing with one of my results that solves x² - Dy² = 1 modularly.

Given n such that: n² = D mod p, where p is a prime number, and r, any residue modulo p:

2x = r + r^-1 mod p and 2y = n^-1(r - r^-1) mod p

gives solutions for x² - Dy² = 1 mod p.

Two equations that follow from the result--or which can be used to derive it--are:

r = x + ny mod p and r^-1 = x - ny mod p

But I wish to play wider than p, a prime number, so will jump to mod N, where N is a natural number, which is easy to prove, but means you now have to add the restriction on n and r that their modular inverse exists! So now I have:

2x = r + r^-1 mod N and 2y = n^-1(r - r^-1) mod N

And I'm going to go now to a famous solution to x² - Dy² = 1.

With D=61, the smallest positive nonzero integer x and y set that will work is:

x = 1766319049, y = 226153980

That solution was made famous by Fermat using the D=61 case as a challenge problem! Hundreds of years ago. Here I'll use it with my equations for r and its modular inverse now modulo N, with 'm' instead of 'n' so there is no confusion with letters:

r = x + my mod N

and

r^-1 = x - my mod N

I'm going to try something, which is to find r and its inverse by using x and y from the D=61 solution, so I need m and N, where m² = 61 mod N. I want N greater than x so will go looking at x+4:

1766319049 + 4 = 1766319053, and its integer square root is: 42027

And I'll add one more and use 42028² - 61, which is: 1766352723.

So N = 1766352723, and m = 42028.

Now I can plug in my numbers:

r = 1766319049 + (42028)(226153980) mod 1766352723

and

r^-1 = 1766319049 - (42028)(226153980) mod 1766352723

Which gives me:

r = 55435303 mod 1766352723; and r^-1 = 1710850072  mod 1766352723

So why bother? Well it just gave me a modular inverse--if the equations are correct!

And, yup, you can use your pc calculator--which I just did--and verify:

(55435303)(1710850072) = 1 + (53693405)(1766352723) = 1 mod 1766352723

What's kind of funny to me is that first while typing this post I did several things wrong, and did that check and didn't get 1, so there is this feeling of mini-panic. And I'll wonder briefly if my math theory is wrong, but then remind myself, nope, it's derived. So I realize I made a mistake somewhere. And of course I did.

Math is perfect. It's us people who make mistakes.

Want to see more? You can check out the derivation of the mod p result here. New to modular arithmetic? Then you might like my light introduction to modular arithmetic.

So what's the use of the result? I can't think of a practical use! But it's just fun playing with numbers to me, and it shows the correctness of the equation for others with a famous solution.

There is that comfort for me, I'll admit too. At times I just run numbers with my research just to get that feeling of satisfaction when everything works, perfectly.


James Harris