\documentclass[12pt]{article}
\usepackage{latex-macros/course}% !! Use the macros

\renewcommand{\reading}{Course notes on number theory.}

\begin{document}
\problemset{5}

\newcommand{\beqn}{\begin{eqnarray*}}
\newcommand{\eeqn}{\end{eqnarray*}}
\newcommand{\rem}{\text{ rem }}



%Given out in class F04 cp5f, but didn't get to it.

%S04 cp5f

\begin{problem}
Suppose that one domino can cover exactly two squares on a chessboard,
either vertically or horizontally.

\bparts

\ppart Can you tile an $8 \times 8$ chessboard with 32 dominos?

\mfigure{!}{1.6in}{figures/chess1}

\solution{Yes.  Place 4 vertical dominos in each column.}

\ppart Can you tile an $8 \times 8$ chessboard with 31 dominos if
opposite corners are removed?

\mfigure{!}{1.6in}{figures/chess2}

\solution{No!  Opposing corners are the same color.  Therefore,
removing opposite corners leaves an unequal number of white and black
squares.  Since every domino covers one black square and one white
square, no tiling is possible.}

%\instatements{\newpage}

\problempart Now suppose that an assortment of squares are removed
from a chessboard.  An example is shown below.

\mfigure{!}{1.6in}{figures/chess3}

Given a truncated chessboard, show how to construct a bipartite graph
$G$ that has a perfect matching if and only if the chessboard can be
tiled with dominos.

\solution{Create a vertex for every white square and a
vertex for every black square.  Put an edge between squares that share
an edge.  (This graph is bipartite, since the coloring of the squares
defines a valid 2-coloring of the vertices.)

If a perfect matching exists in this graph, then a tiling exists: put
a domino over each pair of matched vertices.  On the other hand, if a
tiling exists, then a perfect matching exists: match squares covered
by the same domino.}

\ppart Based on this construction and Hall's theorem, can you state a
necessary and sufficient condition for a truncated chessboard to be
tilable with dominos?  Try not to mention graphs or matchings!

\solution{A board can be tiled with dominos if and only if every set
of white squares is adjacent to at least as many black squares and
vice versa.}

\end{problemparts}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Prove that $\gcd(ka, kb) = k \cdot \gcd(a, b)$ for all $k > 0$.
\end{problem}

\solution{The smallest positive value of:

\[
k \ \cdot\ (s \cdot a + t \cdot b)
\]

(which is equal to $s (k a) + t (k b) = \gcd(ka, kb)$) must be $k$
times the smallest positive value of:

\[
s \cdot a + t \cdot b
\]

(which is equal to $\gcd(a, b)$).
}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Suppose that $a \equiv b \pmod{n}$ and $n > 0$.  Prove or disprove the
following assertions:

\bparts

\ppart $a^c \equiv b^c \pmod{n}$ where $c \geq 0$

\solution{The proof is by induction on $c$ with the hypothesis that
$a^c \equiv b^c \pmod{n}$.  If $c = 0$, then the claim holds, because
$1 \equiv 1 \pmod{n}$.  Now suppose that:

\begin{eqnarray*}
a^c & \equiv & b^c \pmod{n}
\end{eqnarray*}

Multiplying both sides by $a$ gives:

\begin{eqnarray*}
a^{c+1} & \equiv & a b^c \pmod{n}
\end{eqnarray*}

Since $a \equiv b \pmod{n}$, we can replaced the $a$ on the right side
by $b$:

\begin{eqnarray*}
a^{c+1} & \equiv & b^{c+1} \pmod{n}
\end{eqnarray*}

Therefore, the claim holds by induction.
}



\ppart $c^a \equiv c^b \pmod{n}$ where $a, b, \geq 0$

\solution{The claim is false.  For example:

\begin{eqnarray}
2^0 \not\equiv 2^3 \pmod{3}
\end{eqnarray}
}

\iffalse

\ppart $a \equiv b \pmod{n}$ implies $k^a \equiv k^b \pmod{n}$ for all
$k \geq 0$.

\solution{This is false.  For example, $0 \equiv 3 \pmod{3}$, but $2^0
\not\equiv 2^3 \pmod{3}$.}
\fi


\eparts

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}
An inverse of $k$ modulo $n > 1$ is an integer, $k^{-1}$, such that
%
\[ 
k \cdot k^{-1} \equiv 1 \pmod{n}.
\]  
%
Show that $k$ has an inverse iff $\gcd(k, n) = 1$.
{\em Hint:  We saw how to prove the above when $n$ is prime.}
\end{problem}

\solution{If $\gcd(k, n) = 1$, then there exist integers $x$ and $y$
such that $k x + y n = 1$.  Therefore, $y n = 1 - k x$, which means $n
\mid (1 - k x)$ and so $k x \equiv 1 \pmod{n}$.  Let $k^{-1}$ be $x$.}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Here is a long run of composite numbers:

