Monday, July 18, 2011

Two conics equation

A remarkable little equation has a fascinating story:

x2 - Dy2 = 1

In the field of rationals it can be solved as a parametric equation:

x = (D + t2)/(D - t2), y = 2t/(D - t2)

And notice that it gives two of the conic sections, as with D less than 0 it gives ellipses, giving the circle itself with D=-1.

With D greater than 0 it gives hyperbolas.

I have no idea how useful it is for, say, drawing those conic sections and haven't seen much on the subject on the web. But it can be used to draw, and D should be related to eccentricity.

Looking now at integer only solutions, so it is a Diophantine equation, which just means integers only, I'll introduce a simple relation.

Given x2 - Dy2 = F, it must be true that:

(x+Dy)2 - D(x+y)2 = -F(D-1)

You can verify the correctness of the second result by multiplying out:

x2 + 2Dxy +D2y2 - D(x2 + 2xy + y2) = -FD + F


x2 + 2Dxy +D2y2 - Dx2 - 2Dxy - Dy2 = -FD + F

so 2Dxy cancels out, and I can move things around to group like so:

x2 - Dy2 - Dx2 + D2y2 + FD = F

and notice I have my original equation negatively mirrored inside which is easier to see like so:

x2 - Dy2 - D(x2 - Dy2 - F) = F, so: x2 - Dy2 = F

So we've verified the relation as valid.

And I can use that relation over and over again to get a series. So now let's use it with our two conics equation, which means F=1, and let's use D=2, so now I can get a series, where here are the first five:

1. x2 - 2y2 = 1

2. (x+2y)2 - 2(x+y)2 = -1

3. (3x+4y)2 - 2(2x + 3y)2 = 1

4. (7x + 10y)2 - 2(5x + 7y)2 = -1

5. (17x + 24y)2 - 2(12x + 17y)2 = 1

so you can use the simple case of x=1 and y = 0:

1. 12 = 1

2. (1)2 - 2(1)2 = -1

3. (3)2 - 2(2)2 = 1

4. (7)2 - 2(5)2 = -1

5. (17)2 - 2(12)2 = 1

and get solutions.

That trick, however, only works to give you answers so easily for D=2.

For the curious I've delved far deeper into its use with the two conics equation, and found I could connect the two conics equation to what are called Pythagorean Triples.

And I used it to help explain why some integer solutions to the two conics equation are much bigger or smaller than others. A clue is the number of prime factors of D-1. If D-1 is prime then solutions tend to be small, but if it has a lot of small prime factors, and especially if 4 is a factor then solutions get much larger.

(Editing to note that subsequent research gave the full picture, while at this point I still just had one key part of it.)

For example a famous case is D=61, where 60 makes it big:

17663190492 - 61(226153980)2 = 1

But notice that for D=62, because 61 is prime it is much smaller:

632 - 62(8)2 = 1

It is possible to trivially prove that an infinite number of integer solutions for x and y exist, using one more equation.


(n2 + 1)2 - (n2 + 2)n2 = 1

multiplying out gives:

n4 + 2n2 + 1 - n4 - 2n2 = 1

So it simplifies to 1=1, so it's called an identity. In mathematics an equation is called an identity if it simplifies to a simple equality, like x=x or y=y, or 1=1. Notice then we can just let:

x = n2 + 1, y = n, and have a solution if D = n2 + 2

For example, if n=3, D = 11, and 102 - 11(3)2 = 1.

There are other such identities for the curious, and you can guess at them from the one shown.

What I call here the two conics equation is generally considered by mathematicians with integers only as a Diophantine equation, where "Diophantine" just means, integers only, so then D is usually an integer greater than 1, and mathematicians traditionally call the equation Pell's Equation.

But they also note that the name is a mis-attribution to a guy named John Pell. That is, he shouldn't have the equation named after him based on any contributions which he did, so it was a mistake for that to happen, and usually Euler is blamed for that mistake!

So the puzzle is, why don't mathematicians just quit calling it Pell's Equation if that is a mistake?

For years I've followed their tradition, but their tradition also includes ignoring the rational parametric solution, as they just focus on Diophantine equations, which may be a historical oddity as well.

Turns out that Fermat played with finding integer solutions as a competitive game with others and they thought the parametric equation was too easy for that game, as it made finding answers trivial. Finding integer answers only is harder. Their focus on integers only as a game became locked into a mathematical preference by the math community.

Since that was in the 17th century and near four hundred years ago, it seems to me it makes sense in the 21st century to just let that oddity go, use a more explanatory name, and at least mention the parametric solution. Remarkably mathematicians tend to refuse to even mention the parametric equation, except for the circle case. See: eqns. 16 & 17

