# Problem regarding linear congruence

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.

• For 4: 19 and yes you have the right idea for disproving 2. Sep 11 '18 at 17:10
• Any number which is $2$ more than a multiple of six will be $2$ more than a multiple of $3$ (i.e. $6k+2 = 3(2k)+2$). Similarly, any number which is $1$ more than a multiple of $9$ will be $1$ more than a multiple of $3$ (i.e. $9\ell + 1 = 3(3\ell)+1$). Now... is it possible for a number to simultaneously be $1$ more than a multiple of $3$ and $2$ more than a multiple of $3$ at the same time? Sep 11 '18 at 17:15
• @AHusain is there any other way than guessing (trial and error) please let me know how you find that thanks Sep 11 '18 at 17:24
• @JMoravitz i like your proof thanks Sep 11 '18 at 17:25
• The general method is to apply the Chinese reminder theorem, and thus finding equvalent formulations for all conditions that only use prime powers as moduli. Then you check for each prime separetly, starting with the highest prime power. So for problem 2) you find that your number must be $\equiv 1 \pmod 9$ and $\equiv 2 \pmod 3$, which is a contradiction, because $\equiv 1 \pmod 9$ implies $\equiv 1 \pmod 3$. You don't get a contradiction for 4), so this is possible. Of course, finding a value gives rise to a much easier proof, and usually Euclid's algorithm is used for that. Sep 11 '18 at 17:50

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

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

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

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

• For 4, not an only when. e.g. $m=3$ gives $12 \equiv 4$ Sep 11 '18 at 18:03
• Ah, of course, thanks for pointing it out. Amending as we speak. Sep 11 '18 at 18:06
• @thesmallprint , 12m≡−4mod8 and, even still, 4m≡4mod8 could you please explain this step Sep 13 '18 at 9:28
• Here, we are utilising the fact that $12$ and $4$ are in the same congruence class modulo $8$; the same goes for $-4$ and $4$. Sep 13 '18 at 10:13