About Chinese Remainder Theorem

peterso

New member
Joined
Sep 11, 2019
Messages
1
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
Joined
Jan 27, 2012
Messages
5,428
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
Joined
Mar 25, 2016
Messages
1,297
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
Joined
Mar 25, 2016
Messages
1,297
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.
 
Top