It is well known (since Euler) that if a positive integer $N$ can be written as a sum of two squares in at least two essentially different ways, then $N$ is composite.

In other words, if

$N=a^2+b^2=c^2+d^2$ with $\{a,b\}\neq \{c,d\}$ and $a, b, c, d$ nonnegative integers, then $N$ must be composite.

The condition is sufficient as there are many composites which cannot be written as a sum of two squares: $6, 12, 14, 15, 21, 22, \ldots$.

Are there any other similar sufficient criteria (similar in the sense that they involve quadratic forms) which ideally cover a larger subset of composites?

  • 1
    $\begingroup$ Replace $a^2+b^2$ with $a^2+nb^2$ for any fixed $n>0$. Then every prime has at most one representation with $a,b\geq 0$. $\endgroup$
    – Wojowu
    Jan 26 '19 at 14:54
  • 1
    $\begingroup$ zakuski.utsa.edu/~jagy/Brillhart_Euler_factoring_2009.pdf $\endgroup$
    – Will Jagy
    Jan 26 '19 at 16:56
  • 2
    $\begingroup$ Replace $a^2+b^2$ with $a^2-b^2$. $\endgroup$ Jan 26 '19 at 21:11
  • 1
    $\begingroup$ @GerryMyerson Very funny Gerry! $\endgroup$
    – user84909
    Jan 27 '19 at 0:17

Your Answer

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

Browse other questions tagged or ask your own question.