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

Finding x through mod regarding G.C.D

  1. Jan 26, 2012 #1
    Hi, my problem is this one:

    G.C.D of (m,n)=1

    x ≡3 (mod n)
    x ≡2 (mod m)

    Find x.


    Just kindly tell me which subjects shall I study, and kindly give me some quick web references...
    web articles, web pages, etc...

    I'm around this problem and I can't find anything.

    I know that

    [tex]x=q_1 n+3[/tex]

    [tex]x=q_2 m +2[/tex]

    and i know the fraction [tex]\frac{m}{n}[/tex] is irredutible, but which next steps shall I give?

    Thank you
  2. jcsd
  3. Jan 26, 2012 #2
    Hi, Joao,
    you need to google for the "chinese remainder theorem". The Wikipedia page can be a bit obscure depending on your background; this page may be more clear:

    It may point you to study other things first, like the "Euclidean algorithm".
    Hope this helps!
  4. Jan 26, 2012 #3
    I tried to develop the system considering [tex]q_1[/tex] and [tex]q_2[/tex] are naturals...

    x=q_1 n+3 \\
    x=q_2 m+2 \\

    I developed then and I saw that:

    [tex]\frac{m}{n}=\frac{q_1}{q_2}\frac{x-2}{x-3} \ \ q_1,q_2 \in \mathbb{N}[/tex]

    I know that G.C.D(m.n)=1, then these are Irreducible fractions

    can you kindly help out to continue?
  5. Jan 26, 2012 #4
    Here is a simpler version of the story, hopefully.

    When working with coprime numbers like your m,n, numbers such that GCD(m,n)=1, a common strategy is to rely on something called "Bézout's identity": it says that it is always possible to find other integers a,b, such that ma+nb=1. Assume the existence of these other integers a,b for the moment; we can go into more detail later as to why they exist, or you can google that for yourself.

    Notice, then, that the equation ma+nb=1, which we can write as either ma - 1 = n(-b), or as nb - 1 = m(-a), implies respectively that:
    ma ≡ 1 (mod n), and
    nb ≡ 1 (mod m)

    Now you're almost done, as the x you are looking for is x = 3ma + 2nb. It's not hard to see that this x, modulo n, is 3 . 1 + 0 = 3, and modulo m it is 0 + 2 . 1 = 2, which is what you wanted.

    The issue, then, is that you convince yourself about the truth of Bézout's identity, which is a very common trick in dealing with numbers whose GCD is 1.

    In your particular example, given that you have integers [itex]q_1[/itex], [itex]q_2[/itex] such that
    x=q_1 n+3 \\
    x=q_2 m+2 \\
    then, as the two right-hand sides are both equal to x, they are equal among themselves, and
    [tex]q_1 n + 3 = q_2 m + 2[/tex]
    It follows that
    [tex]q_1 n + 1 = q_2 m[/tex]
    which can be written as
    [tex]q_2 m - q_1 n = 1[/tex]
    so the integers a,b I was talking about before, are [itex]a=q_2[/itex] and [itex]b=-q_1[/itex].

    Thus your solution is x = 3ma + 2nb = [itex]3 m q_2 - 2 n q_1[/itex]. (Actually, there are many other solutions, as adding or subtracting any multiple of mn will produce another solution; there will be only one solution in the interval between 0 and mn-1, both inclusive.)
    Last edited: Jan 26, 2012
  6. Jan 26, 2012 #5
    Thank you very much for your kind attention

    Best regards
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook