Diophantus

In order to learn Java, I’m reconstructing some (long since lost) code that I wrote in Mathematica as a graduate student.

Back when you memorized your multiplication tables as a kid, something that made that task easy was the Fundamental Theorem of Arithmetic, which states that every natural number larger than 1 factors uniquely into prime numbers.

However, there are other, stranger algebraic structures where factorizations need not be unique.

Let d denote a negative, square-free integer. If we consider the set

Z[sqrt(d)] = { a + b * sqrt(d) | a,b are integers }

</center>

then, it turns out that irreducible factorizations need not be unique. In particular, if d = -5, then we have

6 = 2 * 3 = (1 + sqrt(-5))(1 - sqrt(-5))

and it can be shown that each of 2, 3, 1+sqrt(-5), 1-sqrt(-5) are irreducible (ie they “can’t be broken down anymore” under multiplication).

The ultimate aim of this software distribution is to compute, for given a,b, and d, all of the irreducible factorizations of a + b * sqrt(d) in Z[sqrt(d)].

Example

Take a look at the file Diophantus.java in com.jackmaney.Diophantus. The source of that file (as of this writing) is:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
package com.jackmaney.Diophantus;


import com.jackmaney.Diophantus.element.Element;


public class Diophantus {

    public static void main(String[] args) {
        Element e = new Element(6,0,-5);

        System.out.println(e.getIrreducibleFactorizations());


    }

}

Note that we’re creating a new Element that corresponds to 6 = 6 + 0 * sqrt(-5). The output is a Vector of Factorizations that, when printed, looks like

[(1 - 1 * sqrt(-5))*(1 + 1 * sqrt(-5)), 2*3]

conforming to our expectations above. Of course, feel free to tinker around with the parameters in this class. For example:

The irreducible factorizations of 81 in Z[sqrt(-14)] are [(5 - 2 * sqrt(-14))*(5 + 2 * sqrt(-14)), 3^4].
There is only one irreducible factorization of 1024 + 768 * sqrt(-39) in Z[sqrt(-39)], namely 2^8*(4 + 3 * sqrt(-39)).
That doesn't mean that every element of Z[sqrt(-39)] enjoys unique factorization! The factorizations of 1000 + 1000 * sqrt(-39) are:
```
[5*(19 + 1 * sqrt(-39))*(29 + 9 * sqrt(-39)),
2*5*(7 + 3 * sqrt(-39))*(31 + 1 * sqrt(-39)),
2^3*5^3*(1 + 1 * sqrt(-39))]
```

There are two factorizations of 1024 + 768 * sqrt(-191) in Z[sqrt(-191)]:

[(33 + 1 * sqrt(-191))*(141 + 19 * sqrt(-191)),
2^8*(4 + 3 * sqrt(-191))]

Why "Diophantus"?

Diophantus of Alexandria was an ancient Greek mathematician and philosopher after whom Diophantine equations are named. Finding irreducible factors of a given element of Z[sqrt(d)] hinges upon finding integer solutions for x and y to the following Diophantine equation:

x^2 - d * y^2 = n

Hence, the name.