# About Chinese Remainder Theorem

#### peterso

##### New member
the question is find all possible integers a which satisfy the following system of congruences

a = 3 mod 6
a = 4 mod 7
a = 6 mod 15

but I find a = 3 mod 6 is 105n1 = 3n1 = mod 6
and their gcd is 3 not 1 so in this question is it no solutuion?

#### HallsofIvy

##### Elite Member
Strictly speaking the "Chinese remainder theorem" does not apply here because 6 and 15 are not mutually prime. There does not exist such an a.

#### ksdhart2

##### Senior Member
Wait, what? Why can't there exist such an $$a$$? Am I missing something? Let a = 81, then:

$$\displaystyle 81 \equiv 3 \mod 6 \\ 81 \equiv 7 \mod 4 \\ 81 \equiv 6 \mod 15$$
I agree that the Chinese Remainder Theorem won't help here, but I found this solution, among infinitely many others, simply by considering the system of equations:

$$\displaystyle a = 6K + 3 \\ a = 7L + 4 \\ a = 15M + 6 \\ \{K, L, M\} \in \mathbb{Z}$$

#### ksdhart2

##### Senior Member
Whoops! I've just been informed I made a big error and reversed the numbers. I meant to type "4 mod 7" to be consistent with the information given in the problem. That's my bad, sorry about that.