\problemdata     
{S01-PS3-1}           
{induction, proofs}              
{}              
{S01-PS3} 		
{S01 Karger}        	

\begin{problem}  \label{ax+by:induct}
Suppose $a,b \in \naturals$ and $a>0$.  Prove by induction on $a$ that for
all $b\leq a$, there are $x,y \in \integers$ such that $ax+by= \gcd
(a,b)$.

\solution{
The proof is actually by strong induction.

{\bf Inductive Hypothesis:} 
\[P(a)::= \forall b\le a \exists x,y\in Z(\gcd(a,b)=a x +b y).
\]

\begin{proof}

{\bf Base Case:} $a=1$.  So $b=0$ or $b=1$.  In either case,
$\gcd(a,b)=a$, so letting $x=1$, $y=0$, proves $P(a)$.

{\bf Inductive Step:} We want to prove $P(a+1)$ assuming $P(n)$ holds for
all $n \leq a$.

If $b=0$ or $b=a+1$, then $P(a+1)$ holds as in the base case, so we may
assume $0<b\leq a$.  Since $b>0$, we can find the quotient, $q$, and
remainder, $r$, of $a+1$ divided by $b$, namely, $a+1 =qb + r$ for some
$q,r \in \integers, 0 \leq r < b \leq a$.

Now we know from the discussion in the text of Euclid's GCD algorithm that
$\gcd(b,r)=\gcd(a+1,b)$.  By induction hypothesis, $P(b)$, there are
integers $x',y'$ such that $gcd(b,r)=b x' + r y'$.  Therefore
\begin{eqnarray*}
\gcd(a+1,b) & = & \gcd(b,r)\\
     & = & b x' + r y'\\
& = & b x' + ((a+1)-q b) y'\\
& = & (a+1) y' + b (x' - q y').
\end{eqnarray*}
So letting $x=y'$ and $y = (x' - q y')$ proves $P(a+1)$.
\end{proof}
}

\end{problem}
