%BEGIN Kavita's problems
%END   Kavita's problems

%BEGIN Joe's problems
%END   Joe's problems

%BEGIN Ray's problems

%%%%%%%%%%%%%%%%  S99 ps1

\problem (\S 2.3, Exercise 34) We are given that $a \equiv b
\pmod{m}$.  This is equivalent to the assertion that $m \mid (a - b)$.
Consequently, $mc \mid (a-b)c$.  By the distributive law, $mc \mid (ac
- bc)$, which is equivalent to $ac \equiv bc \pmod{mc}$.



%END   Ray's problems

%BEGIN Ivan's problems (spring '98)
%END   Ivan's problems

%BEGIN George's problems
%END   George's problems

%BEGIN Josh's problems
%END   Josh's problems

%BEGIN Tina's problems
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% Fall 99

%% problem set 2, problem 4

\problem  \textbf{Modular Arithmetic}

Do the following problems from the Rosen textbook:

\bparts

\ppart \S 2.3, Exercise 38.

\solution{From $a \equiv b \pmod{m}$ we know that $b = a + s m$ 
for some integer $s$. Now if $d$ is a common divisor of $a$ and $m$, then
it divides the right-hand side of this equation, so it also divides $b$.
We can rewrite the equation as $a = b - s m$, and then by similar reasoning,
we see that every common divisor of $b$ and $m$ is also a divisor of $a$. This
shows that the set of common divisors of $a$ and $m$ is equal to the set of
common divisors of $b$ and $m$, so certainly gcd$(a,m)$ = gcd$(b,m)$.
}

\ppart \S 2.4 Exercise 16.

\solution{The key fact here is that $10 \equiv -1 \pmod{11}$, and so 
$10^k\equiv (-1)^k \pmod{11}$. Thus $10^k$ is congruent to $1$ if $k$ is
even and to $-1$ if $k$ is odd. Let the decimal expansion of the integer $a$
be given by $(a_{n-1}a_{n-2}\ldots a_3a_2a_1a_0)_{10}$. Thus 
$a=10^{n-1}a_{n-1}+10^{n-2}a_{n-2}+\ldots+10 a_1+a_0$. Since 
$10^k\equiv (-1)^k \pmod{11}$, we have $a\equiv \pm a_{n-1} \mp a_{n-2}+
\ldots - a_3 + a_2 - a_1 + a_0 \pmod{11}$, where signs alternate and depend
on the parity of $n$. Therefore $a\equiv 0 \pmod{11}$ if and only if 
$(a_0+a_2+a_4+\ldots)-(a_1+a_3+a_5+\ldots)$, which we obtain by collecting 
the odd and even indexed terms, is congruent to $0 \pmod{11}$.  Since being 
divisible by $11$ is being the same as being congruent to $0 \mod 11$, we
have proved that a positive integer is divisible by $11$ if and only if the 
sum of its decimal digits  in even-numbered positions minus the sum of its 
decimal digits in odd-numbered positions is divisible by $11$.
}

\eparts

%% problem set 2, problem 6

\problem \textbf{Modular Arithmetic}

Let $p(n)$ be polynomial of positive degree $d$ with integer
coefficients.  That is
\[
p(n) = a_dx^d + a_{d-1}x^{d-1} + \dots + a_1x + a_0 = \sum_{i=0}^d a_ix^i.
\]
where $d>0$, $a_d \neq 0$, and $a_i \in \integers$ for $0 \leq i \leq d$.

\bparts

\ppart

Prove that
\[
\mbox{if } m \equiv n \pmod{k}, \mbox{ then } p(m) \equiv p(n) \pmod{k},
\]
for all $m,n, k \in \integers$, $k > 1$.

\solution{By structural induction on the recursive definition of
polynomial in the previous problem.  The induction hypothesis
\[
P(p) ::= \forall m,n, k \in \integers((k > 1 \wedge m \equiv n \pmod{k})
 \implies  p(m) \equiv p(n) \pmod{k}).
\]

The base case: $p$ is a
constant polynomial.  In this case $p(m) = p(n)$ and so trivially $p(m) \equiv p(n)
\pmod{k}$, proving $P(p)$.

Induction step: suppose $p(x) = xq(x) + i$ for some $i \in \integers$ and
polynomial $q$ such that $P(q)$ holds.  We must prove $P(p)$.

So suppose $k > 1$ and $m \equiv n \pmod{k}$.  Then also $q(m) \equiv q(n)
\pmod{k}$ by induction hypothesis.   So $mq(m) \equiv nq(n) \pmod{k}$, and then
$mq(m) + i \equiv nq(n) + i \pmod{k} $.  But the lefthand side of this last
equation is $p(m)$ and the righthand side is $p(n)$, proving $P(p)$.
}

\ppart

Prove that the range of $p$ must contain an infinite number of nonprimes.

