Please delete. Posted in wrong forum. Sorry :P
Any integer can be written in the form , where or . It follows that .
Now, simplifying, .
Consider three cases:
1. : and since is divisible by 3, is divisible by 9.
2. : , where and . Then is divisible by 9.
3. : , and since it follows that is divisible by 9.
For cases 1. and 2. I noticed that 1 and 2 are the roots, respectively, of the polynomials and then used Polynomial Division.