Proof of intersection of two positive integer congruence classes

Question

I am reviewing the foundation course I took in year 1 while a question caught my eyes：

Let A be the congruence class of 1 mod 3, and B the congruence class of -1 mod 4. Prove that A∩B is a congruence class mod 12.

The answer is simple, 7 mod 12. However, I wonder if I need to prove that when m,n happen to be coprime ( hcf(m,n)=1, i.e hcf(3,4)=1 here in particular ), there exist a,b ( a,b belong to integers ) in which am+bn=1 beforehand.

I am not certain about it since the proof of it seems a bit too much for a question phrased as above: mZ+nZ=gZ for some g which belongs to natural numbers. g must to be a common factor of m and n, since mZ and nZ are subgroups of gZ. mZ+nZ (i.e gZ) is contained in every subgroup containing both mZ and nZ, hence, gZ=mZ+nZ=hcf(m,n)Z

Therefore, 1-(-1)=2=2(4-3)=2*4-2*3, 2*4-1=7=2*3+1 lcm(3,4)=12

May I ask do I really need to write down the proof of existence of (a,b) such that am+bn=1 when hcf(m,n)=1in order to answer this question?

Also, I really struggle to explain how I come up with 12 here.

Thank you so much！

Regards,

Answer 1

Hint $ $ if $\,x_0 \in A\cap B\,$ then $\,x \in A\cap B \!\iff\! 3,4\mid x\!-\!x_0\!\color{#c00}\iff\! 12\mid x\!-\!x_0\!\iff\! \bbox[6px,border:1px solid #c00]{x \in x_0\!+\!12\Bbb Z}$

Remark $ $ Generally for moduli $m,n\!:\ m,n\mid x\!-\!x_0\color{#c00}\iff {\rm lcm}(m,n)\mid x\!-\! x_0.\,$ OP is the special case where $\,\gcd(m,n) = 1\ [\!\iff {\rm lcm}(m,n) = mn\:\!$].

This is equivalent to the uniqueness half or CRT = Chinese Remainder Theorem (the other half = existence states that such an $\,x_0\,$ exsists). The view in terms of cosets becomes clearer if you study the ring-theoretic form of CRT, i.e.

$$ \gcd(m,n)=1\ \Rightarrow\ \Bbb Z/m \times \Bbb Z/n\, \cong\, \Bbb Z/mn\qquad\qquad\qquad$$

Answer 2

If a number can be represented as both $3k+1$ and $4l-1$, then that number can also be represented as $12m+7$. This can be seen by a simple substitution:

Say $x=3k+1 = 4l-1$
$3k +2 = 4l$
$9k+6=12l$
$k+6 = 4(3l-2k) $
$k-2 = 4(3l-2k-2)$
$k = 2+4m$

Substituting $k$ back in $x$ gives $$x=3k+1=3(4m+2)+1 = 12m+7$$

Answer 3

Every congruence class modulo $3$ is the union of four congruence classes modulo $12$. Every congruence class modulo $4$ is the union of three congruence classes modulo $12$. So $A\cap B$ is the union of some number of congruence classes modulo $12$. To prove it's precisely one class, just try all $12$ classes and see that elements of $11$ of them don't work.