Results 1 to 4 of 4

Math Help - inductive proof on a (mod n) type problem

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

    inductive proof on a (mod n) type problem

    Hi,
    Can someone please help me with this one? N = Natural number, Z= integers.

    Prove by induction that if n is a N and a,b is a Z and a congruent b(mod n), then a^m congruent b^m (mod n).

    what I did was start with a + b = nk
    then a = nk - b and use this fact in a^m -b^m = nk by rewriting it as aa^(m-1) - bb^(m-1) = 2k by subbing a into it. This did not work after multiple attempts. I am quite frustrated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by pberardi View Post
    Hi,
    Can someone please help me with this one? N = Natural number, Z= integers.

    Prove by induction that if n is a N and a,b is a Z and a congruent b(mod n), then a^m congruent b^m (mod n).

    what I did was start with a + b = nk
    then a = nk - b and use this fact in a^m -b^m = nk by rewriting it as aa^(m-1) - bb^(m-1) = 2k by subbing a into it. This did not work after multiple attempts. I am quite frustrated.
    It said use induction, so here goes.

    Base case: Clearly the claim is true for m = 1, since that is given.

    Induction hypothesis: Assume the claim is true for some k, that is a^k \equiv b^k \!\!\!\!\!\pmod{n}. We show that the claim is true for k + 1, that is, a^{k + 1} \equiv b^{k + 1} \!\!\!\!\! \pmod{n}.

    Since a \equiv b \!\!\!\!\!\pmod{n}, we have that a = b + tn, for some integer t


    Now a^k \equiv b^k \!\!\!\!\!\pmod{n}

    \Rightarrow a \cdot a^k \equiv a \cdot b^k \!\!\!\!\!\pmod{n}

    \Rightarrow a^{k + 1} \equiv (b + tn)b^k \!\!\!\!\!\pmod{n}

    \Rightarrow a^{k + 1} \equiv b^{k + 1} + tnb^k \!\!\!\!\!\pmod{n}

    since tnb^k \equiv 0 \!\!\!\!\!\pmod{n} (since it is a multiple of n) we have the desired result.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member pberardi's Avatar
    Joined
    Dec 2008
    Posts
    85
    what i dont understand is the first arrow line of your proof. Did you just multiply both sides by a?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    is up to his old tricks again! Jhevon's Avatar
    Joined
    Feb 2007
    From
    New York, USA
    Posts
    11,663
    Thanks
    3
    Quote Originally Posted by pberardi View Post
    what i dont understand is the first arrow line of your proof. Did you just multiply both sides by a?
    yes
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. help me with Inductive Proof #1
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 16th 2009, 11:16 AM
  2. Inductive proof
    Posted in the Discrete Math Forum
    Replies: 10
    Last Post: October 7th 2009, 02:09 PM
  3. Inductive Proof help!
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 25th 2009, 10:38 AM
  4. Ugh, another inductive proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 13th 2008, 03:56 PM
  5. help...inductive proof???
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: February 16th 2008, 04:11 PM

Search Tags


/mathhelpforum @mathhelpforum