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$.
number prime to $bc$ with system of congruences
-
0On 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. – 2012-06-19
2 Answers
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.
-
0All 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. – 2012-06-21
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$