Here is the proof. It applies not only for prime numbers, but also for every number not divisible by 2 or 3 inclusive.
To test divisibility by 2 and 3, let us first find their least common multiple. It is 6. We can now divide the integers up into subsets using their remainders when one divides by 6:
6n -- divisible by 2 and 3
6n+1
6n+2 -- divisible by 2
6n+3 -- divisible by 3
6n+4 -- divisible by 2
6n+5
So the only ones not divisible by either 2 or 3 are 6n+1 and 6n+5. The second one is equivalent to 6n-1, after bumping n up by 1. Let us now square them.
(6n+1)^2 = 36n^2 + 12n + 1 = 12n*(3n+1) + 1
(6n-1)^2 = 36n^2 - 12n + 1 = 12n*(3n-1) + 1
So we get numbers with form 12*m+1. We are almost there. So let us consider even and odd n.
n = 2k:
12n*(3n+1) + 1 = 24k*(6k+1) + 1
12n*(3n-1) + 1 = 24k*(6k-1) + 1
n = 2k+1:
12n*(3n+1) + 1 = 24*(2k+1)*(3k+2)
12n*(3n-1) + 1 = 24*(2k+1)*(3k+1)
Thus we get the form 24*m+1