• Support PF! Buy your school textbooks, materials and every day products Here!

Chinese Remainder Theorem

  • Thread starter Bleys
  • Start date
  • #1
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,916
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
6
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
41,833
956
"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
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,916
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
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,916
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
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,916
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).
 

Related Threads on Chinese Remainder Theorem

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
1
Views
3K
  • Last Post
Replies
1
Views
2K
  • Last Post
Replies
0
Views
980
Replies
2
Views
502
Replies
0
Views
2K
Replies
1
Views
2K
Replies
0
Views
3K
Replies
1
Views
542
Replies
1
Views
1K
Top