Results 1 to 3 of 3

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

  1. #1
    Newbie
    Joined
    Aug 2013
    From
    Florida
    Posts
    2

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21

    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,546
    Thanks
    1395

    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.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Algebraic proof
    Posted in the Algebra Forum
    Replies: 4
    Last Post: February 22nd 2013, 06:09 PM
  2. Replies: 0
    Last Post: August 3rd 2012, 11:50 PM
  3. Algebraic Proof
    Posted in the Algebra Forum
    Replies: 4
    Last Post: March 15th 2010, 02:55 PM
  4. Algebraic proof
    Posted in the Algebra Forum
    Replies: 1
    Last Post: December 15th 2009, 10:33 AM
  5. Help with an algebraic proof
    Posted in the Algebra Forum
    Replies: 5
    Last Post: March 29th 2008, 02:35 PM

Search Tags


/mathhelpforum @mathhelpforum