4

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,

Hi I am Max
  • 101
  • I mean, it depends on whether you've covered Bezout's Theorem in your class already. – It'sNotALie. Aug 15 '19 at 04:16
  • Thank you for the remind :D, I did learn the theorem and forgot its name. May I ask how can I deduce 12? I kind of lost myself here. – Hi I am Max Aug 15 '19 at 04:29
  • I'm confused what you mean by come up with 12. – It'sNotALie. Aug 15 '19 at 04:40
  • Sorry for the ambiguity. I wondered why it is modulo 12. I mean I have figured out the answer 7 mod 12. 7 thanks to your reminder, Bezout's Theorem, although by that time we have only figured the part am+bn=1 as a corollary. I still had no idea about the legit proof of modulo 12 which should be more comprehensive than a simple hcf(3,4)=12 in my answer. Thank you again :D – Hi I am Max Aug 15 '19 at 05:52
  • Brush up on the chinese remainder th. – fleablood Aug 15 '19 at 07:10
  • @fleablood Thank you so much. I agree that using crt is the most effective way of solving this question. It is not covered in foundation course, unfortunately.(◔◡◔) I forgot crt completely XD – Hi I am Max Aug 15 '19 at 12:10
  • As you have had several answers, and some time to think about them, let me encourage you to "accept" one of them by clicking in the check mark next to it. – Gerry Myerson Aug 22 '19 at 01:15

3 Answers3

1

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$$

AgentS
  • 12,195
  • Thank you so much for your answer. The substitution is so impressive. Whilst I still don't quite get it why you would come up with the idea of multiplying by 3 here ( •̥́ ˍ •̀ू ) – Hi I am Max Aug 15 '19 at 05:43
  • Ahh that was a bit tricky... Only multiplying by $3$ isolates $k$ by itself in $\mod 4$ – AgentS Aug 15 '19 at 05:47
  • At third step in the answer, multiplying by $3$ is not obvious at all yeah – AgentS Aug 15 '19 at 05:50
  • We want to write $k$ as $r+4m$ so that when you plug $k$ back in $3k+1$, we will have used both the given info: $x = 3k+1$ and $x=4l-1$ – AgentS Aug 15 '19 at 05:58
  • Thank you so much. I can see the intention of mutilplying 3 with the help from @Gerry Myerson 's answer. – Hi I am Max Aug 15 '19 at 11:08
  • yw:) Another not so clever way is to view the problem as solving the system of linear congruences: $x\equiv 1\pmod 3$ and $x\equiv -1\pmod{4}$. First congruence gives $x=3k+1$. Plugging this in second congruence gives $3k+1\equiv -1 \pmod{4}$. solving this for $k$ and plugging back in $x$.. – AgentS Aug 15 '19 at 11:53
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$$

Bill Dubuque
  • 272,048
  • Thank you so much! I clearly see why 3 and 4 as devisors of x-x0, since we can rewrite x and x0 as x=3k+1, x0=3k0+1; x=4l-1, x0=4l0-1 where there exist two natural numbers k and k0. Thank you again (◔◡◔). – Hi I am Max Aug 15 '19 at 22:28
0

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.

Gerry Myerson
  • 179,216