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 £ x £ mn-1, such that

x º a₁ (mod m)

and

x º a₂ (mod n) (m and n coprime)

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

a º b (mod m)

and

a º b (mod n),

then a º b (mod m n), and if 0 £ a, b £ 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 º 1 (mod n)

m n º 1 (mod m)

and so one solution is x=a₂ l m + a₁ m n.

Now we suppose that x and y are solutions. Then, we have x-y º 0 (mod m) and x-y º 0 (mod n) and so x-y º 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 º 1 (mod n), we see that x º a₂×1 (mod n), as n º 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₂ l m + a₁ m n fulfil the condition 0 £ x £ 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