Question

May I learn the Chinese Remainder Theorem?
I want to solve the congruences.

Answer 1

The Chinese remainder theorem is a result about congruences in number theory and its generalizations in abstract algebra. In its basic form, the Chinese remainder theorem will determine a number n that when divided by some given divisors leaves given remainders.
For example, what is the lowest number n that when divided by 3 leaves a remainder of 2, when divided by 5 leaves a remainder of 3, and when divided by 7 leaves a remainder of 2? A common introductory example is a woman who tells a policeman that she lost her basket of eggs, and that if she took three at a time out of it, she was left with 2, if she took five at a time out of it she was left with 3, and if she took seven at a time out of it she was left with 2. She then asks the policeman what is the minimum number of eggs she must have had. The answer to both problems is 23.
see here

http://en.wikipedia.org/wiki/Chinese_remainder_theorem

Answer 2

Please help.

Answer 3

@UnkleRhaukus Sorry for tagging.

Answer 4

http://www.math.okstate.edu/~wrightd/crypt/lecnotes/node21.html

Answer 5

@ParthKohli does this help u???

Answer 6

No.

Answer 7

CRT! It's amazing how much you can do with this. Here's my shortest explanation of how to use (no why it works yet, that's more complicated).

Suppose you're given the following two equations.\[x\equiv a\pmod{c}\]\[x\equiv b\pmod{d}\]and \(\gcd(c,d)=1\). First thing to do, is solve the equation \[ec+fd=1\]Now there's just one more thing to do. \[x\equiv bec+afd\pmod{c\cdot d}\]

Answer 8

\(\text{gcf(c,d)}=1\) just means that the numbers are co-prime, right?

Answer 9

Correct.

Answer 10

For example, suppose you want to solve \[x\equiv6\pmod{13}\]\[x\equiv12\pmod{23}\]Then, we first need to solve \(13a+23b=1\). Using the Euclidean algorithm,\[23=13\cdot1+10\]\[13=10\cdot1+3\]\[10=3\cdot3+1\]Using backsubstitution (or magic box) we get \(a=16\) and \(b=-9\). So we have \(13\cdot16-23\cdot9=1\)

Answer 11

That means our solution will be \[x\equiv12\cdot 13\cdot16-6\cdot23\cdot9\pmod{13\cdot23}\]Simplify this a bit, and we get \[x\equiv58\pmod{299}\]

Answer 12

Hm. Can we please go slow?

Answer 13

If you have the time, please do :)

Answer 14

I don't understand what \(e,f\) are in \(ec + fd = 1\).

Answer 15

Look back at the original equations we had \[x\equiv a\pmod{\color{red}{c}}\]\[x\equiv b\pmod{\color{green}d}\]We need to solve \(e\color{red}{c}+f\color{green}{d}=1\). Here, \(e,f\) are merely two integers that give a solution to this equation. Remember that \(\color{red}c\) and \(\color{green}d\) are fixed by the problem.

Answer 16

I see. What is the Euclidean Algorithm?

Answer 17

Wait. I'd make another question, then we'd return back to this :)

Answer 18

It's a method to find the \(\gcd\) of two numbers. As an added bonus, with a little backsubstitution, it also solves that integral equation I gave above.

Answer 19

Feel free to make another question if you want.

Answer 20

Okay - one on the Euclidean Algorithm.

Answer 21

I'm thinking about it.

Answer 22

I don't get why we are using the Euclidean Algorithm here. :/

Answer 23

It's an efficient way to solve the equation \(e\color{red}{c}+f\color{green}{d}=1\). It's not the only method, but it's very efficient, and you can do it by hand.

Answer 24

How does the \(\gcd\) help?

Answer 25

Basically, it boils down to the fact:

\(e\color{red}{c}+f\color{green}{d}=1\) has a solution if and only if \(\gcd(c,d)=1\).

That's the only reason we need the gcd to be 1.

Answer 26

Oh yes! I see what you meant there.

Answer 27

And how did you get \(a = 16\) and \(b = -9\)?

Answer 28

Sorry for interrupting but I have two doubts. Why do we need to solve \(ec+fd=1\)? How do I know \(x \equiv bec + afd \pmod{c\cdot d}\) is true?

Answer 29

Look back up to \[23=13⋅1+10\]\[13=10⋅1+3\]\[10=3⋅3+1\]Now, I just do a bunch of substitutions.\[1=10-3\cdot3\]\[3=13-10\cdot1\]\[10=23-13\cdot1\]So we have\[1=(23-13)-3(13-10)\]\[1=23-4(13)+3(10)\]\[1=23-4(13)+3(23-13)\]\[1=4(23)-7(13)\]So doing it this way, you really should have gotten \(a=-7\) and \(b=4\). However, it doesn't really matter since you will get the same solution for \(x\).

For the solution I got before, I cheated and used wolfram to make it quicker.

Answer 30

Okay. Wolfram FTW! :P

Answer 31

@Ishaan94 Look at the congruences mod c and d respectively. \[ec+fd=1\equiv fd\pmod{c}\qquad\text{(do you see why this is true)}\]\[bec+afd\equiv 0+a\cdot1\pmod{c}\]From this, we can see that if \(x=bec+afd\), then \(x\equiv a\pmod{c}\). From a similar argument we see that \(x\equiv b\pmod{d}\) as well.

Answer 32

Seems like I really need to grip a bit of my current Mathematics.
I am not completely able to understand the whole thing.

I'd tag you in this question when I need in the future, I promise you.
Thanks for the assistance, your majesty!\[\Huge \ddot \smile \]\[\Huge \color{yellow}{\star} \]

Answer 33

You guys may keep up with the discussion. Please do.

Answer 34

ec + fd (mod c) = fd or ec + fd =1 (mod c) = fd? i am unable to red the latter one.

Answer 35

read*

Answer 36

Note the following\[ec+fd\equiv fd\pmod{c}\]\[ec+fd=1\implies ec+fd\equiv1\pmod{c}\]Hence, \[fd\equiv1\pmod{c}\]

Answer 37

Ohh I see now :/

Answer 38

Then we can make a substitution to get\[bec+afd\equiv 0+a\cdot1\pmod{c}\]

Answer 39

okay. I think I understand why it's true.

Answer 40

thanks. i will try solving your problem now.