Sunday, December 23, 2012

Concepts in binary quadratic Diophantine equations

While I am NOT a mathematician I have found myself playing around with intriguing ideas around what are called binary quadratic Diophantine equations and thought it would be a good idea to explain the basics as I know them.

First off binary quadratic Diophantine equations are when you look for integer solutions to equations like:

c1x2 + c2xy + c3y2 = c4 + c5x + c6y

Here x and y are the unknowns to be figured out. An example of such an equation is:

x2 + 2xy + 3y2 = 4 + 5x + 6y

where I've simply used,  c1 = 1, c2 = 2, c3 = 3, c4 = 4, c5 = 5, c6 = 6.

Such equations are also called binary quadratic forms, and in general can be reduced to a more basic binary quadratic form, like:

u2 - Dv2 = C

Here the letters used don't matter, of course, and in this case u and v represent the unknowns.

With my simple example above that reduction to the simpler form using my own research gives:

(-4(x+y) + 10)2 + 2s2 = 166

So to fit into the form above:

u = -4(x+y) + 10 and v = s, while D = -2, and C = 166.

The reason to reduce to a simpler form is to aid in finding solutions. And in this case I can find the answers rather simply.

Subtracting 2s2 from both sides the equation above is:

(-4(x+y) + 10)2 = 166 - 2s2 = 2(83 - s2)

Running through possible odd s's I notice that s=9 works to give -4(x+y) + 10 = 2 or -2, so x+y = 2, or x+y = 3. And x = 4, y = -2, or x = 5, y = -2 work.

The letters do not matter so the general form can also be written as x2 - Dy2 = F.

That form has a modular solution for x and y.

Given x2 - Dy2 = F where all variables are non-zero integers:

With a non-zero integer N for which a residue m exists where--m2 = D mod N, and r, any residue modulo N for which Fr-1 mod N exists then:

2x = r + Fr-1 mod N and 2my = r - Fr-1 mod N

It is derived here.

That result gives solutions to x2 - Dy2 = F mod N.

If modular arithmetic is unfamiliar to you, I have my own short introduction.

And that covers enough of the basic concepts of binary quadratic Diophantine equations to help in understanding my posts on the subject.

James Harris

No comments: