
\subsection{GCD}

\lstset{language=C++}
\begin{lstlisting}
int gcd (int b, int s) {
    int r;
    while ((r = (b % s))) {
        b = s;
        s = r;
    }
    return s;
}
\end{lstlisting}

Euler's totient, $\varphi (n)$, gives the number of positive
integers less than or equal to $n$ that are coprime to $n$ (i.e.,
$n$ and $m$ are coprime if \texttt{gcd (n, m) = 1}).

\begin{displaymath}
\phi(n) = n \prod_{p|n} \left(1 - \frac{1}{p} \right) \ \ \ 
    \mathrm{sum\ over\ primes\ } p\  \mathrm{dividing\ } n
\end{displaymath}

$$G(n) + n = g(n) = \sum_{j=1}^n \mathrm{gcd} (j,n) = n \sum_{d|n} \frac{\phi(d)}{d}$$
$$G(a*b) = (a+G(a))*(b+G(b))-(a*b)$$

\bigskip
Quadratic formula is $\frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$

%%% Local Variables:
%%% mode: latex
%%% TeX-master: "../ref-doc"
%%% End:
