elementary number theory - Chinese Remainder Theorem/Simultaneous congruences

Find an integer N , 0 ≤ N < 105 such that

N ≡ 2 mod 3,

N ≡ 1 mod 5, and

N ≡ 4 mod 7.

What I have done:

So I have been able to start by splitting up the summation of $x$ into 3 sections:

$ x = 5*7 + 3*7 + 3*5 $

with the first multiplication corresponding with the mod 3 equation, the second multiplication corresponding with the mod 5 equation and the third multiplication corresponding with the mod 7 equation.

Therefore:

$x = 35 + 21 +15$

However, I know that this isn't complete. But I am not exactly sure on how to proceed.

Any help?

Answer

$N \equiv 2 \mod 3$ so $N = 2 + 3a$.

$N \equiv 1 \mod 5$ so $N =1 + 5b$

So $2+3a = 1 + 5b$ so $5b - 3a = 1$. One solution is $b = 2$ and $a = 3$

So $N \equiv 2 + 3*3 = 1 + 2*5 = 11 \mod 3*5$.

So $N = 11 + 15c$.

$N \equiv 4 \mod 7$ so $N = 4 + 7d$.

So $11 + 15c = 4 + 7d$ so $15c - 7d = -7$. $c =0$ and $d = 1$ is a solution.

So $N \equiv 11 = 4+7 \equiv 11 \mod 3*5*7 = 105$.

And, indeed, $11 \equiv 2 \mod 3$ and $11 \equiv 1 \mod 5$ and $11\equiv 4 \mod 7$.

---

Trying to follow your partition reasoning.

$5*7 = 35 \equiv 2 \mod 3$ so that satisfies.

$3*7 = 21 \equiv 1 \mod 5$ so that satisifies.

$3*5 = 15 \equiv 1 \not \equiv 4 \mod 7$ so that does not satisfy.

But $4*3*5 \equiv 4 \mod 7$ so that does.

So $5*7 + 3*7 + 60 = 116$ solves all three. But $116 > 105$. But any $k \equiv 116 \mod 105$ so do so $116 - 105 = 11$ will do.

.... or ... when we hae $3*5 \equiv 1 \mod 7$ and we could have figured $4 \equiv -3 \mod 7$ so $-3*3*5 \equiv 4 \mod 7$.

So $N = 5*7 + 3*7 - 3*3*5 = 11$. (by taking a negative we know we won't get a number too large).

Actually, I had never done the "partitioning" before.

It works well. I like it.