I am writing a paper and I would like to cite the person(s) who proved that only primes of the form $4k+1$ can evenly divide odd integers of the form $n^2+1$?

For example, if $n=8$, $n^2 + 1 = 65$ which is evenly divisible by 5 and 13, both of which are of the form $4k + 1$.

  • 1
    $\begingroup$ I don't know an answer to your question, but certainly Fermat knew such things, so the discovery of the fact would have been earlier... $\endgroup$ Feb 11, 2019 at 18:13
  • 1
    $\begingroup$ Just want to mention that, for purposes of validating your overall work, any citation of a book which contains a proof of this theorem suffices. I do applaud your intent to (in addition) give credit to the first person to find a proof. $\endgroup$ Feb 12, 2019 at 13:20
  • 1
    $\begingroup$ Oystein Ore, in his book Number Theory and its History mentions that Brahmagupta worked with numbers of this form in the 6th Cenrury BCE. But Ore just named the works and didn't go into detail. However, Ore discusses the sums of two squares at several places in his book. $\endgroup$
    – Spencer
    Feb 12, 2019 at 23:24

1 Answer 1


It would seem to be Euler. Dickson, in Ch. XVI of History of the Theory of Numbers, writes the following:

"Euler discussed the numbers $a$ for which $a^2+1$ is divisible by a prime $4n+1=r^2+s^2$. Let $p/q$ be the convergent preceding $r/s$ in the continued fraction for $r/s$; then $ps-qr=1$. Thus every $a$ is of the form $(4n+1)m\pm k$, where $k=pr+qs$. Euler gave the $161$ integers $a< 1500$ for which $a^2+1$ is a prime, and the cases $a= 1, 2, 4, 6, 16, 20, 24, 34$ for which $a^4+1$ is a prime.

The first appearance is in the letter to Goldbach from July 9, 1743. Euler came back to these numbers in 1755 and 1762:

[...] Euler treated the problem to find all integers for which $a^2+1$ is divisible by a given prime $4n+1=p^2+q^2$. If $a^2+b^2$ is divisible by $p^2+q^2$, there exist integers $r,s$ such that $a=pr+qs,b=ps-qr$. We wish $b=\pm1$. Hence we take the convergent $r/s$ preceding $p/q$ in the continued fraction for $p/q$. Thus $ps-qr=\pm1$, and our answer is $a=(pr+qs)$. He listed all primes $P=4n+1<2000$ expressed as $p^2+q^2$, and listed all the $a$'s for which $a^2+1$ is divisible by $P$. The table may be used to find all the divisors $<a$ of $a$ given number $a^2+1$. He gave his table and tabulated the values $a<1500$ for which $(a2+1)/k$ is a prime, for $k=2, 5, 10$. He tabulated all the divisors of $a^2+1$ for $a\leq1500$."

Fermat is mentioned on the same page, but only in connection with something else, so I doubt that he looked into factorizations of $a^2+1$. Lehmer in Guide to Tables in the Theory of Numbers (p.31) also names Euler as the first to produce a factorization table of $a^2+1$ numbers in 1762, and nobody else.

As for Fermat, there are almost no proofs by him in existence, a notable exception is a case of his Last theorem for $n=4$. Euler generally made it his task to sort out Fermat's guesses. For example, Fermat "knew" that $2^{2^n}+1$ were all primes, after checking the first four. Euler computed $2^{2^5}+1=641\times6700417$. No other primes of this form turned up since.

  • 3
    $\begingroup$ Fermat claimed in letters that he could use his method of descent to show any prime dividing a number of the form $n^2+1$ is a sum of two squares, so unless the prime is $2$ it has to be $1\bmod 4$. See page 67 of Weil's Number Theory: an Approach Through History. $\endgroup$
    – KCd
    Feb 12, 2019 at 9:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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