Results 1 to 4 of 4

Math Help - Show that if m and n are relatively prime and a and b are any integer,

  1. #1
    Newbie
    Joined
    Feb 2013
    From
    New York
    Posts
    10

    Show that if m and n are relatively prime and a and b are any integer,

    Show that if m and n are relatively prime and a and b are any integer,
    then there is an integer x that simultaneously satisfies
    the two congruence x ≡ a (mod m) and x ≡ b (mod m)
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,517
    Thanks
    771

    Re: Show that if m and n are relatively prime and a and b are any integer,

    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Feb 2013
    From
    New York
    Posts
    10

    Re: Show that if m and n are relatively prime and a and b are any integer,

    thank you so much. my prof and the textbook didnt cover this topic
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Super Member
    Joined
    Dec 2012
    From
    Athens, OH, USA
    Posts
    616
    Thanks
    249

    Re: Show that if m and n are relatively prime and a and b are any integer,

    Here's a very simple constructive proof:
    Form the sequence a+mi, 0<=i<n. If two of these were the same mod n, a+mi=a+mj mod n, m(i-j)=0 mod n. Since n and m are relatively prime, n divides i-j and i=j. So the sequence forms a complete set of remainders mod n; b mod n must be one of these. Actually, there's more: the x is unique mod mn, but I won't bother with a proof.

    Since the above proof is constructive, for "small" m and n, you can rapidly find the x. Example: suppose you know the last two digits of a positive integer are 7 mod 25 and 1 mod 4. Then the sequence is 7+25=32, 7+2*25=57 which is 1 mod 4. So the last two digits are 57
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 1
    Last Post: June 1st 2012, 10:08 PM
  2. Replies: 5
    Last Post: September 8th 2010, 02:16 AM
  3. Replies: 0
    Last Post: October 6th 2009, 03:52 PM
  4. Positive Integer is Prime Like
    Posted in the Number Theory Forum
    Replies: 14
    Last Post: May 4th 2009, 07:57 AM
  5. Proving an integer is prime
    Posted in the Number Theory Forum
    Replies: 2
    Last Post: September 12th 2005, 03:25 PM

Search Tags


/mathhelpforum @mathhelpforum