Multiple-select question on chinese remainder theorem

Question

Which of the following integers can be written in the form $595m+252n$ where $m$ and $n$ are integers.

1. $1$
2. $5$
3. $7$
4. $63$

Now can we use the Chinese remainder theorem in this?

I don't know how could we apply that here.

Please help.

Answer 1

The $\text{gcd}$ of $252$ and $595$ is pretty easily seen to be $7$ (see @J.W. Tanner's comment).

Then by Bezout's identity, $7$ is a linear combination of $252$ and $595$. (To get such a linear combination, you can use the Euclidean algorithm and then work backwards. This is called the extended Euclidean algorithm.)

Furthermore, if any other number could be written as a such a linear combo, it would be a multiple of $7$ (also noted by @J.W. Tanner). So, since $63$ is a multiple of $7$, we get $3.$ and $4.$ for our solutions.