\[
114, 115, 116, 117, 118, 119, 120, 121, 122, 123, 124, 125, 126
\]

Prove that there exist arbitrarily long runs of composite numbers.
Consider numbers a little bigger than $n!$ where $n! = n \cdot (n - 1)
\cdots 3 \cdot 2 \cdot 1$.


\solution{

  Let $k$ be some natural number such that $1 < k \leq n$.  We know $k
  | (n! + k)$ because $k \mid n!$ and $k \mid k$. Thus, the numbers
  $n!+2, n!+3, n!+4, \ldots, n!+n$ must all be composite.  This is a
  run of $n-1$ consecutive composite numbers. Because we can
  arbitrarily choose $n$, we know arbitrarily long runs of compisite
  numbers exist.}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\begin{problem}
Take a big number, such as 37273761261.  Sum the digits, where every
other one is negated:

\beqn
3 + (-7) + 2 + (-7) + 3 + (-7) + 6 + (-1) + 2 + (-6) + 1 & = & -11
\eeqn

As it turns out, the original number is a multiple of 11 if and only
if this sum is a multiple of 11.

\bparts

\ppart Use a result from elsewhere on this problem set to show that
$10^k \equiv -1^k \pmod{11}$.

\solution{

  We know $10 \equiv -1 \pmod{11}$. From 2a, we conclude $10^k \equiv
  (-1)^k \pmod{11}$.

}

\ppart Using this fact, explain why the procedure above works.

\solution{

A number in decimal has the form:

\[
d_k \cdot 10^k + d_{k-1} \cdot 10^{k-1} + \ldots + d_1 \cdot 10 + d_0
\]

From the observation above, we know:

\begin{eqnarray*}
&& d_k \cdot 10^k + d_{k-1} \cdot 10^{k-1} + \ldots + d_1 \cdot 10 + d_0 \\
    & \equiv & d_k \cdot (-1)^k + d_{k-1} \cdot (-1)^{k-1} + \ldots \cdot + d_1 \cdot (-1)^1 + d_0 \cdot (-1)^0 \pmod{11} \\
& \equiv & d_k - d_{k-1} + \ldots \cdot - d_1 + d_0  \pmod{11} \\
\end{eqnarray*}


Note that the above assumes $k$ is even.  The case where $k$ is odd is
analogous.  Also, the procedure given in the problem may have us
reverse all signs. Because we are only checking for divisibility, this
does not matter.}

\eparts

\end{problem}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{problem}[10 points]
Let $S_k = 1^k + 2^k + \ldots + (p-1)^k$, where $p$ is an odd prime
and $k$ is a positive multiple of $p - 1$.  Use Fermat's theorem to
prove that $S_k \equiv -1 \pmod{p}$.  

\solution{Fermat's theorem says that $x^{p-1} \equiv 1 \pmod{p}$ 
when $1 \leq x \leq p - 1$.  Since $k$ is a multiple of $p-1$, 
raising each side to a suitable power proves that $x^k \equiv 1 
\pmod{p}$.  Thus: 
% 
\begin{align*} 
1^k + 2^k + \ldots + (p-1)^k 
& \equiv \underbrace{1 + 1 + \ldots + 1}_{\text{$p-1$ terms}} \pmod{p} \\ 
& \equiv p - 1 \pmod{p} \\ 
& \equiv - 1 \pmod{p} 
\end{align*} 
}

\end{problem}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%% Guiness problem

\iffalse
\begin{problem}
At one time, the Guiness Book of World Records reported that the
``greatest human calculator'' was a guy who could compute 13-th roots
of 100-digit, perfect 13-th powers.  What an curious choice of
tasks...

\bparts

\ppart Prove that $n$ and $n^{13}$ agree in the last digit for all $n
\geq 0$:

\begin{eqnarray*}
2^{13} & = & 819\underline{2} \\
3^{13} & = & 159432\underline{3} \\
       & \text{etc.}
\end{eqnarray*}

This is a bit tricky.

\insolutions{
\underline{Solution 1.}  We reason as follows:

\begin{eqnarray*}
n^{13}
    & \equiv & (n \rem 10)^{13} \pmod{10} \\
    & \equiv & (n \rem 10) \pmod{10} \\
    & \equiv & n \pmod{10}
\end{eqnarray*}

Since $(n \rem 10)$ is between 0 and 9, we can justify the second
congruence by direct calculation:

\[
\begin{array}{rcrcrcr}
0^{13} & = & 0 & \quad & 5^{13} & = & 1220703125 \\
1^{13} & = & 1 & \quad & 6^{13} & = & 13060694016 \\
2^{13} & = & 8192 & \quad & 7^{13} & = & 96889010407 \\
3^{13} & = & 1594323 & \quad & 8^{13} & = & 549755813888 \\
4^{13} & = & 67108864 & \quad & 9^{13} & = & 2541865828329
\end{array}
\]

\underline{Solution 2.} Let $n = 2^a 5^b c$, where $c$ is not
divisible by 2 or 5.  Then $c$ is relatively prime to 10.  Since
$\phi(10) = 4$, we have $c^{4} \equiv 1 \pmod{10}$ by Euler's Theorem.
Therefore, $c^{13} \equiv (c^{4})^3 \cdot c \equiv c \pmod{10}$.  Now
we can reason as follows:

\beqn
n^{13}
    & \equiv & 2^{13a} 5^{13b} c^{13} \pmod{10} \\
    & \equiv & (2^{13})^a (5^{13})^b c^{13} \pmod{10} \\
    & \equiv & 2^a 5^b c \pmod{10} \\
    & \equiv & n
\eeqn

The third step uses the observation above and the facts that $2^{13}
\equiv 2 \pmod{10}$ and $5^{13} \equiv 5 \pmod{10}$.
}

