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

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

\begin{document}
\problemset{7}

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

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

\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}
}

\eparts

\end{problem}

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

\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}
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}

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

\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}

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

\end{document}



