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 x2 - Dy2 = 1 modularly.
Given n such that: n2 = 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 x2 - Dy2 = 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 x2 - Dy2 = 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 m2 = 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 420282 - 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
No comments:
Post a Comment