For N to be not divisible by 3, N can either be of the form 3k + 1 (1,4...) or 3k + 2 (2,5...), where k is an integer.

The proof can then be done by checking both 3k + 1 and 3k + 2 when N is squared, to see if they can be rearranged into the form 3a + 1.

N = 3k + 1, so N^{2} = (3k + 1)^{2} = 9k^{2} + 6k + 1

This can then be rearranged to prove 3a + 1. Note that a can be made of any polynomial of k with integer powers, as k is an integer so its polynomial with integer powers will also be an integer for any value of k.

9k^{2} + 6k + 1 = 3(3k^{2} +2k) + 1, so true for N = 3k + 1

The same method can then be used to prove for N = 3k + 2

N= 3k + 2, N^{2} = 9k^{2} + 12k + 4 = 3(3k^{2} + 4k + 1) + 1