# Thread: CRT and System of Congruences

1. ## CRT and System of Congruences

$x\equiv1\ (mod\ 3)$
$x\equiv3\ (mod\ 5)$
$x\equiv5\ (mod\ 7)$

I did this exercise based on this post: http://www.mathhelpforum.com/math-he...ongruence.html
And I just want to know if I did this properly and if this is the right approach.

$x\equiv1\ (mod\ 3)\ \Rightarrow\ 5x\ \equiv5\ (mod\ 15)\ \Rightarrow\ 10x\ \equiv10\ (mod\ 15)$
$x\equiv3\ (mod\ 5)\ \Rightarrow\ 3x\ \equiv9\ (mod\ 15)\ \Rightarrow\ -9x\ \equiv-27\ (mod\ 15)$
Adding gives $x\equiv-17 \ (mod\ 15)$

Comparing with the third equation:

$x\equiv-17\ (mod\ 15)\ \Rightarrow\ 7x\ \equiv-119\ (mod\ 105)\ \Rightarrow\ -14x\ \equiv238\ (mod\ 105)$
$x\equiv5\ (mod\ 7)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)$
Adding gives $x\equiv313\ (mod\ 15)$

So the solution is $\{313+15k:k\in\mathbb{Z}\}$

While I'm here, can anyone tell me what the easiest way to find the inverse of a congruence is? I seem to struggle with that.

2. Originally Posted by kyldn6
$x\equiv1\ (mod\ 3)$
$x\equiv3\ (mod\ 5)$
$x\equiv5\ (mod\ 7)$

I did this exercise based on this post: http://www.mathhelpforum.com/math-he...ongruence.html
And I just want to know if I did this properly and if this is the right approach.

$x\equiv1\ (mod\ 3)\ \Rightarrow\ 5x\ \equiv5\ (mod\ 15)\ \Rightarrow\ 10x\ \equiv10\ (mod\ 15)$
$x\equiv3\ (mod\ 5)\ \Rightarrow\ 3x\ \equiv9\ (mod\ 15)\ \Rightarrow\ -9x\ \equiv-27\ (mod\ 15)$
Adding gives $x\equiv-17 \ (mod\ 15)$

Comparing with the third equation:

$x\equiv-17\ (mod\ 15)\ \Rightarrow\ 7x\ \equiv-119\ (mod\ 105)\ \Rightarrow\ -14x\ \equiv238\ (mod\ 105)$
$x\equiv5\ (mod\ 7)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)$
Adding gives $x\equiv313\ (mod\ 15)$

So the solution is $\{313+15k:k\in\mathbb{Z}\}$

While I'm here, can anyone tell me what the easiest way to find the inverse of a congruence is? I seem to struggle with that.

Let me suggest you a nice observation here.

x+2 = 0(mod 3)
x+2 = 0(mod 5)
x+2 = 0(mod 7)

Now can you take it fwd?

Also haven't seen your eqs in details but answer appear wrong. Put k=1 and try the last congruence?

3. Originally Posted by kyldn6
$x\equiv1\ (mod\ 3)$
$x\equiv3\ (mod\ 5)$
$x\equiv5\ (mod\ 7)$

I did this exercise based on this post: http://www.mathhelpforum.com/math-he...ongruence.html
And I just want to know if I did this properly and if this is the right approach.

$x\equiv1\ (mod\ 3)\ \Rightarrow\ 5x\ \equiv5\ (mod\ 15)\ \Rightarrow\ 10x\ \equiv10\ (mod\ 15)$
$x\equiv3\ (mod\ 5)\ \Rightarrow\ 3x\ \equiv9\ (mod\ 15)\ \Rightarrow\ -9x\ \equiv-27\ (mod\ 15)$
Adding gives $x\equiv-17 \ (mod\ 15)$

Comparing with the third equation:

$x\equiv-17\ (mod\ 15)\ \Rightarrow\ 7x\ \equiv-119\ (mod\ 105)\ \Rightarrow\ -14x\ \equiv238\ (mod\ 105)$
$x\equiv5\ (mod\ 7)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)\ \Rightarrow\ 15x\ \equiv75\ (mod\ 105)$
Adding gives $x\equiv313\ (mod\ 15)$
I think you mean $x\equiv 313 (mod 105)$ here.

So the solution is $\{313+15k:k\in\mathbb{Z}\}$
And $\{313+105k:k\in\mathbb{Z}\}$ here.

While I'm here, can anyone tell me what the easiest way to find the inverse of a congruence is? I seem to struggle with that.
What do you mean by "inverse of a congruence"?

4. Originally Posted by HallsofIvy
I think you mean $x\equiv 313 (mod 105)$ here.

And $\{313+105k:k\in\mathbb{Z}\}$ here.

What do you mean by "inverse of a congruence"?
Yes this looks correct. Thanks.
@kyldn6 But you don't have to perform any of these modular calculations if you look at the observations I said earlier. It comes directly from there, atleast in this question.

5. Yes, those were typos. And thanks everyone!