Added: Thanks to Noam Elkies for pointing out that I mixed up Legendre and Jacobi (j'adresse `a leurs patries respectives mes plus plates excuses): My answer yields only a proof of Legendre's theorem.
A bit of a cheat: Check that it holds for all integers up to 15 and use Conway's fifteen Theorem (https://en.wikipedia.org/wiki/15_and_290_theorems).