\solution{Since $d>0$ and $a_d \neq 0$, there must be an $n_0 \in
\naturals$ such that $p(n_0) = k > 1$.  So $p(n_0) \equiv 0  \pmod{k}$.
Therefore $p(n) \equiv 0 \pmod{k}$ whenever $n \equiv n_0  \pmod{k}$.  Since
there are larger and larger such $n$, there are larger and larger $\abs{p(n)}$
which are divisible by $k$ and hence are not prime.}

\ppart (Optional, best done with a Scheme program.)
Suppose $p(n) = n^2 - n + 41$.

Find the smallest natural number $n$ such that $p(n)$ is \emph{not} prime.

\solution{$n=41$.  Clearly $p(41)= 41^2 - 41 + 41$ is divisible by 41, so
is not prime.  Successive values $p(0)=41, p(1)=41, p(2)=43, p(3)=47,
\dots, p(40)= 1601$ all turn out to be prime.}

\eparts

%% problem set 5, problem 2
\problem \textbf{Modular Exponentiation} \\
Consider the following procedure to compute $a^b \bmod n$.
\begin{itemize}
\item Let $\langle b_k, b_{k-1}, \ldots, b_0\rangle$ be the binary representation of $b$.
\item Do the assignment $c := 1$.
\item Do the assignment $d := a \bmod n$.
\item Do the assignment $i := k$.
\item Repeat the following steps:
\begin{itemize}
\item if $i = 0$ \textbf{return} $d$ and halt.
\item Do the assignment $i := i-1$.
\item Do the assignment $c := 2c$.
\item Do the assignment $d := (d \cdot d) \bmod n$.
\item if $b_i = 1$
\begin{itemize}
\item Do the assignment $c := c+1$.
\item Do the assignment $d := (d \cdot a) \bmod n$.
\end{itemize}
\end{itemize}
\end{itemize}

\renewcommand{\theenumi}{(\roman{enumi})}
\begin{enumerate}
\item Model the procedure with a state machine. 
\item Notice that at the begining of every iteration 
the binary representation of $c$ 
is $\langle b_k, b_{k-1}, \ldots, b_i \rangle$.
Formulate an invariant relating $a$, $b$, $c$, $d$, $i$, and $n$,  which
holds at the top of the loop. Your invariant should imply that upon
termination, $d = a^b \bmod n$.
\item Prove that the invariant holds. 
\end{enumerate}
\renewcommand{\theenumi}{(\arabic{enumi})}
\solution{
(i). The states $Q$ can be represented as triples $(c, d, i) \subset
(\mathbb{N} \times \mathbb{N}\times \mathbb{N}$). The initial state
$q_0$ is $(1,a\bmod n,k)$.  
There are two possible transitions: if $b_{i-1} = 0$,
then $(c,d,i) \rightarrow (2c, d^2 \bmod n, i-1)$, else $(c,d,i)
\rightarrow (2c+1, d^2a \bmod n, i-1)$.  The terminating condition is
$i = 0$, and the machine outputs $d$. \\
(ii). The invariant is expressed by the predicate $P(\cdot)$, which
takes a state of the machine as its argument: \\ $P(c,d,i)$ = ``$d =
a^c \bmod n \wedge c = \langle b_k, b_{k-1}, \ldots, b_i \rangle$'' \\
Note that if $i = 0$ and $P(c,d,i)$, then $c = b$, and therefore $d =
a^b \bmod n$. \\
(iii). $P(q_0)$ holds, since $d = a \bmod n = a^1 \bmod n = a^c \bmod n$, 
and $c = 1 = b_k$
($b_k$ must be 1, as it is the most significant bit).  If $(q, q')$ is
a valid transition, we will show that $P(q) \Rightarrow P(q')$.  For
any state $q = (c,d,i)$, $q'$ will be a state following $q$ iff either
$b_i-1 = 0$ and $q' = (2c, d^2 \bmod n, i-1)$ or $b_i-1 = 1$ and $q'=(2c+1,
d^2a \bmod n, i-1)$.  If we assume that $P(q)$ holds, \emph{i.e.} $d_0
= a^{c_0} \bmod n$ and $c_0 = \langle b_k, b_{k-1}, \ldots,
b_{i_0}\rangle$ then there are two cases to consider. In the case
$b_{i_0-1} = 0$, we have $d = d_0 \cdot d_0 \equiv a^{c_0} \cdot
a^{c_0} \equiv a^{2c_0} \equiv a^c \pmod n$ and $c = 2c_0 = \langle
b_k, \ldots, b_{i_0}, 0 \rangle$, which is $P(q')$. In the case that
$b_{i_0-1} = 1$, we have $d = d_0 \cdot d_0 \cdot a \equiv a^{c_0}
\cdot a^{c_0} \cdot a \equiv a^{2c_0+1} \equiv a^c \pmod n$ and $c =
2c_0+1 = \langle b_k, \ldots, b_{i_0}, 1 \rangle$, which is $P(q')$. 
}

%END   Tina's problems
