Hey, thanks for giving this puzzle some attention.
Let me rephrase the problem so that it is less ambiguous. There will still be multiple solutions.
How can you determine the last three digits of (3 + √5)n before the decimal using only integer operations?
Incidentally, this explanation provides a much simpler way to arrive at the solution to your aha problem, bonanova.
Edit - I just realized that there was an equally elegant words-only solution further along the aha thread. And it has a slightly different angle than the explanation we have above. Man, this is what I love about math.