+0

# Determine the smallest non-negative integer that satisfies the congruences:

0
46
3
+74

Determine the smallest non-negative integer  that satisfies the congruences:

\begin{align*} &a\equiv 2\pmod 3,\\ &a\equiv 4\pmod 5,\\ &a\equiv 6\pmod 7,\\ &a\equiv 8\pmod 9. \end{align*}

RektTheNoob  Jul 30, 2017
Sort:

#1
+1

Since the LCM of  3, 5, 7, 9 =315, and the remainders are 1 less than the moduli in each case, therefore the smallest number that satisfies the congruences is:

315 - 1 = 314, so that you have:

315N + 314 and N =0, 1, 2, 3......etc. So:

a = 314, 629, 944.....etc.

Guest Jul 30, 2017
edited by Guest  Jul 30, 2017
#3
+89752
+1

Thanks Guest, I just wanted to think this one through myself :)

a=9k1-1    that satisifes both the first and the last congruences

a=5k2-1

a=7k3-1

So if a is 1 less than a multiple of 5 and 9 and 7 then it must be 1 less than any common factor of 9 and 5 and 7

So the smallest one is 1 less than 315