Proof verification: Find the number of positive integer between $1$ and $300$ that satisfies the given linear congruences.

Question

Problem: Find the number of positive integer lying between $1$ and $300$ that satisfies the linear congruences $$x\equiv 1\pmod4\\ x\equiv 0\pmod3\\ x\equiv 5\pmod7$$

My approach:

Here $~4,~3,~7~$ are pairwise prime to each other.
Let $~m=4\times 3\times 7=84.~$
Let $~M_1=\frac m4=21,~~M_2=\frac m2=28,~~M_3=\frac m7=12.~$
Then $~~\gcd(M_1,4)=1,~~\gcd(M_2,3)=1,~~\gcd(M_3,7)=1~.$

Now since $~\gcd(M_1,4)=1,~$ the linear congruence $21x\equiv 1~\pmod4~$ has a unique solution and the solution is $~x\equiv 1~\pmod4~.$

Again since $~\gcd(M_2,3)=1,~$ the linear congruence $28x\equiv 1~\pmod3~$ has a unique solution and the solution is $~x\equiv 1~\pmod3~.$

Also since $~\gcd(M_3,7)=1,~$ the linear congruence $12x\equiv 1~\pmod7~$ has a unique solution and the solution is $~x\equiv 3~\pmod7~.$

Therefore $~x_0=1\cdot(21\cdot1)+0\cdot(28\cdot1)+5\cdot(12\cdot3)=201~$ is a solution and the solution is unique modulo $~84~.$

Hence the solution of the given system is $~x\equiv 201~\pmod{84}\equiv 33~\pmod{84}~.$

i.e., the solutions are $~33,~117,~201,~285,~369,~\cdots~$

Answer of the given question as per my approach:

The number of positive integer lying between $1$ and $300$ that satisfies the given linear congruences is $4~.$

Questions:
$(a)~$Is this okay ?
$(b)~$Is there any other short and easy method there to solve the following problem except of my approach ?

Answer 1

a) The solution, as you correctly found, is $x \equiv 33 \pmod{84}$, that is, integers of the form $33+k84$. Before you edited the question, you considered integers of the form $33+k33$ instead. Now you are considering the correct ones.

b) For a possibly shorter solution, consider this: since $5\equiv 1 \pmod{4}$, set $y:=x-5$. Then $y$ satifies: $$y\equiv 0\pmod4\\ y\equiv 1\pmod3\\ y\equiv 0\pmod7 $$ The first and the last congruences allow to write $y=28t$, so that all we have to solve is: $$ 28t \equiv 1 \pmod 3$$ Being $28 \equiv 1 \pmod 3$, we get $t= 1 + 3k$, so $y=28 + 84k$ and finally $x= 33+ 84k$. Now, every set of consecutive 84 integers contains precisely one solution. Since $300=3\cdot 84 + 48$ you know the number of solutions in $[1,300]$ is $4$ or $3$, according as a solution exists in $[1,48]$. This leads to the answer $4$.

Answer 2

Correct. Easier: mentally, by Easy CRT, where sup/subscripts are moduli

$$\begin{align} &x\overset{7}\equiv \color{#0a0}5,\ x\overset{4}\equiv \color{#c00}1 \iff x\,\overset{28}\equiv\,\color{#0a0}5\,+\,7\left[\frac{\color{#c00}1-\color{#0a0}5}{7}\right]_4\!\!\equiv 5\,+\,7\,\left[\frac{0}{3}\right]\equiv\, \color{#90f}5\\[.4em] &x\overset{28}\equiv \color{#90f}5,\ x\overset{3}\equiv \color{orange}0\iff x\,\overset{84}\equiv\, \color{#90f}5+28\left[\frac{\color{orange}0-\color{#90f}5}{28}\right]_3\!\!\equiv 5+28\left[\frac{1}{1}\right]\equiv \bbox[5px,border:1px solid #c00]{33}\end{align}\qquad\qquad$$

Remark $ $ We chose mod $7$ first since $7\overset{4}\equiv-1,\,7\overset{3}\equiv1\, $ so it's easy to invert in Easy CRT. We chose mod $4$ next since $\,\color{#c00}1\overset{4}\equiv\color{#0a0}5\,$ so $\left[\frac{\color{#c00}1-\color{#0a0}5}{7}\right]_4\! = 0\,$ so we don't even need to compute $\,7^{-1}\equiv 1/7\bmod 4$ (even though easy); equivalently $\,x\overset{4}\equiv\color{#c00}1\equiv\color{#0a0}5,\,x\overset{7}\equiv\color{#0a0}5\!\iff\! x\overset{28}\equiv\color{#0a0} 5\,$ by CCRT = Constant case CRT.