0
$\begingroup$

I'v learnt from this site that a composite number $n$ can be expressed as the sum of two squares if and only if its prime factor do not contain a prime $p \equiv3 \pmod 4$ which is powered to even power. To my understanding, if and only if means that if a number $n$ factors to $p \equiv3 \pmod 4$ with an even power, it must be composable as the sum of two squares. However, $49=7^2$, which is an even power of $7$, but still cannot be composed as the sum of two squares bigger than $0$. How can it leave together with the above statement?

$\endgroup$
3
$\begingroup$

The original statement requires that $0^2$ is a valid square. If you disallow this, some squares will fail. See https://en.wikipedia.org/wiki/Pythagorean_triple on more information on which squares still work.

$\endgroup$
3
$\begingroup$

The problem occurs if there is a prime factor equivalent to $3$ modulo $4$ which appears to an odd power in the factorisation. The statement you have given is awkwardly expressed and incorrect. For a few more details see below.

Using complex numbers we have $$(a+bi)(c+di)=(ac-bd)+(ad+bc)i$$

Almost magically we find that $$(ac-bd)^2+(ad+bc)^2=(a^2+b^2)(c^2+d^2)$$

So if two numbers $p=a^2+b^2$ and $q=c^2+d^2$ are the sum of two squares then so is $pq$.

Also so is $pn^2=(an)^2+(bn)^2$ for any integer $n$.

Integers $\equiv 3 \bmod 4$ cannot be expressed as the sum of two squares.

It can be shown that all prime numbers $\equiv 1 \bmod 4$ and also the prime $2=1^2+1^2$ can be expressed as the sum of two squares.

So when we factorise a number into its prime factors, the ones which will cause a problem are the primes equivalent to $3$ modulo $4$. If these are present to an even power, that is fine (we can multiply by any square number and preserve the property). If any such prime is present to an odd power, then there is no decomposition into two squares.

There are various statements above which have to be proved to get a rigorous answer. None is particularly difficult, and standard texts and references on number theory will cover the details.

$\endgroup$
  • $\begingroup$ Sorry for the in successful formulation-it seems my english is not that good. The inverse of what you wrote is also true? that is, given that p*q can be expressed as a sum of two squares, so thus p and q themselves? $\endgroup$ – Evgeni Vaknin May 23 at 5:34
  • 1
    $\begingroup$ @EvgeniVaknin Consider $9*49=441=21^2$ (if necessary ie $0^2$ is not available, multiply by $2$ to obtain $882=21^2+21^2=21\cdot 42$. Note that neither $21$ nor $42$ are the sum of two squares. This factorisation puts takes an even power of a prime $\equiv 3 \bmod 4$ and splits it into two pieces. More simply consider $9=3^2$ or $18=9+9=3\cdot 6$ $\endgroup$ – Mark Bennet May 23 at 5:40

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.