## Thursday, November 03, 2011

### A Neat Trick

The idea that modern advances in knowledge can greatly enhance and simplify is potent in just about every field of human endeavor and is fun for the amateur math researcher, where I can use a neat trick only available with modular arithmetic.

Consider x2 - Dy2 = 1, where mathematicians like to study it as a Diophantine equation, which means you try to find integer solutions, and in its case you look for nonzero ones instead of the trivial case where y=0. Nonzero integer solutions are called the fundamental solution and the equation is called Pell's Equation, in honor of John Pell, though oddly enough mathematicians also say he doesn't deserve it.

People have studied the equation for thousands of years, but modular arithmetic has been around for a lot shorter time, so a nifty solution was not possible until the time of Gauss, where I will shift its form to use a neat trick:

(z-y)2 - Dy2 = 1

Expand out:

z2 - 2yz + y2 - Dy2 = 1

Now obviously, it makes sense to group the y2, and see:

z2 - 2yz - (D-1)y2 = 1

And I've talked about this before in other posts, but zipped past what is an amazing trick, which only arrived with modular arithmetic, as before, to mathematicians who did not have it, the above would be pointless.

They literally could not see what happens next:

z2 - 2yz = 1 mod D-1

And now you can move that 1 to the left hand side: z2 - 2yz - 1 = 0 mod D-1

And solve for y, to find:

2y = z-1(z2 - 1) mod D-1

Without a way to solve for y modularly--as it hadn't been invented yet--previous math people found various clever ways to get solutions. And if you read about "Pell's Equation" on the web you can get a lot of history lessons on what they did, while I just solved it modularly, very quickly.

Now a modular solution is not necessarily an explicit answer, but the technique given can be generalized, with another variable, I'll call k:

(z-ky)2 - Dy2 = 1

Which gives from the same steps above:

2y = (kz)-1(z2 - 1) mod D-k2

which can also be written as:

2y = k-1(z - z-1) mod D-k2

where you also get an added rule, as z2 - 2kyz - 1 = (D-k2)y2, shows that D-k2 cannot be a square, if k is even.

Notice that k and z are forced to be coprime to D-k2 so that the modular inverses exist.

Turns out that I need one more equation.

Going back to: (z-ky)2 - Dy2 = 1

Let's add k2y2 to both sides: (z-ky)2 + k2y2 - Dy2 = k2y2 + 1

and now again focusing mod D-k2, I have:

(z-ky)2 = k2y2 + 1 mod D-k2

And I have what I like to call a quadratic residue engine, which then is as follows.

Given (z-ky)2 - Dy2 = 1, it must be true that:

2y = k-1(z - z-1) mod D-k2

(z-ky)2 = k2y2 + 1 mod D-k2

when if k is even, D-k2 is not a square.

Now you can get as many modular solutions for y as you want, and use them to get answers for y with something called the Chinese remainder theorem.

While I will not work it all the way through, it may help to get a sense of how it might work with a famous large case, which is D=61, which I looked up on the web to find that x = 1766319049, y = 226153980.

17663190492 - 61*2261539802 = 1

Let's start with k=1, and notice that 2y = (z - z-1) mod 60, requires that z be coprime to 60 so that its modular inverse exists, which means that z can only be: 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 49, 53, or 59.

But the second equation show things are even simpler than that might indicate:

(z-y)2 = y2 + 1 mod 60, which requires that y=0 mod 60 or you need a quadratic residue that when 1 is added to it, is STILL a quadratic residue, which is called a quadratic residue pair, of which there is only one modulo 60, as here are all the quadratic residues modulo 60:

1, 4, 9, 16, 21, 24, 25, 36, 40, 45, 49

So we know that y2 = 0 mod 60 or y2 = 24 mod 60, so despite having 14 possible z's, there are only a few possible answers for y. And since we have the fundamental answer it's easy enough to see that 30 is in fact a factor of 226153980.

The curious might wonder with 2y = (z - z-1) mod 60, with all the possible z's, how many cases for y=0 come up.

Those cases for z are: 11, 19, 29, 31, 41, 49, 59, where for all those y2 = 0 mod 60.

(Intriguingly, for all the other cases the modular inverse of z is a prime number, which I'm not sure is significant.)

So you could have two possibilities for y mod 60, since for y2 = 24 mod 60, you'd only need one answer, and then can go on to other values by shifting k. But notice that 2 and 3 are definitely factors of y. So fewer possibilities with, k=2, as then you're modulo 57, where you know that 3 has to be a factor of y. And the quadratic residues modulo 57 are:

1, 4, 6, 7, 9, 16, 19, 24, 25, 28, 30, 36, 39, 42, 43, 45, 49, 54, 55

And each possible y is indeed forced to have 3 as a factor.

At k=3, you have modulo 52, which has for quadratic residues:

1, 4, 9, 12, 13, 16, 17, 25, 29, 36, 40, 48, 49

And at k=4, you are modulo 45, which has for quadratic residues:

1, 4, 9, 10, 16, 19, 25, 31, 34, 36, 40

That again shows 3 is a factor and gives 5 a choice, as y2 = 0 mod 45 is possible.

It is of interest that the k=6 case is blocked because k is even and 61 - 36 = 25, which is a square. That case has no quadratic residue pairs and if not blocked would falsely indicate that 5 must be a factor of y.

And still a long ways away from getting the actual answer for y, which is HUGE, but intriguingly enough, there is a short-cut, which in this case is to use m2 - 61n2 = -1, which has a solution here, as all the tricks above work with it, though the equations shift a bit.

It gives a solution to "Pell's Equation" from: x = 2m2 + 1.

For instance,

297182 - 61*38052 = -1, so m = 29718, gives

x = 1766319049, from x = 2m2 + 1

Notice the k=6 case is valid here as the rule that D-k2 cannot be a square if k is even doesn't apply and 5 gets forced as a factor. The curious reader can see how things shift for the other factors. I looked the answer up here as well, but 3805 is a lot more accessible so probably could have calculated that if I were interested in the effort.

With D a prime, if m2 - Dn2 = -1 doesn't have solutions then the other alternate equations m2 - Dn2 = -2 or m2 - Dn2 = 2, will, where again their answers are much smaller.

Lots of fun things then thanks to the advance called modular arithmetic, which allows you to just solve for y modularly, where without it, things are not so easy.

And possibly new ways to approach getting explicit answers where I just glanced at the surface of what is to me a less interesting issue, as people have ways of getting those now using other techniques.

James Harris