Other disciplines are capable of letting go past mistakes.

James Harris

Thursday, July 14, 2011

Focus on modular arithmetic

One of the coolest mathematical areas to me is modular arithmetic and it shows up a LOT in my research, as it is a simplification tool, and a lot of my ideas simplify previously difficult and abstract areas of mathematics. It is critical in that simplification.

Most explanations of modular arithmetic that I've seen focus on what they call clock arithmetic, which is where with the clock things just cycle around. So you can't have 100 o'clock.

100 = 4 mod 12

So you have 4 o'clock, as that's the information you need, so succinctly modular arithmetic is about throwing away information you do not need. And with it you can do some really cool things.

Simple rule: with "mod" what is to the right of the equal sign is less than what is to the right of "mod" which is called the modulus. What is on the left of the equal sign may be greater.

When you consider something with "mod" you are said to be "modulo" a particular value, like with clocks you are modulo 12, or modulo 24, if you're not using am and pm.

Most mathematical texts don't use the regular equals sign with "mod" but instead use "≡" which is just adding one more line and if that doesn't show on your browser, it's just adding one more line beneath the normal equals. I did that for a while but soon got tired of it and just use the normal equals without I think losing anything.

As it is a fundamental branch of mathematics you can do an unlimited number of things with "mod" but usually its focus is with Diophantine equations, which are just situations where the answers are all integers, like -1, 0, 1, 2 or 3. So things like e or pi do not show up. And fractions like 1/2 or 1/3 do not usually show up, though they can be useful in a particular way.

Here's an example of something clever you can do with "mod", as, if you're just bored, you might wonder, if you square an integer and add 2, can it be divisible by 5? With modular arithmetic that is:

Does x2 + 2 = 0 mod 5 exist?

You can do a lot of typical algebra with modular arithmetic so that is the same as:

x2 = -2 mod 5, and you can add 5, to get rid of the negative, because what remains is less than 5, so you get: x2 = 3 mod 5

Important nomenclature issue: With 3 mod 5, 3 is called the residue, as it's what's left over, and often 0 is not considered a residue, but sometimes it may be, depending on the author. In my research 0 is not a residue. So, in my writing, the residue is what is to the left of "mod" as long as it is not zero.

Now we can look at all the positive residues modulo 5: 1, 2, 3, 4

And we can square them all: 1, 4, 9, 16

So we have 1 mod 5, 4 mod 5, 4 mod 5, and 1 mod 5

And you can see that only 1 and 4 are the residues when you square residues modulo 5, and they are called quadratic residues.

And our question is answered as 3 is not in that list! So no, it's not possible to add 2 to a square and have an integer divisible by 5.

Or stated another way, we've proven that the Diophantine equation x2 + 2 = 0 mod 5 has no solutions.

By focusing only on the necessary information and throwing everything else away, modular arithmetic allows you to answer questions that otherwise might seem impossible to answer, as you can answer questions over infinity.

You might think that the quadratic residue would always look like a square, but go up just a bit to modulo 7, and notice that 32 = 2 mod 7. So, no, the quadratic residue is not necessarily what is sometimes called a perfect square, which is redundant as you can just call it a square.

Now let's ask the math another question, if you multiply a number by 2 can it equal 3 modulo 5?

That is, does 2x = 3 mod 5 exist?

The answer is, yes. That's because of something called the modular inverse, which is a cool thing that lets you move that 2 from the left hand side to the right hand side:

x = (2-1)3 mod 5

It may seem complicated but it's just a number that you multiply times 2 to get 1 mod 5, and that number is: 3.

3(2) = 1 mod 5, so 3 is the modular inverse of 2 modulo 5.

So now we have: x = (2-1)3 mod 5 = (3)3 mod 5 = 4 mod 5.

The modular inverse will always exist as long as it is not a factor or does not contain factors of the modulus. So we could not do the same thing with 2x = 3 mod 10, which does not exist.

Here also is where you can use fractions instead, as you could have said:

x = 3/2 mod 5 = 3(3) mod 5 = 4

However, very important, with modular arithmetic something that looks like a fraction is never really a fraction, but is instead an actual whole number where you may use the form of a fraction simply as an intermediate step.

Sometimes you need to move from "mod" to what is called an explicit equation, and that's easy!

For example x = 4 mod 5 is equivalent to x = 4 + 5k, where k is some non-zero integer, where usually you have no idea what its actual value is. That is the information that is being thrown away, so there are an infinity of k's usually that will work. And that goes again to the power of "mod" as it always to some extent involves infinity.

And that is just a quick overview of some of the basics with modular arithmetic, where you can learn a lot more as it is a huge subject from many sources including the Wikipedia article on modular arithmetic.

James Harris