Assignment 2

Exercise $\PageIndex{1}$

1. Compute $gcd(-231,150)$ and express it as a linear combination of $-231$ and $150.$
2.  Find $gcd(-231,150)$ and $lcm(231, 150)$ using prime factorization.
3.  Find Euler Totient function $\phi(150)$ and $\phi(231)$.

Answer

1. $$\begin{align*} -231 &= -2(150)+69\\ 150 &= 2(69)+12\\69 &= 5(12)+9\\12 &= 1(9) + 3\\9&=3(3)+0. \end{align*}$$  Hence, $gcd(-231,150) = 3.$ By using Bezout's algorithm,  $$\begin{align*} 3 &= 12(1) + (-9)(1)\\  &= 12(1) + (-69(1) + 12(5))(1)\\&= 12(6) + (-69)(1)\\ &= (150(1) - 69(2))(6) + (-69)(1)\\ &= 150(6) + (-69)(13)\\ &= 150(6) - (-231(1) + 150(2))(13)\\ &= 150(-20) + (-231)(-13).\end{align*}$$

2. Since $gcd(-231,150)=gcd(231,150),$ $231 = (3)(7)(11),$ and $150 = (2)(3)(5^{2} )$,$gcd(-231,150)= gcd(231,150)=3.$ 

$lcm( (3) (7) (11), (2)(3)(5^{2} )) = (2)(3)(5^{2} )(7)(11).$

3. $\phi(150)=(2-1)(3-1)(5^{2}-5 )=40$ and $\phi(231)=(3-1) (7-1) (11-1)=120$.

Exercise $\PageIndex{2}$

1. Let $a, b,c \in \mathbb{Z}_+$. Show that $gcd(a, bc) = 1$ if and only if $gcd(a, b) = 1$  and $gcd(a, c) =1$.
2. For every integer $n$, prove that  $n^3+2n$  is divisible by $3$.

Answer

1. Let $a, b,c \in \mathbb{Z}_+$ Assume that $gcd(a, bc) = 1$. Then there exist integers$x$ and $y$ such that $a(x)+bc(y)=1.$ Thus $a(x)+b(cy)=1$ and $a(x)+c(by)=1.$ Since $x, cy, by \in \mathbb{Z},$ $gcd(a, b) = 1$  and $gcd(a, c) =1$.

Conversely, assume that $gcd(a, b) = 1$  and $gcd(a, c) =1$. Then there exist integers$x,y,v$ and $w$ such that $a(x)+b(y)=1$ and $a(v)+c(w)=1.$ Consider $1=(ax + by)(av + cw) = a^2xv + axcw+ byav + bycw=a( axv + xcw+ yav)+(bc)yw.$ Since $( axv + xcw+ yav),yw  \in \mathbb{Z}$, $gcd(a, bc) = 1$.

2. Let $n \in \mathbb{Z}$.

Proof by Cases:

 Case 1: $n \equiv 0 (\mod \, 3) \implies n^{3} \equiv 0^{3} (\mod \, 3)$

Consider $n^{3} + 2n = (0^{3} + 0)(mod \, 3) \equiv 0 (\mod \, 3)$.

Thus $3 \mid (n^{3} + 2n)$.

Case 2: $n \equiv 1 (\mod \, 3) \implies n^{3} \equiv 1^{3} (\mod \, 3)$

Consider $n^{3} + 2n = (1 + 2)(\mod \, 3) \equiv 3 (\mod \, 3)$

Thus, $3 \mid (n^{3} + 2n)$ 

Case 3: $n \equiv 2 (\mod \, 3) \implies n^{3} \equiv 2^{3} (\mod \, 3)$

Consider $n^{3} + 2n = (8 + 4)(\mod \, 3) \equiv 12 (\mod \, 3)$

Thus $3 \mid (n^{3} + 2n)$.

Hence the result.

Exercise $\PageIndex{3}$

Let $a, b, c \in \mathbb{Z},$ and $m \in \mathbb{Z}_+,$ such that $a\equiv b(\mod\, m).$ Show that 

1. $a+c\equiv b+c(\mod \,m).$
2. $ac\equiv bc(\mod\, m).$
3. $a^2\equiv b^2(\mod\, m).$

