Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: A Modular Arithmetic Proof Problem

  1. Sep 7, 2008 #1
    The problem statement, all variables and given/known data
    Let a, b, s, t be integers with s, t > 0. What conditions must s, t satisfy if the following statement is true:

    If a = b (mod s) and a = b (mod t), then a = b (mod st).

    The attempt at a solution
    If s | a, s | b, t | a and t | b, then st | a and st | b if and only if s, t are relatively prime. This is as far as I've gone. How should I continue?
  2. jcsd
  3. Sep 7, 2008 #2


    User Avatar
    Science Advisor
    Homework Helper

    The statement is equivalent to s | (b-a) and t | (b-a) -> st | (b-a).
  4. Sep 7, 2008 #3
    Oh, that's right! I completely forgot about that. And by using what I have, I can conclude that s and t must be relatively prime.

    Thanks again.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook