# number prime to $bc$ with system of congruences

Can you please help me to understand why all numbers $x$ prime to $bc$ are all the solutions of this system? \begin{align*} x&\equiv k\pmod{b}\\ x&\equiv t\pmod{c} \end{align*} Here $k$ is prime to $b$, and $t$ is prime to $c$.

-
I think you mean "number prime to $bc$" not "prime number with $bc$". – Zev Chonoles Jun 19 '12 at 20:25
Sorry both for my very basic math knowledge. And my bad english. Question modified, you both were right. – Zagorax Jun 19 '12 at 20:27
Careful: it's true that if $x$ is prime to $bc$, then there exist $k$ that is coprime with $b$, and $t$ that is coprime to $c$, such that $x\equiv k\pmod{b}$ and $x\equiv t\pmod{c}$; and conversely, that if $k$ is coprime to $b$ and $t$ is coprime to $c$, then any solution to the system of congruences will be coprime to $bc$. It is generally not true that there exist $k$ that is coprime to $b$ and $t$ that is coprime to $c$ such that any $x$ that is coprime to both $b$ and $c$ must satisfy $x\equiv k\pmod{b}$ and $x\equiv t\pmod{c}$, which your phrasing allows as an interpretation. – Arturo Magidin Jun 19 '12 at 20:46
Thank you for your edit. I just fixed a typo. :) – Zagorax Jun 19 '12 at 20:54
On first reading I interpreted the problem as saying that a number $x$ is prime to $bc$ if and only if it is prime to both $b$ to $c$. I think the statement sort of obscures this. – Dylan Moreland Jun 19 '12 at 21:06

Suppose that $x\equiv k \pmod{b}$, where $k$ and $b$ are relatively prime. We show first that $x$ and $k$ are relatively prime.

For suppose to the contrary that $d \gt 1$ divides both $x$ and $b$. Since $x-k=qb$ for some integer $q$, we have $k=x-qb$. By assumption $d$ divides $x$ and $b$, so $d$ divides $x-nb$. It follows that $d$ divides $k$, contradicting the fact that $k$ and $b$ are relatively prime.

Similarly, $x$ and $c$ are relatively prime.

Finally, we show that $x$ and $bc$ are relatively prime. There are various ways to prove this. For example, if $x$ and $bc$ are not relatively prime, there is a prime number $p$ that divides both $x$ and $bc$. But since $p$ divides $bc$, it follows that $p$ divides $b$ or $p$ divides $c$ (or both). If for example $p$ divides $b$, that contradicts the fact that $x$ and $b$ are relatively prime.

Remark: There is a mild ambiguity in the statement of the problem. We have shown that any $x$ that is a common solution of the congruences must be relatively prime to $bc$. But in general a number relatively prime to $bc$ need not be a solution of the system of congruences. Generally most of them aren't. If $b$ and $c$ are themselves relatively prime, there will be only one $x$ in the interval $0\le x\lt bc$ which satisfies both congruences.

-
Actually it was part of a problem that demonstrates that $\phi(bc)$ is equal to $\phi(b)$$\phi(c)$. That was suggested as a starting point for this demonstration, so I thought that all and only the solution of that system were prime to $bc$. But it seems false since your remark. – Zagorax Jun 21 '12 at 8:39
All the solutions are relatively prime to $bc$. But certainly not all numbers relatively prime to $bc$ are solutions. For proving the result about $\varphi$ along the lines you describe, I think you may need the Chinese Remainder Theorem. – André Nicolas Jun 21 '12 at 8:52

Hint $\rm\quad \begin{eqnarray} x\equiv k\,\ (mod\ b)&\Rightarrow&\rm\:(x,b) = (k,b) = 1 \\ \rm x\equiv t\,\,\ (mod\ c)\,&\Rightarrow&\rm\:(x,c) =\, (t,c) = 1\end{eqnarray} \Bigg\}\ \Rightarrow\ (x,bc) = 1\ \ by\ Euclid's\ Lemma$

-