Find $x$ given remainders mod $2, 3, 4, 5, 6, 7$ Here is the problem:

If eggs are counted in pairs one will remain, if counted in threes two will remain, if counted in fours three will remain, if counted in fives four will remain, if counted in sixes five will remain, if counted in sevens nothing will remain. How many eggs were there?

I framed equations using Euclid's lemma: $a=b×q+r$, $a=2×q+1$ etc. But I couldn't arrive at the solution
 A: I assume your question is asking:

Find $x$ such that
\begin{align*}
    x &\equiv 1 \pmod 2\\
      &\equiv 2 \pmod 3\\
      &\equiv 3 \pmod 4\\
      &\equiv 4 \pmod 5\\ 
      &\equiv 5 \pmod 6\\
      &\equiv 0 \pmod 7 
\end{align*}

Now, this is really actually quite a unique question in that while you certainly could use the CRT, there is a trick that you can use to solve this specific question much faster!
Suppose instead that our question is asking

Find $x$ such that
\begin{align*}
    x &\equiv 1 \pmod 2\\
      &\equiv 2 \pmod 3.
\end{align*}

Because $x$ is one less than $2$ & $3$, we find $x$ to be one less than lcm$(2, 3) = 5$, which we can see is $1 \pmod 2$ and $2 \pmod 3$. This will be true for however many congruences we have, so long as $x$ is one less than the modulus (can you prove this?).
Thus, for our original problem, we can do the same thing. So, we find that lcm$(2, 3, 4, 5, 6) = 60$ which yields the answer $60 - 1 = 59$.
However, we also need this number to be divisible by $7$, so we can take multiples of our lcm$(2, 3, 4, 5, 6) = 60$ and check values from there.
The next multiple of $60$ is $120$ which yields the solution $119$, which is in fact divisible by $7$!!
