how about fermat's theorem that all primes of form 4k+1 are sums of 2 squares?
Here is a sketch:
Fermat’s Theorem on Sums of Two Squares
The secret to understanding which integers are sums of two squares lies in introducing complex (“imaginary”) numbers. All numbers exist in our minds of course, hence are imaginary so we no longer use this old fashioned term for them, except informally or out of habit. Just as real numbers correspond to points on the line, complex numbers correspond to points on the plane, so just as it takes two real coordinates to describe a point in the plane, it takes two real numbers to describe a complex number. We define a complex number to be an ordered pair of real numbers (a,b). We add them by adding each coordinate separately, i.e. (a,b) + (c,d) = (a+c,b+d). The multiplication is more complicated, and we define (a,b)(c,d) = (ac-bd, ad+bc). In fact our new multiplication is commutative and has all the other properties you would expect of a multiplication (associative, and especially distributive).
The definition can be made easier to remember as follows: notice that in our multiplication the complex number (1,0) is a multiplicative identity, since (1,0)(a,b) = (1a-0b, 1b+0a) = (a,b). Thus it is natural to call this number “1”, i.e. to set 1 = (1,0). On the other hand the complex number (0,1) has the interesting property that when you square it you get -1, i.e. (0,1)(0,1) = (0-1,0+0) = (-1,0) = -1. This is news, since we never had a number whose square was -1 before. If we denote this interesting complex number by “i”, i.e. if we set i = (0,1), then every complex number can be written in one and only one way as a linear combination of 1 and i as follows: (a,b) = (a,0) + (0,b) = a(1,0) + b(0,1) = a1 + bi = a+bi. From now on we drop the clunky notation of (a,b) for a complex number and use a+bi instead, where a and b are real numbers. Now the multiplication is easy to remember, because all you need to know is that i^2 = -1. I.e. now (a+bi)(c+di) = ac + adi + bic + bidi = ac +adi + bci + bdi^2 = ac +adi + bci -bd = (ac-bd) + i(ad+bc), and this is the same answer we got before for this multiplication, namely
(ac-bd, ad+bc).
We are interested only in complex numbers a+bi where a and b are both integers, and we call them “Gaussian integers”. They are the complex version of the integers. The useful property they have in relation to the problem of the sum of two squares is this: if n = a^2 + b^2, where n, a and b are natural numbers, then we can factor n as n = (a+bi)(a-bi) in the Gaussian integers. To see this, just use the old “difference of two squares” formula. I.e. now that -1 is a square, a sum of two squares behaves exactly like a difference of two squares, so we have = n = a^2 + b^2 = a^2 - b^2(-1) = a^2 - b^2i^2 = a^2 - (bi)^2 = (a+bi)(a-bi). Thus a number n like this which is a sum of two squares, even if it is prime in the usual integers, is no longer prime in the Gaussian integers.
An example is 13, since 13 = 4+9 = 2^2 + 3^2 = (2+3i)(2-3i). Now notice that 13 is congruent to 1 mod 4. We have already proved that a number congruent to 3 mod 4 cannot be written as a sum of two squares. We claim that if n is a prime integer congruent to 1 mod 4, then n can be written as a sum of two squares.
All we have to do is prove that n is not prime in the Gaussian integers, since then it can be factored as a product of two Gaussian integers, n = (a+bi)(c+di) and by taking absolute values, then n^2 = (a^2+b^2)(c^2+d^2). Since n is prime then n = a^2+b^2. Thus if n is a prime integer which can be factored in the Gaussian integers, we could write n as a sum of two squares. Thus writing a prime integer n as a sum of two squares is equivalent to factoring n in the Gaussian integers. So we want to show that a prime integer n of form 4m+1 is no longer prime (i.e. can be factored) in the Gaussian integers.
Now look at the property of having a square root of -1. There is a square root of -1 in the Gaussian integers, namely i^2 = -1. But there is already a square root of -1 in some modular number systems Z/n too. For example, if n = 13, then 5^2 = 25 is congruent mod 13, to -1.
In fact when n is an odd prime, then -1 has a square root mod n exactly when n is congruent to 1 mod 4. This is not hard to prove, since solving equations in a modular system like Z/n is relatively easy because there are only finitely many numbers to deal with. So if n is an odd prime of form 4K + 1, then -1 has a square root mod n, and we claim that then n is not prime in Z, which will prove it can be written as a sum of two squares.
So let k be an integer such that k^2 is congruent to -1, mod n, and consider the Gaussian integers mod n, i.e. numbers of form a+bi where a and b are integers mod n. Then -1 has the two square roots k, i, so k^2 = -1 = i^2 , mod n, so 0 = k^2 - i^2 = (k-i)(k+i) = k^2+1, mod n. This means k^2+1 is divisible by n. But n does not divide either factor (k-i) or (k+i), since by definition of division in the Gaussian integers, n would have to divide both parts, k and i, and n does not divide i.
Thus in the Gaussian integers we have found a product that n divides, while n does not divide either factor. Since prime numbers have the same “prime divisibility” property in the Gaussian integers as in the usual integers, this means that although n is a prime number in Z, n is not a prime in the Gaussian integers Z, i.e. although n does not factor non trivially using only ordinary integers, it does factor using complex or “Gaussian” integers, which is what we wanted to show.
Summary: If a prime integer n has form n = 4m+1, then there is an integer k such that k^2 = -1, mod n, i.e. such that n divides k^2 - (-1) = k^2+1, in the usual integers, hence n divides k^2 + 1 also in the Gaussian integers. But in the Gaussian integers, k^2+1 = (k-i)(k+i), and n does not divide either factor, so n is not prime in the Gaussian integers, hence n = (a+bi)(c+di), so by taking absolute values of both sides and squaring, n^2 = (a^2 + b^2)(c^2+d^2), and since n is a prime integer, n = a^2+b^2. QED.
