%p8S.tex: 
%begin macros
\baselineskip=14pt
\parskip=10pt
\magnification=\magstephalf
\parindent=0pt
\overfullrule=0in
\def\frac#1#2{{#1 \over #2}}
\def\g{\bigtriangledown}
\def\S{\cal S}
\nopagenumbers
%end macros
 

\centerline
{
\bf Solutions to the 
Attendance Quiz \# 8 for Dr. Z.'s Number Theory
Course for Sept. 30, 2013
}
\bigskip

{\bf 1.} Use the Euclidea algoithm to find  $gcd(49, 140)$ 

{\bf Sol. to 1}: Since ${\bf 140}= 2 \cdot {\bf 49} + 42$,
we have
$$
gcd(140,49)=gcd(49,42) \quad .
$$
Since ${\bf 49}= 1 \cdot 42 + 7$, so $r=7$, and we have
$$
gcd(49,42)=gcd(42,7) \quad .
$$
Since $42= 7 \cdot 6+0$, $r=0$, and the gcd is $7$.

{\bf Ans. to 1}: $gcd(140,49)=7$

{\bf 2.} Find out whether it is possible to express $1$ as a linear combination $1=m 35 +n 9$ for some integers $m$ and $n$,
and if it is, find it.

{\bf Sol.to  2}:

${\bf 35}= 3 \cdot {\bf 9} + 8$ so $r=8$ and

$$
gcd(35,9)=gcd(9,8) \quad , \quad 8= {\bf 35} - 3 \cdot {\bf 9} \quad .
$$

Now ${\bf 9}= 1 \cdot 8 +1$ so $r=1$ and
$$
gcd(9,8)=gcd(8,1) \quad , 1={\bf 9}- 1 \cdot 8
$$
$$
= {\bf 9} -({\bf 35} - 3 \cdot {\bf 9})=
4 \cdot {\bf 9} -{\bf 35} \quad .
$$

Now $8=8 \cdot 1+0$ so $r=0$ and the previous $r$ (namely $1$) is the gcd, and
$$
1=4 \cdot {\bf 9} -{\bf 35} \quad .
$$

{\bf Ans. to 2}: It is possible to express $1$ as a linear combination
of $9$ and $35$: $1= -{\bf 35}+ 4 \cdot {\bf 9}$. So $m=-1$ and $n=4$.

\end






