Diophantine Equations

\(a = xy\)

Say we want to find \(x\), \(y\), and we are given \(a\). This is just factorization. If we have to do this repeatedly for many numbers, the most efficient way is to use a sieve, which will factorise many numbers at once.

\(a = x^2 - y^2\)

This is a difference of squares. In this case, we can factorise out \(a = (x + y)(x - y)\). Let \(m = x + y\) and \(n = x - y\), then we have \(a = mn\) which we can solve by factorisation. Once we have \(m\) and \(n\), we can find \(x\) and \(y\) again.