Answer

 Let $a, b, c \in \mathbb{Z},$ and $m \in \mathbb{Z}_+,$ such that $a\equiv b(\mod\, m).$ Since $a \equiv b (mod \, m), m \mid (a - b)$. That is, $\exists k \in \mathbb{Z}$ such that $a = b + km.$

1. Now, consider $a+c=(b+km)+c=(b+c)+km.$ Thus, $(a+c)-(b+c) = km$. Since $k \in \mathbb{Z}$, $m \mid ((a+c)-(b+c))$. Hence, $a + c \equiv b + c (\mod \, m)$.

2. Now, consider $ac=c(b+km)=bc+ckm$. Thus, $ac-bc = (ck)m$. Since $ck \in \mathbb{Z}$, $m \mid (ac-bc)$. Hence, $ac \equiv bc (\mod \, m)$.

3. Now, consider $a^{2} = (b+km)^{2} = b^{2} + 2bkm + k^{2}m^{2}.$ Thus  $a^{2} - b^{2} = m(2bk + k^{2}m)$. Since $(2bk + k^{2}m)\in \mathbb{Z}$,  $m \mid (a^{2}-b^{2})$. Therefore $a^{2} \equiv b^{2} (\mod \, m).$

Exercise $\PageIndex{4}$

For each of the following pairs of integers $a$ and $n.$ show that $a$ and $n$ are relatively prime,  determine multiplicative inverse of  $[a]$ in $\mathbb{Z}_n,$ and find all integers  $x$ for $ax \cong 11 (\mod \, n).$

1. $a=16, n=37.$
2. $a=19, n=35.$
3. $a=69, n=89.$

Answer

1. $$\begin{align*} 37 &= 2(16)+5 \\16&=3(5)+1. \end{align*}$$ Thus, $gcd(37,16)=1$.

$$\begin{align*} 5 &= 37 - 2(16) \\1 &= 16 - 3(5). \end{align*}$$

Now, $$\begin{align*} 1 &= 16 - 3(5) \\ &= 16 - 3(37 - 2(16))=16(7)+37(-3). \end{align*}$$ Hence, the multiplicative inverse of 16 is 7.

Now $x\equiv (7)(11)(\mod 37)\equiv (77)(\mod 37)\equiv 3(\mod 37)$. Thus, the solution set is $\{ 3+37m |m \in \mathbb{Z}\}.$

2.  $$\begin{align*}35 &= (1)19+16 \\19&=(1)16+3 \\16&=(5)3+1  .\end{align*}$$  Thus, $gcd(35,19)=1$.

Now,  $$\begin{align*} 1 &= 16 + 3(-5)\\ &=16+( - 5)(19 - 16)\\&=(6)16+(-5)19\\&=(6)(35+19(-1))+(-5)19\\&=35(6)+19(-11). \end{align*}$$

So the multiplicative inverse of $19$ is $-11 (\mod 35)\equiv 24(\mod 35).$ Thus $19x \cong 11 (\mod \, 35) \implies x \cong (24)(11)(\mod 35)\cong 19(\mod 35).$

Thus, the solution set is $\{ 19+35m |m \in \mathbb{Z}\}.$

3.  $$\begin{align*} 89 &= 1(69) + 20\\ 69 &= 3(20) + 9\\20& = 2(9) + 2\\9& = 4(2) + 1.\end{align*}$$ Thus, $gcd(69, 89) = 1.$

  $$\begin{align*}1 &= 9(1) - 4(2)\\& = 9(1) - (20(1) - 9(2))(4)\\& = 9(9) - 20(4)\\& = (69(1) - 3(20))(9) - 20(4)\\& = 69(9) - 20(31)\\& = 69(9) - (89(1) - 69(1))(31)\\& = 69(40) - 89(31).\end{align*}$$ So, the multiplicative inverse $69$ is  $40 (\mod 89).$

Now solve $69x \cong 11 (\mod \, 89) \implies x \cong (11) (40) (\mod \, 89) \cong 440 \cong 84 (\mod \, 89)$.

Thus, the solution set is $\{ 84+89m |m \in \mathbb{Z}\}.$