Fermat postulated that all numbers of the form $$2^{2^n}+1$$ are prime (where n = any integer). Then Euler came along with a rather ingenious proof that this was not, in fact the case. I came across this while reading William Dunham's Journey Through Genius, Chapter 10.
Here's the gist of what I get so far (of how Euler refuted Fermat's above suggestion):
Theorem A: If $a$ is an even number, and $p$ is prime that does not factor evenly into $a$ (but is a factor of $a+1$), then $p = 2k+1$ for an integer $k$.
So far so good, and Dunham discusses the proof for this theorem, but I'm going to guess that you mathematicians here are familiar with this.
Next we move onto Theorem B.
Theorem B: If $a$ is an even number and p is a prime (not a factor of $a$), and $p$ goes evenly into $a^2+1$, then for an integer $k$, $p = 4k+1$, but $p$ cannot equal $4k+3$.
Here's how this works:
Firstly, $a$ is even, so $a^2$ is also even. Using Theorem A, it becomes obvious that any prime factor of $a^2+1$ is odd. Ergo, $p$ is odd (so it's not 2).
If we divide $p$ by 4, then $p$ can equal either $4k+1$ or $4k+3$.
Since $p$ is a divisor of $a^2+1$, p also divides evenly into the product ($a^2+1$)($a^{4k}-a^{4k-2}+a^{4k-4}...+a^4-a^2+1$). Algebraic manipulation shows that this product equals $a^{4k+2}+1$.
And this is where I'm confused. Where on earth does Dunham pull ($a^{4k}-a^{4k-2}+a^{4k-4}...+a^4-a^2+1$) from? No explanation is offered on his part, so any enlightenment on this would be appreciated.
More Details As stated earlier, if we divide $p$ by 4, then $p$ can equal either $4k+1$ or $4k+3$ (which is pretty clear if you plug in values for $k$). We want to demonstrate that $k$ can only equal $4k+1$, and we do this by proof by contradiction (assume $p=4k+3$). Why do we want to do this? Well, we want to know the form of $p$ so we can figure out the potential factors of $2^{32}+1$, which Fermat postulated was prime.
Since $p$ is not a divisor of $a$ (by hypothesis), Fermat's little theorem would suggest that $p$ goes nicely into $a^{p-1}-1=a^{{4k+3}-1}-1=a^{4k+2}-1$.
Says Dunham (p. 231):
"On the other hand, we have assumed that $p$ is a divisor of $a^2+1$, and consequently $p$ is also a divisor of the product ($a^2+1$)($a^{4k}-a^{4k-2}+a^{4k-4}...+a^4-a^2+1$)."
Since this product equals $a^{4k+2}+1$, and since $p$ goes evenly into both $a^{4k+2}+1$ and $a^{4k+2}-1$, $p$ is a divisor of ($a^{4k+2}+1$)-($a^{4k+2}-1$) = 2, but this cannot be true since $p$ is an odd prime. Ergo, $p$ is not of the form $p=4k+3$.
Let me know if you all need more details and stuff.
Let me rephrase the argument, and put the contradiction in another place:
Let $a$ be an even integer, and let $p$ be a prime dividing $a^2+1$. Then $p$ is odd because $a^2+1$ is odd, so $p$ has remainder $1$ or $3$ after division by $4$, that is, either $p=4k+1$ or $p=4k+3$ for some integer $k$.
Suppose towards a contradiction that $p=4k+3$ for some integer $k$. By Fermat's little theorem we know that $p$ divides the number $$a^{p-1}-1 = a^{4k+2}-1,$$ and it is clear that $p$ does not divide $2$. It follows that $p$ does not divide $a^{4k+2}+1$. By assumption $p$ divides $a^2+1$, and $a^2+1$ in turn divides $a^{4k+2}+1$. But then $p$ divides $a^{4k+2}+1$, a contradiction.
To see that $a^2+1$ divides $a^{4k+2}+1$, one can write out the multiplication $$(a^2+1)(a^{4k}-a^{4k-2}+a^{4k-4}+\ldots+a^4-a^2+1).$$ This may seem like magic, but with the use of some abstract algebra one can quickly see that $a^2+1$ must divide $a^{4k+2}+1$, without having to figure out how many times $a^2+1$ fits into $a^{4k+2}+1$ exactly. Once you know that one divides the other, you can apply (for example) Euclid's algorithm to find precisely how many times $a^2+1$ fits in $a^{4k+2}+1$. In this way you may find the big and nasty expression $a^{4k}-a^{4k-2}+a^{4k-4}+\ldots+a^4-a^2+1$, but the only purpose of this expression in the proof is to show that $a^2+1$ divides $a^{4k+2}+1$.
It is worth noting that a bit of abstract algebra allows for a much shorter proof of Theorem B. It requires only some modular arithmetic and group theory:
Let $p$ be an odd prime dividing $a^2+1$, so that $a^2\equiv-1\pmod{p}$. Then $a$ has order $4$ in $(\Bbb{Z}/p\Bbb{Z})^{\times}$, hence $4$ divides the order of $(\Bbb{Z}/p\Bbb{Z})^{\times}$, which is $p-1$. This shows that $p=4k+1$ for some $k\in\Bbb{Z}$.