# Sum of two relatively prime squares in two distinct ways

I hope that this isn't simple because I've been scratching my head with it:

In David Burton's "Elementary Number Theory", there is a question that says that in 1647, Mersenne noted that when a number can be written as a sum of two relatively prime squares in two distinct ways, it is composite and can be factored as:

$n=a^2+b^2=c^2+d^2$ implies $n=\frac{(ac+bd)(ac-bd)}{a+d)(a-d)}$.

The problem in the book merely asks the reader to use this for a particular example (n=493) but doesn't give a reason for the general case.

Now, my question is this: how was n factored in this way?

I've tried manipulating n in a few ways such as playing $n+n, n-n, n^2$ but I haven't had any luck. Any help would be awesome.

• there are two nice articles by Brillhart on this and extensions. Euler's first note on the problem gave your formula and proved there was a nontrivial factorization of $n$ that can be found from it. Later, Euler gave a more cookbook answer, messier to prove. – Will Jagy Jul 8 '16 at 18:45
• $(ac+bd)(ac-bd) = a^2 c^2 - b^2 d^2 = a^2 (c^2 + d^2) - (a^2 + b^2) d^2 = n (a^2 - d^2) = n (a+d)(a-d)$ – Robert Israel Jul 8 '16 at 18:58

Hint $\$ You can do this by taking gcds of Gaussian integers $\,\Bbb Z[i].\,$ Let $\,\alpha = a+bi,\ \beta = c+di.\$ Then $\,\alpha\bar\alpha = n = \beta\bar\beta.\,$ Since the rep's are different $\,\alpha\,$ is not associate to $\,\beta\,$ or $\,\bar \beta.\,$ Nor can $\,\alpha\,$ be coprime to both (else it would be coprime to their product, since $\,\Bbb Z[i]\,$ is a UFD). So it is not coprime to one of them, say $\,\gamma = \gcd(\alpha,\beta)\,$ is a nonuit. Then $\,\gamma\bar\gamma\,$ is a proper factor of $\,n = \alpha\bar\alpha$.
Remark $\$ This yields a constructive algorithm, using the simple Euclidean algorithm in $\,\Bbb Z[i].\,$