# Who first proved that only primes of the form $4k+1$ divide odd integers of the form $n^2+1$?

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$$.

• 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... – paul garrett Feb 11 '19 at 18:13
• 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. – Carl Witthoft Feb 12 '19 at 13:20
• 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. – Spencer Feb 12 '19 at 23:24

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 $$ 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.

• 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. – KCd Feb 12 '19 at 9:11