How to write an integer into a product [duplicate]
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.
Solution 1:
Apparently I made jpegs of bits from the first Brillhart article,
Solution 2:
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].\,$
This is best viewed from a slightly more general perspective as follows. In any $\rm UFD$, if $\rm\ a\ $ is not prime, i.e. $\rm\ a\:|\:bc\ $ but $\rm\ a\nmid b,\ a\nmid c\ $ then $\rm\ \gcd(a,b)\ $ is a proper factor of $\rm\,a.\,$ Moreover this gcd can be computed when a $\rm UFD$ has a constructive Euclidean algorithm, as does $\rm \mathbb Z[i]\:$. Therefore this yields a constructive proof that nonprime nonunits are reducible in Euclidean domains (i.e. the nontrivial half of the equivalence of irreducible and prime elements in $\rm UFDs$).