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

Prime Counting 10 Year Anniversary

So I should acknowledge an intriguing milestone as it has been 10 years since I found a way to count prime numbers using, for the first time known, a difference equation:

With natural numbers

P(x,y) = x - 1 - sum for j=2 to y of {(P([x/j],j-1) - P(j-1, sqrt(j-1)))(P(j, sqrt(j)) - P(j-1, sqrt(j-1)))}

where if y>sqrt(x), then P(x,y) = P(x,sqrt(x)).

Because it is a difference equation you do not need to tell the equation any prime numbers.

To count primes up to 100, for example, you'd calculate P(100,10), which gives 25.

For me it was always fascinating as I found the original form working at the computer.

It was such a fascinating feeling August of 2002, ten years ago, when that computer screen filled up with prime numbers, found as the full count took place. It finds the primes up to the square root, so if you're counting to 100, it finds 2, 3, 5 and 7. If you're counting primes up to 10000, it finds primes up to 100 as it counts. So cool.

It does have a sieve form, where you give it those primes instead of letting the math find them, which is what can be made faster as in iterating through to count with the fully mathematicized form, it's doing some calculations over and over again. The sieve form helps stop that repetition so it's faster:

Still with natural numbers where p_j is the j_th prime:

P(x,n) = x - 1 - sum for j=1 to n of {P(x/p_j,j-1) - (j-1)}

where if n is greater than the count of primes up to and including sqrt(x) then n is reset to that count.

Because you're using natural numbers, no fractions or decimals, so those are just dropped. So 10/3 is 3 with just natural numbers, the sqrt() is the integer square root, for instance sqrt(10) = 3, as that's floor(sqrt(10)), and it's automatically positive because natural numbers are only the positive integers greater than 0.

But if you're not looking for something faster to count primes, it's more interesting to probe the difference equation further, and follow it through to a differential equation!

Continuous function:

In the complex plane

P'_y(x,y) = -(P(x/y,y) - P(y, sqrt(y))) P'(y, sqrt(y))

is the partial differential equation that follows from the difference equation.


James Harris

Derivations are fun

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: 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.

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 = x² - n²y² mod p

Which is: x² - n²y² = 1 mod p

And introduce D, such that: D = n² mod p, and I have: x² - Dy² = 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

My math comfort

For years I've realized I find comfort in the solidity of mathematics and turn to it when the world seems screwy, or I'm under a lot of pressure. Then I kind of reflexively find myself musing on some result and I feel better, as math can give you that certainty that can be missing in an often arbitrary world.

And recently I've found myself turning often to the equation x² - Dy² = 1. I've found quite a few things about it, and lots of results about it that I enjoy. Here I'll talk about one of the latest.

Back in June of this year I noticed a way to solve for x and y mod p, where p is a prime for which D is a quadratic residue, so there exists n such that: n² = D mod p

Then where r is any residue modulo p:

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

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

So you don't necessarily get an explicit answer to the original equation, but you can use any prime p you want as long as D is a quadratic residue. You can easily move to composite N versus prime p, but I find it simpler to just focus on primes for just playing around, so for instance I know the modular inverse will exist.

And you can find p as big as you want.

Now let's plug in some numbers! For me with number theory it's so cool when you watch the numbers follow the rules. Perfectly. They do it with absolute perfection.

Here I'll use D=23, and I just checked and it's a quadratic residue of 101, which I picked arbitrarily. So let p=101. Then n = 15 is a solution, as 15² = 23 mod 101.

And I need its modular inverse and 15^-1 = 27 mod 101.

And I can use whatever residue I want for r, where I note I don't consider 0 a residue, and 1 would be boring I'm sure, and 2 might be ok, but I'll just use r = 3, because that might be more interesting.

And I need its modular inverse and 3^-1 = 34 mod 101.

So now I can solve for x and y:

2x = 3 + 34 = 37 mod 101, and 2y = 27(3 - 34) = 27(-31) = 27(70) = 72 mod 101.

And now I need the modular inverse of 2, and 2^-1 = 51 mod 101.

So:

x =51(37) = 69 mod 101, and y = 51(72) = 36 mod 101

So do they work? They HAVE to work, as it's math! But let's plug them in and check:

69² - 23(36)² = -25047 = 1 - 248(101) = 1 mod 101

So they work! But of course they do, it's math.

But you don't get an explicit solution for x and y, and I'm curious about what r would give it to you.

I looked up the explicit solution even though it's easy to figure it out, and it is:

x = 24, and y = 5, as 24² - 23(5)² = 1

From my derivation I have that r = x + ny mod 101, so: 24 + 15(5) = 99.

So guess I should have worked down from 101 instead of up!

The interested reader can run through with r = 99 and see that it all works.

And for me that is relaxing! It is just really cool seeing the numbers do as expected. And they follow rules that I found! Is it really practical? What do I care. I like the perfection and keeping my mind occupied.

For years when the world stresses me, I've had my math to rely on. It's a comfort like no other, and its perfection is a great shelter.


James Harris