\documentclass[11pt]{article}
\usepackage{handout2e}
\begin{document}
\input{macros}
\input{courseMacros}
\thispagestyle{empty}
\setlength{\parindent}{0pt}
\setlength{\parskip}{1.8ex}

\head{CS5800}{Algorithms}{Spring 2011}{26 January 2011}{1}

\begin{center}
\Large{\bf Quiz 1 (26 January 2011)}
\end{center}

{\bf 1. Answer:} Here are two possible algorithms.

Algorithm 1: 



According to Fermat's little theorem, if p is prime, then for every
$1 \le a < p$,
\begin{eqnarray*}
{a^{p-1}} & \equiv & {1 \; mod \; p}
\end{eqnarray*}


We can rewrite the problem as
\begin{eqnarray*}
{x^{y^z}} \;mod \; p & = & ({{x^{t(p-1)}} \;mod \; p})
\times({{x^{y^z \;mod \; (p-1)}} \;mod \; p})
\end{eqnarray*}

in which t is an integer representing the quotient of ${y^z}$
divided by (p-1); since
\begin{eqnarray*}
{x^{t(p-1)}} & = & {1 \; mod \; p}
\end{eqnarray*}

We then further have
\begin{eqnarray*}
{x^{y^z}} \;mod \; p & = & {{x^{y^z \;mod \; (p-1)}} \;mod \; p}
\end{eqnarray*}


So we can handle ${y^z\;mod \; (p-1)}$ first, and then calculate
${x^{y^z}}\;mod \; p$, which include two power operations, that is
power(x, power(y,z,(p-1)), p).

The total running time will be O(2${n^3}$) = O(${n^3}$).

\vspace{10 mm}

{\bf 2. Answer:}

If ${a=b}$, the claim holds;

If ${a>b}$, suppose we denote ${\gcd(a,b)=t}$, t is an integer. So
we have
\begin{eqnarray*}
{a = xt, \;\; b = yt}
\end{eqnarray*}
in which x and y are all integers. Then we have
\begin{eqnarray*}
{a+b = (x+y)t, \;\; a-b = (x-y)t}
\end{eqnarray*}

So t is a common divider of (a+b) and (a-b), which implies
\begin{eqnarray*}
{\gcd(a+b,a-b) \ge t}
\end{eqnarray*}

So we can claim
\begin{eqnarray*}
{\gcd(a+b,a-b) \ge \gcd(a,b)}
\end{eqnarray*}


\end{document}
