Chinese Remainder Theorem

  • Thread starter Bleys
  • Start date
  • #1
Bleys
74
0
This doesn't actually require the use of the CRT, since it actually wants you to sort of derive it for a system of two equations. So while using the CRT will help me solve this fairly quickly and easily, that's not what I'm after

Homework Statement


Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that
[tex]c\equiva(mod m)[/tex] and [tex]c\equivb(mod n)[/tex]

2. The attempt at a solution

now, sm + tn = 1 for some integers s,t. It's obvious that
[tex]sm\equiv0(mod m)[/tex] and [tex]tn\equiv0(mod n)[/tex]

I know I'm suppose to use sm and tn as coefficients to combine a and b, but I'm not really sure how to go about it. I've tried adding tn to get 1 == tn (mod m) but I'm not sure that's correct. And even if it is, I multiply by a or by b and can still not figure it out. I end up in circles and get c == a (mod m). -_- Can you lend me hand? Remember, don't give me the chinese remainder theorem, because that's not what the excercise is about.
 

Answers and Replies

  • #2
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
It's essentially a linear algebra problem -- your "vectors" are the two-tuples whose components are "value mod m" and "value mod n", and you seek to express a particular vector as an integer linear combination of the two vectors you have already considered.


I've tried adding tn to get 1 == tn (mod m) but I'm not sure that's correct.
Well, have you thought about how you might prove it? If not, can you explain why you think it might be true?
 
  • #3
gabbagabbahey
Homework Helper
Gold Member
5,002
7
Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that
[tex]c\equiva(mod m)[/tex] and [tex]c\equivb(mod n)[/tex]

Do you mean that you are trying to show that you can always find integer [itex]c[/itex] such that:

[tex]c \equiv a \quad (\text{mod} \; m)[/tex] and [tex]c \equiv b \quad (\text{mod} \; n)[/tex]

?
 
  • #4
HallsofIvy
Science Advisor
Homework Helper
43,021
970
"Let gcd(m,n)=1. Given integers a,b, show that it is possible to find an integer c such that [itex]c (mod m)[/itex] and [itex]c (mod n)[/itex]" makes no sense. What is supposed to be true of [itex] c (mod m)[/itex] and [itex]c (mod m)[/itex]? That they are equal?
 
  • #5
Bleys
74
0
yes, gabbagabbahey, sorry that's what I meant:
[tex]c \equiv a \quad (\text{mod} \; m)[/tex]
[tex]c \equiv b \quad (\text{mod} \; n)[/tex]

So since [tex]sm \equiv 0 (\text{mod} \; m)[/tex] then, I thought
[tex]tn + sm \equiv tn (\text{mod} \; m)[/tex]
[tex]1 \equiv tn (\text{mod} \; m)[/tex]
 
  • #6
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
So since [tex]sm \equiv 0 (\text{mod} \; m)[/tex] then, I thought
[tex]tn + sm \equiv tn (\text{mod} \; m)[/tex]
[tex]1 \equiv tn (\text{mod} \; m)[/tex]
Yes, this is definitely correct.
 
  • #7
Bleys
74
0
hmm, looking at it though, I don't think it would get me anywhere would it? Rather, the congruence also implies

[tex]tn \equiv 1 (\text{mod} \; m)[/tex] therefore
[tex]atn \equiv a (\text{mod} \; m)[/tex]
and in the same way you can get

[tex]bsm \equiv b (\text{mod} \; n)[/tex]

then, can you say bsm + atn is congruent to both a (mod m) and b (mod n); hence that's the c I'm looking for?
 
  • #8
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
then, can you say bsm + atn is congruent to both a (mod m) and b (mod n); hence that's the c I'm looking for?
You seem hesitant to assert that -- what might be a problem? If you can indeed prove both of those congruences, it sounds like you've constructively shown the existence of such a c.
 
  • #9
Bleys
74
0
I guess I'm convinced; after all if you have
bsm + atn == a (mod m)
0 + atn == a (mod m)
and we've seen tn == 1 (mod m), so
a == a (mod m); similarly for bsm == b (mod n)

If I can ask another question;
What if gcd(m,n)=k for some k>1
Going through similar steps I obtain
[tex]atn \equiv ak (\text{mod} \; m)[/tex]

I thought, you would need to obtain the inverse of k modulo m (assuming m is prime, and therefore the inverse exists). Let f be the inverse of k (mod m). Then
[tex]fatn \equiv fak (\text{mod} \; m)[/tex]
[tex]fatn \equiv a (\text{mod} \; m)[/tex]

Similarly for bsm, you would obtain
[tex]bsm \equiv bk (\text{mod} \; n)[/tex]
[tex]gbsm \equiv gbk (\text{mod} \; n)[/tex] where g is the inverse of k (mod n)
[tex]gbsm \equiv b (\text{mod} \; n)[/tex]

Therefore our c = fatn + gbsm. Correct?
If either m or n, possibly both, are not prime, then you would you still have a solution for this only if the inverse of k exists for both (mod m) and (mod n). If it doesn't, then is the system not solvable?
 
  • #10
Hurkyl
Staff Emeritus
Science Advisor
Gold Member
14,967
19
I believe you know exactly when k, as defined, is invertible modulo m...

I believe it might be better to first work through the case where you have many different relatively prime moduli. Once you understand that, you can then reduce to it the case where you have two moduli that are not relatively prime.

Alternatively, you might first try to work out exactly when a single linear modular equation does and does not have a solution (and if it does, how many).
 

Suggested for: Chinese Remainder Theorem

Replies
2
Views
777
Replies
1
Views
869
  • Last Post
Replies
12
Views
696
Replies
27
Views
1K
Replies
4
Views
72
  • Last Post
Replies
7
Views
185
Replies
1
Views
179
  • Last Post
Replies
5
Views
335
Replies
6
Views
314
Top