Quadratic Reciprocity. Gauss' original proof is entirely elementary, but far from easy (I think I recall reading that Gauss himself said he spent more than a year tormented trying to find a proof).
There are many modern proofs. Using algebraic number theory and in particular the Kronecker-Weber theorem, we now have a conceptual proof, literally 4-5 lines in length.
