Chapter 1.8, Problem 6E

(a)

To determine

To find: $d=\gcd (a,b),\text{and }x,y\in 𑨀$ such that $d=ax+by$

Answer to Problem 6E

  $\begin{array}{l}d=1\\ x=7\\ y=-6\end{array}$

Explanation of Solution

Given information:

  $a=13,b=15$

Concept used:

Euclid’s Algorithm says that, if $a,b\in \mathbb{N}$ with $a\le b$ then $\gcd (a,b)=r_k$ where $q_1,q_2,\mathrm{...},q_k$ and $r_1,r_2,\mathrm{...}{r}_k$ are the positive integers such that

  $\begin{array}{l}a>r_1>r_2,\mathrm{...}>r_k>r_{k+1}=0\\ b=a{q}_1+r_1\\ a=r_1{q}_2+r_2\\ r_1=r_2{q}_3+r_3\\ ⋮\\ r_{k-3}=r_{k-2}{q}_{k-1}+r_{k-1}\\ ⋮\\ r_k=r_{k-1}{q}_{k+1}\end{array}$

Calculation:

From Euclid’s Algorithm:

  $\begin{array}{l}15=13(1)+2\text{ (1)}\\ 13=2(6)+1\text{ (2)}\\ 2=1(2)\\ \Rightarrow \gcd (13,15)=1\end{array}$

To find $x\text{ and }y$ , go backward:

  $\begin{array}{l}1=\gcd (13,15)\\ (2)\Rightarrow 1=13-2(6)\\ (1)\Rightarrow 1=13-(15-13)(6)\\ \Rightarrow 1=13(7)+15(-6)\\ \Rightarrow x=7,y=-6\end{array}$

(b)

To determine

To find: $d=\gcd (a,b),\text{and }x,y\in 𑨀$ such that $d=ax+by$

Answer to Problem 6E

  $\begin{array}{l}d=2\\ x=5\\ y=-4\end{array}$

Explanation of Solution

Given information:

  $a=26,b=32$

Calculation:

From Euclid’s Algorithm:

  $\begin{array}{l}32=26(1)+6\text{ (1)}\\ 26=6(4)+2\text{ (2)}\\ 6=2(3)\\ \Rightarrow \gcd (26,32)=2\end{array}$

To find $x\text{ and }y$ , go backward:

  $\begin{array}{l}2=\gcd (26,32)\\ (2)\Rightarrow 2=26-6(4)\\ (1)\Rightarrow 2=26-(32-26)(4)\\ \Rightarrow 2=26(5)+32(-4)\\ \Rightarrow x=5,y=-4\end{array}$

(c)

To determine

To find: $d=\gcd (a,b),\text{and }x,y\in 𑨀$ such that $d=ax+by$

Answer to Problem 6E

  $\begin{array}{l}d=3\\ x=-3\\ y=1\end{array}$

Explanation of Solution

Given information:

  $a=9,b=30$

Calculation:

From Euclid’s Algorithm:

  $\begin{array}{l}30=9(3)+3\text{ (1)}\\ 9=3(3)\text{ (2)}\\ \Rightarrow \gcd (30,9)=3\end{array}$

To find $x\text{ and }y$ , go backward:

  $\begin{array}{l}3=\gcd (9,30)\\ (1)\Rightarrow 3=9(-3)+30(1)\\ \Rightarrow x=-3,y=1\end{array}$

(d)

To determine

To find: $d=\gcd (a,b),\text{and }x,y\in 𑨀$ such that $d=ax+by$

Answer to Problem 6E

  $\begin{array}{l}d=1\\ x=-19\\ y=1\end{array}$

Explanation of Solution

Given information:

  $a=77,b=4$

Calculation:

From Euclid’s Algorithm:

  $\begin{array}{l}77=4(19)+1\text{ (1)}\\ 4=4(1)\text{ (2)}\\ \Rightarrow \gcd (77,4)=1\end{array}$

To find $x\text{ and }y$ , go backward:

  $\begin{array}{l}1=\gcd (77,4)\\ (1)\Rightarrow 1=4(-19)+77(1)\\ \Rightarrow x=-19,y=1\end{array}$

(e)

To determine

To find: $d=\gcd (a,b),\text{and }x,y\in 𑨀$ such that $d=ax+by$

Answer to Problem 6E

  $\begin{array}{l}d=2\\ x=17\\ y=-1\end{array}$

Explanation of Solution

Given information:

  $a=100,b=6$

Calculation:

From Euclid’s Algorithm:

  $\begin{array}{l}100=6(16)+4\text{ (1)}\\ 6=4(1)+2\text{ (2)}\\ 4=2(2)\\ \Rightarrow \gcd (6,100)=2\end{array}$

To find $x\text{ and }y$ , go backward:

  $\begin{array}{l}2=\gcd (6,100)\\ (2)\Rightarrow 2=6-4(1)\\ (1)\Rightarrow 2=6-(100-6(16))\\ \Rightarrow 2=6(17)+100(-1)\\ \Rightarrow x=17,y=-1\end{array}$

(f)

To determine

To find: $d=\gcd (a,b),\text{and }x,y\in 𑨀$ such that $d=ax+by$

Answer to Problem 6E

  $\begin{array}{l}d=2\\ x=-1\\ y=1\end{array}$

Explanation of Solution

Given information:

  $a=48,b=50$

Calculation:

From Euclid’s Algorithm:

  $\begin{array}{l}50=48(1)+2\text{ (1)}\\ 48=2(24)\text{ (2)}\\ \Rightarrow \gcd (48,50)=2\end{array}$

To find $x\text{ and }y$ , go backward:

  $\begin{array}{l}2=\gcd (48,50)\\ (1)\Rightarrow 2=48(-1)+50(1)\\ \Rightarrow x=-1,y=1\end{array}$