Practice: Divisibility, Euclidean Algorithm

Solution. $\gcd(1400,210)$$=\gcd(2^3\times 5^2\times 7,2\times 3\times 5\times 7)$$=2\times 5\times 7=70$.

Solution 1. We use the Euclidean algorithm.

$$ \begin{align*} 170051&=1000\times170+51\\ 170&=3\times 51+17\\ 51&=3\times 17+0\\ \end{align*} $$

so $\gcd(170051,170)=17$.

Solution 2. $170=17\times 2\times 5$ is the prime factorization of $170$. Clearly $170051$ is not divisible by $2$ nor by $5$ but it is divisible by $17$. Therefore $\gcd(170051,170)=17$.

Solution. The solution to the previous problem shows that: $$ \begin{align*} \underline{170051}&=1000\times\underline{170}+\underline{51}\\ \underline{170}&=3\times \underline{51}+\underline{17}\\ \end{align*} $$ To get a relationship only between $170051$, $170$, and $17$, we must eliminate $51$. We multiply the first equation by $3$, and subtract the second equation from it: $$ \begin{align*} 3\times\underline{170051}&=3000\times\underline{170}&+3\times\underline{51}&\\ -\,\,\big[\quad\qquad\underline{170}&=&3\times \underline{51}&+\underline{17}\big]\\\hline 3\times \underline{170051}-\underline{170}&=3000\times\underline{170}&&-\underline{17} \end{align*} $$ Rearranging gives $$ \underline{17}=-3\times \underline{170051}+3001\times\underline{170} $$ so we may take $m=-3$ and $n=3001$.

Notice that $(m,n)=(-3+170k,3001-170051k)$ forms an infinite family of solutions, where $k$ can be any integer.

Solution. First we run the Euclidean algorithm on $623$ and $300$: $$ \begin{align*} \underline{623}&=2\times\underline{300}+\underline{23}\\ \underline{300}&=13\times \underline{23}+\underline{1}\\ \end{align*} $$ To get a relationship only between $623$, $300$, and $1$, we must eliminate $23$. We multiply the first equation by $13$, and subtract the second equation from it: $$ \begin{align*} 13\times\underline{623}&=26\times\underline{300}&+13\times\underline{23}&\\ -\,\,\big[\quad\qquad\underline{300}&=&13\times \underline{23}&+\underline{1}\big]\\\hline 13\times \underline{623}-\underline{300}&=26\times\underline{300}&&-\underline{1} \end{align*} $$ Rearranging gives $$ \underline{1}=-13\times \underline{623}+27\times\underline{300} $$ so we may take $m=-13$ and $n=27$.

Moreover, $(m,n)=(-13+300k,27-623k)$ forms an infinite family of solutions, where $k$ can be any integer.

Solution. We use the first step of the Euclidean algorithm.

$$ 11221111=1\times 11111111+110000 $$

So $\gcd(11221111, 11111111)=\gcd(11111111, 110000)$.

We now switch to using prime factorization to find the gcd. Observe that $$110000=2^4\times5^4\times 11.$$ Clearly $2$ and $5$ are not factors of $11111111$. Finally, $11$ divides $11111111$ by long division so $$\gcd(11221111, 11111111)=\gcd(11111111, 110000)=11.$$