Results 1 to 4 of 4

Math Help - mod proof by induction uses transitivity

  1. #1
    Member pberardi's Avatar
    Joined
    Dec 2008
    Posts
    85

    mod proof by induction uses transitivity

    I need to see why this proof works. I have most of it I think but can someone clear me up here?

    Prove that for each natural number n, 8^n = 1 mod 7

    By induction show 1 is true
    8 = 1 (mod 7) or 8 - 1 = 7k trivial

    assume n is true there for 8^n = 1 (mod 7)
    Show 8^(n+1) = 1 mod 7

    multiply by 8
    8*8^(n) = 8 (mod 7)
    8^(n+1) = 8 (mod 7)

    Now this is where I get confused. My TA said that now 8^(n+1) = 1 mod 7 because of a transitivity property. Could someone help me see this please? Is there another way of doing this that perhaps I can see it better? Thank you.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Senior Member TheAbstractionist's Avatar
    Joined
    Apr 2009
    Posts
    328
    Thanks
    1
    Quote Originally Posted by pberardi View Post
    I need to see why this proof works. I have most of it I think but can someone clear me up here?

    Prove that for each natural number n, 8^n = 1 mod 7

    By induction show 1 is true
    8 = 1 (mod 7) or 8 - 1 = 7k trivial

    assume n is true there for 8^n = 1 (mod 7)
    Show 8^(n+1) = 1 mod 7

    multiply by 8
    8*8^(n) = 8 (mod 7)
    8^(n+1) = 8 (mod 7)

    Now this is where I get confused. My TA said that now 8^(n+1) = 1 mod 7 because of a transitivity property. Could someone help me see this please? Is there another way of doing this that perhaps I can see it better? Thank you.
    Hi pberardi.

    Modulo congruence is indeed a transitive relation. Suppose a\equiv b\pmod n and b\equiv c\pmod n. Then a=b+rn and b=c+sn for some integers r,s. Hence a=c+sn+rn=c+(r+s)n\equiv c\pmod n.

    In your problem, 8^{n+1}\equiv8\pmod7 and 8\equiv1\pmod7 imply 8^{n+1}\equiv1\pmod7.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member pberardi's Avatar
    Joined
    Dec 2008
    Posts
    85
    Ok thanks now that you put it that way I see it.
    I think my trouble was that I was looking at it this way:

    8^n = 1 mod 7 and
    8^(n+1) = 8 mod 7 so
    8^n = 8 mod 7
    this does not help one bit.

    But if I just switch them to
    8^(n+1) = 8 mod 7
    8^n = 1 mod 7
    8^(n+1) = 1 mod 7

    then your formula works fine. Thank you for showing me that.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member

    Joined
    May 2006
    From
    Lexington, MA (USA)
    Posts
    11,662
    Thanks
    603
    Hello, pberardi!

    Prove that, for each natural number n\!:\;\;8^n \equiv 1\text{ (mod 7)}


    Show S(1) is true: . 8 \equiv 1 \text{ (mod 7)} or 8 - 1 \:=\: 7k ... trivial

    Assume S(k) is true: . 8^k \equiv 1\text{ (mod 7)}

    Show that: . 8^{k+1} \equiv 1\text{ (mod 7)}

    Multiply by 8: . 8\cdot8^n \:\equiv \:8\text{ (mod 7)}

    Since 8 \equiv 1\text{ (mod 7)}, we have: . 8^{k+1} \equiv 1 \text{ (mod 7)}

    Your demonstration is absolutely correct!

    As The Abstrationist explained, you used the Transitive Property
    . . though you probably didn't realize it.


    Perhaps your course insists on a justification for every step?

    If so, we cannot write: . x \:=\:3^2 \:=\:9


    We must write something like:

    . . \begin{array}{ccc}\text{Statement} & & \text{Reason} \\ \hline<br />
x \:=\:3^2 & & \text{previous steps} \\<br />
3^2 \:=\:9 & & \text{arithmetic fact} \\<br />
\therefore\;x = 9\quad & & \text{transitive property} \end{array}

    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Set Theory Transitivity Proof
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: October 22nd 2011, 03:23 PM
  2. permutation/transitivity
    Posted in the Advanced Algebra Forum
    Replies: 1
    Last Post: November 13th 2009, 08:55 PM
  3. Transitivity
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 12th 2009, 08:13 PM
  4. Mathemtical Induction Proof (Stuck on induction)
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 8th 2009, 09:33 PM
  5. Proof with algebra, and proof by induction (problems)
    Posted in the Discrete Math Forum
    Replies: 8
    Last Post: June 8th 2008, 01:20 PM

Search Tags


/mathhelpforum @mathhelpforum