There is a somewhat trivial proof, if you know modular arithmetic. Namely, everything relies on the following fact:
If and then .
With this in mind, .
I was reading a book on graph theory and came across an exercise I found quite interesting. It essentially proved "(4^n)mod3 = 1, if (n) is a natural number," but did so in a round-about geometric fashion. Does this theorem have a name that I can look into farther? "Fermat's 143rd theorem" or something?
----------------
If you're curious, the explanation in the book was as such (It might be hard to interpret without pictures.):
Suppose you have a "chessboard" composed of (2^n) rows of (2^n) squares, where (n) is any natural number. The chessboard is also defective, in that one square is arbitrarily cut out.
[My interpretation: the number of squares on the board is ((2^n)^2)-1 = (2^2n)-1 = (4^n)-1 ]
Prove that you can cover any such (4^n)-1 chessboard by tiling it with trominoes (3-squared dominoes shaped like a right angle).
[My interpretation: the number of squares on the board is evenly divisible by 3.]
[ ((4^n)-1)mod3 = 0, or more cleanly, (4^n)mod3 = 1 ]
The smallest such chessboard [(4^1)-1] would only have 3 squares and could be tiled easily with one tromino.
The next largest board [(4^2)-1 in this case] can easily be tiled if it is treated as, itself, a tiling of four copies of the last board (but not copying the single missing square). A 4x4 board would thus become four 2x2 boards, one of which has a missing square and is covered by one tromino perfectly, the other three would have a tromino placed at their intersection, covering one square each, and would thus be essentially the same as the first 2x2 board, having only 3 uncovered squares left.
Inductively, it should hold for all (n) that are natural numbers.
------
The geometric proof is pretty convincing if you draw it out. I did the arithmetic in my head up to (n=6) and it seems believable, but I imagine there's more to the story.