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}\}.\)