Which of the following statement is False ?
1) There exists a natural number which when divided by 3 leaves remainder 1 and which when divided by 4 leaves remainder 0
2) There exists a natural number which when divided by 6 leaves remainder 2 and which when divided by 9 leaves remainder 1
3)There exists a natural number which when divided by 7 leaves remainder 1 and which when divided by 11 leaves remainder 3
4)There exists a natural number which when divided by 12 leaves remainder 7 and which when divided by 8 leaves remainder 3
1 and 3 are true because of Chinese remainder theorem . I guess 2 is false (since |6n-9m| is either 3 or 0 ) but i'm not sure how to prove /disprove 2 and 4.
Please give me a hint
Call this natural number $x$. Then $x\equiv 1\bmod 3$ and $x\equiv 0\bmod 4$. $3$ and $4$ are coprime so, by the Chinese remainder theorem, we get that $x\equiv 4\bmod 12$.
Again, let's call this natural number $x$. Then $x\equiv 2\bmod 6$ and $x\equiv 1\bmod 9$. Here, we cannot turn to the Chinese remainder theorem since $6$ and $9$ are not coprime. Instead, observe that $x\equiv 2\bmod 6$ is equivalent to $x\equiv 2+6m$ for some integer $m$. Now, if we substitute this into our second congruence, we get $2+6m\equiv 1\bmod 9$. This is the same as $6m\equiv 8\bmod 9$. Since there is no inverse for $6$ modulo $9$, we have that no solution exists.
Here, we have $x\equiv 1\bmod 7$ and $x\equiv 3\bmod 11$. Since $7$ and $11$ are coprime, by the Chinese remainder theorem, we obtain $x\equiv 36\bmod 77$.
We have $x\equiv 7\bmod 12$ and $x\equiv 3\bmod 8$. Applying a similar train of thought that we did for the second problem, we obtain $12m+7\equiv 3\bmod 8$, or equivalently, $12m\equiv -4\bmod 8$ and, even still, $4m\equiv 4\bmod 8$. The solutions to this congruence occur when $m\in\{1,3,5,7\}$ modulo $8$. This is equivalent to writing $m\equiv 8n+1$, $m\equiv 8n+3$, $m\equiv 8n+5$ and $m\equiv 8n+7$. Substituting these into our $12m+7$ expression leads us to conclude with these solutions: $x\equiv 19\bmod 96$, $x\equiv 43\bmod 96$, $x\equiv 67\bmod 96$ and $x\equiv 91\bmod 96$. So, this statement is true.
Therefore, statement 2 is the false one.