Results 1 to 8 of 8

Math Help - Test Tommorow, Urgent Discrete Math advice needed.

  1. #1
    Member
    Joined
    Jan 2008
    Posts
    175

    Test Tommorow, Urgent Discrete Math advice needed.

    Having my first exam tomorrow, and while Im prepared, im finding that problems with modulus arithmetic are giving problems.

    For example, prove that if ac =(congruent) bc (mod m), then a =(congruent) b (mod m/d), where d = gcd(m,c).

    I was wondering if anyone could give me any tips for these types of problems?

    This was a review question, and i WILL have a question like this on my exam tomorrow.

    thanks!

    btw i have the answer for the question, but just provided it as an example. I understand the theory and what it means, just being able to prove it one way or another is proving to be difficult.
    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 p00ndawg View Post
    Having my first exam tomorrow, and while Im prepared, im finding that problems with modulus arithmetic are giving problems.

    For example, prove that if ac =(congruent) bc (mod m), then a =(congruent) b (mod m/d), where d = gcd(m,c).

    I was wondering if anyone could give me any tips for these types of problems?

    This was a review question, and i WILL have a question like this on my exam tomorrow.

    thanks!

    btw i have the answer for the question, but just provided it as an example. I understand the theory and what it means, just being able to prove it one way or another is proving to be difficult.
    the best way to tackle these is to learn how to write them without congruences. that is, if you are unfamiliar with manipulating congruences themselves. when you have a set of equations working with, it is usually easier to "see" what you need to do. write out what the statements mean and then write out what you want to show.

    the problem asked you to prove ac \equiv bc~(\mbox{mod }m) \implies a \equiv b~(\mbox{mod }m/d), where d = \mbox{gcd}(m,c)

    so ac \equiv bc~(\mbox{mod }m) means c(a - b) = km for k \in \mathbb{Z} (i suppose you know how to get to this equation)

    you are required to use the equation above to show that a \equiv b~(\mbox{mod }m/d) that is, you want to show a - b = \frac {\alpha m}d for some \alpha \in \mathbb{Z}

    since d = \mbox{gcd}(m,c), we can get the desired result by dividing the first equation through by d and simplifying
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Jan 2008
    Posts
    175
    Quote Originally Posted by Jhevon View Post
    the best way to tackle these is to learn how to write them without congruences. that is, if you are unfamiliar with manipulating congruences themselves. when you have a set of equations working with, it is usually easier to "see" what you need to do. write out what the statements mean and then write out what you want to show.

    the problem asked you to prove ac \equiv bc~(\mbox{mod }m) \implies a \equiv b~(\mbox{mod }m/d), where d = \mbox{gcd}(m,c)

    so ac \equiv bc~(\mbox{mod }m) means c(a - b) = km for k \in \mathbb{Z} (i suppose you know how to get to this equation)

    you are required to use the equation above to show that a \equiv b~(\mbox{mod }m/d) that is, you want to show a - b = \frac {\alpha m}d for some \alpha \in \mathbb{Z}

    since d = \mbox{gcd}(m,c), we can get the desired result by dividing the first equation through by d and simplifying

    Thanks, so it general a question similar to this, the first part needs to be used to prove the second?
    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 p00ndawg View Post
    Thanks, so it general a question similar to this, the first part needs to be used to prove the second?
    yes. whenever you see IF ... THEN ---. you have what we call an implication

    it means you have to use ... to prove ---

    or by the contrapositive, you can assume NOT --- and use it to prove NOT...
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Member
    Joined
    Jan 2008
    Posts
    175
    Quote Originally Posted by Jhevon View Post
    yes. whenever you see IF ... THEN ---. you have what we call an implication

    it means you have to use ... to prove ---

    or by the contrapositive, you can assume NOT --- and use it to prove NOT...
    thanks this helps a bit.

    I still sometimes just get stuck on the very last part, I guess you could call it the "inductive" part of the problem.

    Follow Math Help Forum on Facebook and Google+

  6. #6
    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 p00ndawg View Post
    thanks this helps a bit.

    I still sometimes just get stuck on the very last part, I guess you could call it the "inductive" part of the problem.

    it may help for you to be a little more specific. are you having trouble with the last part of this problem? maybe there's another problem that was giving you trouble. you may want to post it and state your difficulties...
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Member
    Joined
    Jan 2008
    Posts
    175
    Quote Originally Posted by Jhevon View Post
    it may help for you to be a little more specific. are you having trouble with the last part of this problem? maybe there's another problem that was giving you trouble. you may want to post it and state your difficulties...

    prove that n^4 is congruent to(mod5).

    5 does not divide n.


    also a problem like this, show that if a, b, and c are intergers where c does not equal 0, such that ac divides bc, then a divides b.

    I guess I have problems understanding why. I understand how to set them up, but having trouble putting it together.
    Follow Math Help Forum on Facebook and Google+

  8. #8
    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 p00ndawg View Post
    prove that n^4 is congruent to(mod5).

    5 does not divide n.
    congruent to what?


    also a problem like this, show that if a, b, and c are intergers where c does not equal 0, such that ac divides bc, then a divides b.

    I guess I have problems understanding why. I understand how to set them up, but having trouble putting it together.
    remember this.

    all these statements are equivalent:

    a \equiv b~(\mbox{mod }n)

    n~|~a - b which is the same as saying n~|~b - a

    a - b = kn for some k \in \mathbb{Z}


    with that being said. we have an IF, THEN statement here. i already told you how to deal with that. here we opt for the "direct proof." that is, we will use the first statement to prove the second.

    recall from above, ac~|~bc means bc = k(ac) for k \in \mathbb{Z}

    we want to use this to show a~|~b, that is, b = \alpha a for \alpha \in \mathbb{Z}.

    since c \ne 0, we can divide by it. dividing the first equation by c we get the desired result
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 0
    Last Post: June 9th 2011, 11:45 AM
  2. Discrete Math. Urgent help please.
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 29th 2009, 10:30 PM
  3. ratio test (series) urgent test tommorow!
    Posted in the Calculus Forum
    Replies: 3
    Last Post: December 2nd 2008, 03:27 PM
  4. Extra Credit Discrete Math HW Help Needed
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: September 20th 2007, 03:51 AM
  5. Math help, test tommorow.
    Posted in the Algebra Forum
    Replies: 3
    Last Post: October 19th 2006, 08:27 PM

Search Tags


/mathhelpforum @mathhelpforum