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
Post a Comment