# 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:

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.