DiscMat assignment 7

exercise

7.2 Properties of GCD and LCM

1)

Let $d_1=gcd(a,c)$ and $d_2=gcd(b,c)$. We first show that $gcd(d_1,d_2)=1$

• Assume there is a common divisor $x$ of $d_1$ and $d_2$ with $x>1$ , then $x|gcd(a,c)$ and $x|gcd(b,c)$
• By definition of $gcd$, we get $x|a$ and $x|c$ and $x|b$
• This contradicts to the statement that $gcd(a,b)=1$, so $gcd(d_1,d_2)=1$ must hold.

We then show that $d_1{d}_2|gcd(ab,c)$

• Since $d_1|a$ and $d_2|b$, we can conclude that $d_1{d}_2|ab$
• We also know that $d_1|c$ and $d_2|c$, and $gcd(d_1,d_2)=1$
  • set $c=k{d}_1$ where $k$ a positive integer (since $d_1|c$)
  • so $d_2|c$ gives $d_2|k{d}_1$
  • Because $gcd(d_1,d_2)=1$, Euclid’s lemma implies $d_2|k$. Let’s then write $k=d_{2}t$ where $k$ is also a positive integer
  • Therefore $c=d_{1}k=d_1{d}_{2}t$
  • Hence, $d_1{d}_2|c$
• According to the definition of $gcd(ab,c)$, we have $\forall x((x|ab\wedge x|c)\to x|gcd(ab,c))$
• Let $x=d_1{d}_2$ (since $d_1{d}_2$ satisfies $d_1{d}_2|ab$ and $d_1{d}_2|c$). Then we must have $d_1{d}_2|gcd(ab,c)$

We then show that $gcd(ab,c)|d_1{d}_2$

• Let $d=gcd(ab,c)$ with $d|ab$ and $d|c$
• we write $d$ as $d={\prod }_i{p}_i^{e_i}$. Because $gcd(a,b)=1$, each prime of $d$ divides exactly $a$ or $b$. we then split $d$ into $d=d_a{d}_b$ with $d_a|a$ (containing primes that divides $a$) and $d_b|b$ (containing primes that divides $b$)
• Since $d|c$, we get $d_a|c$ and $d_b|c$. Thus $d_a|d_1$ and $d_b|d_2$
• Therefore, we get $d=d_a{d}_b|d_1{d}_2$, meaning $gcd(ab,c)|d_1{d}_2$ Conclusion By showing $d_1{d}_2|gcd(ab,c)$ and $gcd(ab,c)|d_1{d}_2$, we proved that $d_1{d}_2=gcd(ab,c)$, which means $gcd(ab,c)=gcd(a,c)\cdot gcd(b,c)$ The claim is proved.

2)

We write $a,b,c$ as followings:

$$a=\prod _i{p}_i^{e_i},b=\prod _i{p}_i^{f_i},c=\prod _i{p}_i^{g_i}$$

We now write the left part of the equation as

$$lcm(a,gcd(bc))=lcm(\prod _i{p}_i^{e_i},\prod _i{p}_i^{min(f_i,g_i)})=\prod _i{p}_i^{max(e_i,min(f_i,g_i))}$$

We now write the right part of the equation as

$$gcd(lcm(a,b),lcm(a,c))=gcd(\prod _i{p}_i^{max(e_i,f_i)},\prod _i{p}_i^{max(e_i,g_i)})=\prod _i{p}_i^{min(max(e_i,f_i),max(e_i,g_i))}$$

We now only need to prove that $max(e_i,min(f_i,g_i))=min(max(e_i,f_i),max(e_i,g_i))$ We show that $max(x,min(y,z))=min(max(x,y),max(x,z))$

• case 1: $x\ge min(y,z)$
  • $max(x,min(y,z))=x$
  • At least one of $y$ and $z$ is smaller or equal to $z$. Therefore one of $max(x,y)$ and $max(x,z)$ must be $x$ and the other one must be greater or equal to $x$. Hence, $min(max(x,y),max(x,z))$ must be $x$. Thus, $max(x,min(y,z))=min(max(x,y),max(x,z))=x$
• case 2: $x<min(y,z)$
  • $max(x,min(y,z))=min(y,z)$
  • $max(x,y)=y$ and $max(x,z)=z$, so we have $min(max(x,y),max(x,z))=min(y,z)$
  • $max(x,min(y,z))=min(max(x,y),max(x,z))=min(y,z)$ Hence, the statement $max(x,min(y,z))=min(max(x,y),max(x,z))$ always holds Therefore,

$$lcm(a,gcd(bc))=\prod _i{p}_i^{max(e_i,min(f_i,g_i))}=\prod _i{p}_i^{min(max(e_i,f_i),max(e_i,g_i))}=gcd(lcm(a,b),lcm(a,c))$$

The claim is proved.