Results 1 to 6 of 6

Math Help - Congruences Proof

  1. #1
    Super Member
    Joined
    Feb 2008
    Posts
    535

    Congruences Proof

    Prove, by induction: If a and b are congruent mod m, then a^n and b^n are congruent mod m.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    o_O
    o_O is offline
    Primero Espada
    o_O's Avatar
    Joined
    Mar 2008
    From
    Canada
    Posts
    1,407
    Recall: a \equiv b \ (\text{mod } m) \ \Leftrightarrow \ a = b + km for some k \in \mathbb{Z}

    For the inductive step, we assume that it is true for some k, i.e a^k \equiv b^k \ (\text{mod } m) and we want to prove that it is also true for k+1.

    Multiply both sides by a and substitute a = b + km for some integer k (just go by the definition of congruences!)
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Super Member
    Joined
    Feb 2008
    Posts
    535
    Okay, so I understand that I must show that a^(k+1) and b^(k+1) are congruent mod m.

    And I understand that a and b are congruent mod m iff a = b + km, k e Z.

    But, Im not sure why I would multiply both sides by a?? And where do I plug in my Inductive Hyp? Is the base case 0?
    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 jzellt View Post
    Okay, so I understand that I must show that a^(k+1) and b^(k+1) are congruent mod m.

    And I understand that a and b are congruent mod m iff a = b + km, k e Z.

    But, Im not sure why I would multiply both sides by a?? And where do I plug in my Inductive Hyp? Is the base case 0?
    the base case is n = 1, which is given. we are told a \equiv b ~(\bmod ~m)

    picking up where o_O left off. we have

    a^k \equiv b^k ~(\bmod ~m)

    \Rightarrow a^{k + 1} \equiv ab^k ~(\bmod ~m) ....by multiplying both sides by a

    now change the a on the right how o_O said to change it. see what you get
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Super Member
    Joined
    Feb 2008
    Posts
    535
    So, on the right side we have (b + mk)b^k = b^(k+1) + b^k(mk)

    Now what do I do with b^k(mk)??
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor

    Joined
    Apr 2005
    Posts
    15,525
    Thanks
    1384
    edit: Sorry, I just noticed you are required to use induction. Too bad!
    I don't think it is necessary to use induction.

    If a and b are congruent modulo n, then a-b is a multiple of n.

    For any positive integer n, a^n- b^n= (a- b)(a^{n-1}+ a^{n-2}b+ a^{n-3}b^2+ \cdot\cdot\cdot+ a^2b^{n-3}+ ab^{n-2}+ b^{n-1}.

    Do you see how that shows that a^n- b^n is a multiple of n?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Congruences
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: March 11th 2010, 12:52 PM
  2. congruences
    Posted in the Number Theory Forum
    Replies: 1
    Last Post: September 5th 2009, 10:59 AM
  3. Congruences
    Posted in the Number Theory Forum
    Replies: 3
    Last Post: May 7th 2009, 02:26 PM
  4. Number Theory Congruences Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 17th 2008, 09:31 AM
  5. Congruences
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 6th 2008, 06:18 PM

Search Tags


/mathhelpforum @mathhelpforum