0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Will Jagy Jul 8 '16 at 18:45
  • 1
    $\begingroup$ $(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) $ $\endgroup$ – Robert Israel Jul 8 '16 at 18:58
2
$\begingroup$

Apparently I made jpegs of bits from the first Brillhart article,

enter image description here

enter image description here

$\endgroup$
  • $\begingroup$ This answer has been very helpful. Thank you! $\endgroup$ – user328442 Jul 8 '16 at 19:14
2
$\begingroup$

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].\,$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.