\ppart Find an integer $c > 1$ such that $n$ and $n^c$ agree in the
last {\em two digits} whenever $n$ is a positive number relatively
prime to 100.

\solution{

  Finding a $c$ such that for all $k$ relatively prime to 100, $k^c
  \equiv k \pmod{100}$ would satisfy the requirement.  From Euler's
  theorem, we know $c = \Phi(100)+1$ satisfies this equation. Thus $c =
  \Phi(100)+1 = 41$.

}

\eparts


\end{problem}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%  fall 05 -- can't use as written since don't know structural induction yet

%%%% fall 05 -- proof is really induction on #moves.  ``structural
%%%% induction'' is a misnomer here

\iffalse
\begin{problem}
Here is a {\em very, very fun} game.  We start with two distinct,
positive integers written on a blackboard.  Call them $x$ and $y$.
You and I now take turns.  (I'll let you decide who goes first.)  On
each player's turn, he or she must write a new positive integer on the
board that is the difference of two numbers that are already there.
If a player can not play, then he or she loses.

For example, suppose that 12 and 15 are on the board initially.  Your
first play must be 3, which is $15 - 12$.  Then I might play 9, which
is $12 - 3$.  Then you might play $6$, which is $15 - 9$.  Then I can
not play, so I lose.

\bparts

\ppart Show that every number on the board at the end of the game is a
multiple of $\gcd(x, y)$.

\solution{

  We use structural induction. Let $g = \gcd(x,y)$. Let the state of
  the game, $Q$ be the set of numbers currently on the board.  Let our
  inductive hypothesis, $P(Q)$ be ``Every number on the board is a
  multiple of $g$.''  For the base case, $x$ and $y$ are on the board
  initially and both are multiples of $g$. For the inductive case, let
  $Q$ be the state before a move, and $Q'$ be the state after a
  move. Then $Q'$ contains all the same elements $Q$ did, along with
  an additional element $m-n$ for some $m,n \in Q$.  We need to show
  $m-n$ is a multiple of $g$. We know $m,n$ are multiples of $g$, thus
  $m=kg$ and $n=jg$ for some integers $k,j$. Therefore, $m-n = kg-jg =
  (k-j)g$ thus $m-n$ is a multiple of $g$ as well.  }

\ppart Show that every positive multiple of $\gcd(x, y)$ up to
$\max(x, y)$ is on the board at the end of the game.

\solution{

  Assume without loss of generality that $x = \max(x,y)$.  Let $s$ be
  the smallest number on the board at the end of the game.  Write $x =
  q s + r$ where $0 \leq r < s$ as in the division algorithm.  Then $x
  - s$ must be on the board and thus so must $x - 2s$, $x - 3s$,
  \ldots, $x - (q-1)s$.  However, $r = x - q s$ can not on the board,
  since $r < s$ and $s$ is defined to be the smallest number there.
  The only explanation is that $r = 0$, which implies that $s \mid x$.
  By the same argument, $s \mid y$.  Therefore, $s$ is a common
  divisor of $x$ and $y$.  Since $s$ is a multiple of the greatest
  common divisor of $x$ and $y$ by the preceding problem part, $s$
  must actually be the greatest common divisor.  We already argued
  that $x$, $x - s$, $x - 2s$, \ldots, $x - (q-1)s$ must be on the
  board, and these are all the positive multiples of $\gcd(x, y)$ up
  to $\max(x, y)$.

}

\ppart Describe a strategy that lets you win this game every time.

\solution{

  Assume without loss of generality that $x = \max(x,y)$. Structural
  induction will easily show all elements on the board are at most
  $x$, so we show no elements larger than $x$ may be on the board. The
  first part shows no elements that are not multiples of $\gcd(x,y)$
  may be on the board and the second part shows all multiples of
  $gcd(x,y)$ up to $x$ are on the board. Thus, for each game, we know
  \emph{exactly} how many values will be placed on the board before
  the game ends. Thus, if there will be an odd number of values
  eventually placed ($x$ is an odd multiple of $\gcd(x,y)$), decide to
  go first. Otherwise, decide to go second.

}

\eparts

\end{problem}
\fi

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{document}
