Modular arithmetic

By Olof Sisask (P3033) on Friday, May 25, 2001 - 11:42 am :

Hi,

How does the fact that there's a unique integer

x

0 \leq x \leq mn - 1

, such that

$x \equiv a_{1} (\mod m)$

and

$x \equiv a_{2} (\mod n)$ ( $m$ and $n$ coprime)

follow from the results that if $a$ , $b$ are integers, and

$a \equiv b (\mod m)$

and

$a \equiv b (\mod n)$ ,

then $a \equiv b (\mod m n)$ , and if $0 \leq a$ , $b \leq m n - 1$ , then $a = b$ ?
It's a slow morning...

Thanks,
Olof

By Kerwin Hui (Kwkh2) on Friday, May 25, 2001 - 02:41 pm :

Yes, it does follow once you have shown there is a solution.

One way to prove that there exists the integer $x$ is by Bezout's Theorem, which states that there exists $l$ , $m$ such that

$l m + m n = hcf (m, n)$

and in our case, $hcf (m, n) = 1$ . So now look at mod $m$ and mod $n$ respectively, we see that

$l m \equiv 1 (\mod n)$

$m n \equiv 1 (\mod m)$

and so one solution is $x = a_{2} l m + a_{1} m n$ .

Now we suppose that $x$ and $y$ are solutions. Then, we have $x - y \equiv 0 (\mod m)$ and $x - y \equiv 0 (\mod n)$ and so $x - y \equiv 0 (\mod m n)$ .

Kerwin

By Olof Sisask (P3033) on Friday, May 25, 2001 - 06:59 pm :

Hi Kerwin,

How do you know that x = a₂ l m+a₁ m n is a solution? I get the rest.

Thanks,
Olof

By Kerwin Hui (Kwkh2) on Friday, May 25, 2001 - 10:31 pm :

Look at

l m \equiv 1 (\mod n)

, we see that

x \equiv a_{2} \times 1 (\mod n)

, as

n \equiv 0 \mod n

. Similar for mod

m

Kerwin

By Olof Sisask (P3033) on Friday, May 25, 2001 - 11:10 pm :

Ah of course. Cheers Kerwin.

Olof

By Anonymous on Friday, June 1, 2001 - 12:31 pm :

How does

x = a_{2} l m + a_{1} m n

fulfil the condition

0 \leq x \leq m n - 1

By Kerwin Hui (Kwkh2) on Friday, June 1, 2001 - 11:36 pm :

I think there is some confusion here due to lazy-typing. What I have not typed is "a₂ l m+a₁ m n is a solution in Z , and we can always reduce this to a member of the set of residues {0,1,...,mn-1}".

Kerwin