# Math Help - Algebraic proof of [ (4^n)mod3 = 1 ] ??

1. ## Algebraic proof of [ (4^n)mod3 = 1 ] ??

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.

2. ## Re: Algebraic proof of [ (4^n)mod3 = 1 ] ??

There is a somewhat trivial proof, if you know modular arithmetic. Namely, everything relies on the following fact:

If $a\equiv b\text{ mod }n$ and $c\equiv d\text{ mod }n$ then $ac\equiv bd\text{ mod }n$.

With this in mind, $4^n=4\cdots 4\equiv (1)\cdots(1)\equiv 1^n=1\text{ mod }n$.

3. ## Re: Algebraic proof of [ (4^n)mod3 = 1 ] ??

I would use "induction". Clearly 4= 3+ 1 so $4^1= 1$ (mod 3). Now suppose that, for some k, $4^k= 1$ (mod 3). That is, $4^k= 3n+ 1$ for some integer n. Then $4^{k+1}= 4(4^k)= 4(3n+1)= 3(4n)+ 4= 3(4n+1)+ 1$.