Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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$.

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.