CRT and System of Congruences

Printable View

October 12th 2009, 08:41 AM
kyldn6

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.
October 12th 2009, 08:45 AM
aman_cc

Quote:

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?
October 12th 2009, 07:02 PM
HallsofIvy

Quote:

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.

Quote:

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

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

Quote:

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"?
October 12th 2009, 09:32 PM
aman_cc

Quote:

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.
October 12th 2009, 10:08 PM
kyldn6

Yes, those were typos. And thanks everyone!