Finding x through mod regarding G.C.D

[joao_pimentel]

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

$$x=q_1 n+3$$

$$x=q_2 m +2$$

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

Thank you

 

[dodo]

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:
http://www.math.okstate.edu/~wrightd/crypt/lecnotes/node21.html

It may point you to study other things first, like the "Euclidean algorithm".
Hope this helps!

 

[joao_pimentel]

I tried to develop the system considering $$q_1$$ and $$q_2$$ are naturals...

$$\begin{cases}<br /> x=q_1 n+3 \\<br /> x=q_2 m+2 \\<br /> \end{cases}$$

I developed then and I saw that:

$$\frac{m}{n}=\frac{q_1}{q_2}\frac{x-2}{x-3} \ \ q_1,q_2 \in \mathbb{N}$$

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

can you kindly help out to continue?

 

[dodo]

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.

--------------
P.S.:
In your particular example, given that you have integers $q_1$, $q_2$ such that
$$\begin{cases} <br /> x=q_1 n+3 \\ <br /> x=q_2 m+2 \\ <br /> \end{cases}$$
then, as the two right-hand sides are both equal to x, they are equal among themselves, and
$$q_1 n + 3 = q_2 m + 2$$
It follows that
$$q_1 n + 1 = q_2 m$$
which can be written as
$$q_2 m - q_1 n = 1$$
so the integers a,b I was talking about before, are $a=q_2$ and $b=-q_1$.

Thus your solution is x = 3ma + 2nb = $3 m q_2 - 2 n q_1$. (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.)

 

[joao_pimentel]

Thank you very much for your kind attention

Best regards