Finding math derivations is something I enjoy doing, where I like finding multiple ones for the same thing as it helps understanding, and is an enjoyable exercise for me. So here is a post deriving a result I've already derived.
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.
Here I'll give a different derivation by considering two modular equations:
r = x + ny mod p
and
r-1 = x - ny mod p
Since r(r-1) = 1 mod p, I can just multiply and get:
r(r-1) = 1 = x2 - n2y2 mod p
Which is: x2 - n2y2 = 1 mod p
And introduce D, such that: D = n2 mod p, and I have: x2 - Dy2 = 1 mod p
Solving for x and y then is just a matter of adding and subtracting and simplifying with my original equations. Adding to solve for x and subtracting to solve for y, to get finally:
2x = r + r-1 mod p, and 2y = n-1(r - r-1) mod p
Here I like leaving the 2 on the left side as I think it is a little bit cleaner. And looking modulo p, means I don't have to worry if the modular inverse exists. Note, I don't consider 0 to be a residue.
This result will solve the original equation explicitly and non-trivially if you have p greater than x and y, and you happen to pick the right residue! Or just run through them all till you find it. So it's not like it's practical. But I like it.
Oh yeah, it will solve explicitly non-trivially as long as D is not a perfect square, because if D is a perfect square then you have (x-ny)(x+ny) = 1, which has only x=1 or -1, y = 0 as an integer solution.
Re-deriving results over and over again is maybe one of those things that others might not understand, but I think it's fun, and it's something that keeps the mind active for a bit before moving on to other things.
James Harris
No comments:
Post a Comment