linear congruence questions

Question

A:

For the two systems of linear congruences, one system has integer solutions while the other does not. For the system with integer solutions, write down 2 of them whose difference is less than 192. For the other system, explain why no integer solution exists.

A: n congruent 13 (mod 16)
   n congruent 5 (mod 12)

B: n congruent 14 (mod 16)
   n congreunt 4 (mod 12)

B:

Let a1 and a2 be integers. Let m1 and m2 be natural numbers. Let d = gcd(m1,m2) Based on your observations from part A, complete the following proposition and prove it.

Proposition1: The system: n congruent a1 (mod m1) n congruent a2 (mod m2) has an integer solution if and only if ____ (The blank needs to be filled with a simple condition on a1,a2,d)

Answer 1

Hint $\ \ d\mid 12,16\,\Rightarrow\, \begin{array}{}d\mid 12\mid n\!-\!a\\ d\mid 16\mid n\!-b\end{array}\Rightarrow\,d\mid n\!-\!b-(n\!-\!a) = a\!-\!b$

Or, equivalently, $\,{\rm mod}\ d\!:\,\ a\equiv n\equiv b\ $ is a necessary condition for solvability.

Answer 2

Partial answer first: system B has no integer solutions: n = 14( mod 16) ==> n = 16k + 14, and n = 4(mod 12) ==> n = 12m + 4 ==> 12m + 4 = 16k + 14 ==> 12m - 16k = 10 ==> 6m - 8k = 5. This is not possible because 6m - 8k = 0 (mod 2), but 5 = 1 (mod 2).