4
$\begingroup$

First, let $m$,$n$ be coprime.

Suppose we want to find:

$x\equiv y\text{ mod }m$

$x\equiv z\text{ mod }n$

As m,n are coprime $\exists a,b\in\mathbb{Z}:am+bn=1$ (GCD=1 basically)

Then, for $y\in\mathbb{Z}$ we have $ybn=y\text{ mod }m$ and $ybn = 0\text{ mod }n$

Then, for $z\in\mathbb{Z}$ we have $zam=z\text{ mod }n$ and $zam = 0\text{ mod }m$

Thus $$ybn+zam\equiv y\text{ mod }m$$ and $$ybn+zam\equiv z\text{ mod }n$$


I am happy with this, I am them asked to find $x$ where $x\equiv 2\text{ mod }7$ and $x\equiv -2{ mod }11$ this is easy you just choose $y,b,n,z,a,m$ so the forms match, which explains why the first part wanted an explicit solution to $7a+11b=1$

The actual question

Part 2 is different, it wants me to give an explicit solution to $$77a+13b=1$$ (easy enough, $a=-1,b=6$ works) and to find $k$ such that:

$k\equiv 2\text{ mod }7$

$k\equiv -2\text{ mod }11$

$k\equiv -1\text{ mod }13$

I'm not sure how to do this in the way I'd like to / the question wants, I may not say $k\equiv \text{(something) mod }77$ but 77 is 7*11, and the last part was about a 7 and an 11!

How do I do this in the spirit of the question?

I have tagged this as "Abstract algebra" and "Ring theory" because it follows on from some work about defining a bijection from rings that are cyclic groups of coprime orders. I have titled it Chinese Remainder Theorem because that can be phrased to state "The rings $Z_mXZ_n$ are isomorphic if and only if m, n are coprime" and then it finds them.

$\endgroup$
  • $\begingroup$ From the first part, $\ k\equiv 2\pmod 7\,$ and $\ k\equiv -2\pmod{11}\ $ $\iff $ $\,k\equiv \ldots\pmod{77}.\,$ Next apply CRT to that combined with $\,k\equiv -1\pmod{13},\,$ using the work in the second part. $\endgroup$ – Bill Dubuque Mar 3 '14 at 2:59
  • $\begingroup$ @BillDubuque of course! I'm not sure why you used dots, it is obviously 9! Thanks. $\endgroup$ – Alec Teal Mar 3 '14 at 7:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.