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

#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**+1 **

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

a=9k_{1}-1 that satisifes both the first and the last congruences

a=5k_{2}-1

a=7k_{3}-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

**answer 314**

Melody
Jul 31, 2017