%  Homework assignment 4 solutions
%  21-110: Problem Solving in Recreational Mathematics, spring 2010
%  Assigned: Friday, February 19, 2010. Due: Friday, February 26, 2010.
%  Brian Kell <bkell@cmu.edu>

\pdfpagewidth=8.5truein \pdfpageheight=11truein
\hsize=6truein \vsize=9truein
\pdfhorigin=1.25truein \pdfvorigin=1truein

% MetaPost stuff
\input supp-pdf
\def\fig#1{\convertMPtoPDF{#1}{1}{1}}
\def\midfig#1{{%
	\setbox0=\hbox{\fig{#1}}%
	\dimen0=0.5\ht0%
	\advance\dimen0 by-0.3\ht\strutbox
	\lower\dimen0\box0%
}}

% AMSFonts
\input amssym.tex

\font\titlefont=cmbx12
\font\smfont=cmr8

\headline={\hfil}
\footline={\hfil Page~\folio\hfil}
\topskip=20pt plus2pt

\newcount\pno  \pno=0
\def\problem{\goodbreak\advance\pno by1 \noindent{\bf Problem~\the\pno.} }
\def\problemno#1. {\goodbreak\noindent{\bf Problem~\hbox{#1}.} }
\def\noskiphint#1\par{\nobreak{\hyphenpenalty=10000\noindent{\it Hint:\/}\enspace#1\par}}
\def\hint#1\par{\nobreak\medskip\noskiphint#1\par}
\def\itemhint#1\par{\nobreak\smallskip\item{}{\it Hint:\/}\enspace#1\par}
\def\solution{\nobreak\medskip\noindent{\bf Solution.} }
\def\part#1{\goodbreak\medskip\indent\llap{#1\enspace}\ignorespaces}
\def\firstpart#1{\nobreak\medskip\indent\llap{#1\enspace}\ignorespaces}

% Pilfered from an example on page 106 of the TeXbook
\def\qed{{\unskip\nobreak\hfil\penalty50
	\hskip1em\hbox{}\nobreak\hfil\hbox{\vrule\vbox to6pt{\hrule\hbox to5.2pt{\hss}\vfil\hrule}\vrule}
	\parfillskip=0pt \finalhyphendemerits=0 \par}}

\def\ipmod#1{\;({\rm mod}\,\,#1)}  % looks better inline than \pmod does
\def\clap#1{\hbox to 0pt{\hss$\scriptstyle{#1}$\hss}}
\def\lcm{\mathop{\rm lcm}}  \def\gcd{\mathop{\rm gcd}}

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

\centerline{\titlefont 21-110: Problem Solving in Recreational Mathematics}
\smallskip
\centerline{\bf Homework assignment~4 solutions}

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Recall that $n!$, read ``$n$~factorial,'' is the number
$n\times(n-1)\times(n-2)\times\cdots\times3\times2\times1$. For example,
$5!=5\times4\times3\times2\times1=120$. The number~$110!$~ends with a bunch of
zeroes. How many?

\solution A zero at the end of a number is a consequence of a factor of~10. For
example, the number~70 ends with one zero because it has one factor of~10
($70=7\times10$), and the number~12,000 ends with three zeroes because it has
three factors of~10 ($12{,}000=12\times10\times10\times10$). So to count the
number of zeroes at the end of~$110!$ we need to count the number of factors
of~10 in~$110!$.

One factor of~10 is the same as one factor of~2 and one factor of~5, since 2
and~5 are the prime factors of~10. We can see how many factors of~2 and factors
of~5 a number has by looking at the prime factorization of the number.

Let's return to the examples above. The prime factorization of~70 is
$2\times5\times7$. The~2 and the~5 combine to make a factor of~10, so we can
tell from the prime factorization that 70 has one zero at the end. Similarly,
the prime factorization of~12,000 is
$2\times2\times2\times2\times2\times3\times5\times5\times5$, or
$2^5\times3\times5^3$. The three factors of~5 combine with three of the five
factors of~2 to form three factors of~10 in~12,000, giving us three zeroes at
the end. (The other two factors of~2 are ``leftovers,'' because there are no
more factors of~5 for them to combine with.)

In a factorial the factors of~2 will always outnumber the factors of~5, since
every even number in the product
$n\times(n-1)\times(n-2)\times\cdots\times3\times2\times1$ will contribute at
least one factor of~2, whereas factors of~5 are contributed only by multiples
of~5 (which occur more rarely). This means that we can count the factors of~10
in a factorial by counting how many factors of~5 it has (because there will
always be enough factors of~2 to combine with them).

In the number~$110!$, every multiple of~5 from 5 up to~110 contributes one
factor of~5. This gives us $110/5=22$~factors of~5, which will give us
22~zeroes at the end of~$110!$.

But there are a few more factors of~5. The number~25 will contribute not one
but two factors of~5 to the number~$110!$, as will all multiples of~25 (50,~75,
and~100). So there are four additional factors of~5, giving us four more zeroes
at the end of~$110!$. (If, instead of~$110!$, we had been considering the
number~$150!$, say, we would also need to consider the fact that $5^3$, or~125,
will contribute {\it three\/} factors of~5, and so on.)

In total, then, the number~$110!$ ends with 26~zeroes. \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem What is the remainder when $3^{21{,}110}$ is divided by~7?

\solution There are at least three ways to solve this problem. Perhaps the
simplest is to start looking at small powers of~3 and their remainders when
divided by~7, in the hopes of finding a pattern.
$$\vbox{\offinterlineskip
\halign{\enspace\hfil\strut#\hfil\enspace&\vrule#&
	\enspace\hfil\strut#\hfil\enspace&&\hfil\strut#\hfil\enspace\cr
$n$&&1&2&3&4&5&6&7&8&9&10&11&12&13&$\ldots$\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$3^n$&&3&9&27&81&243&729&2,187&6,561&19,683&59,049&177,147&531,441&1,594,323&$\ldots$\cr
rem.&&3&2&6&4&5&1&3&2&6&4&5&1&3&$\ldots$\cr
}}$$
We see that these remainders repeat 3,~2, 6, 4, 5,~1 over and over, in other
words, every sixth power of~3. The greatest multiple of~6 less than 21,110 is
21,108, which is $6\times3{,}518$. So if we were to continue this table all the
way to~$3^{21{,}110}$, we would have 3,518~repetitions of the sequence 3,~2, 6,
4, 5,~1, which would bring us up to~$3^{21{,}108}$; two more powers of~3 would
give us~$3^{21{,}110}$ and would bring us two numbers into the next repetition
of the sequence. The second number of the repeating sequence is~2, so the
remainder when $3^{21{,}110}$ is divided by~7 is~2.

The second approach is similar, but uses modular arithmetic to simplify the
calculations. Since we are interested in remainders when numbers are divided
by~7, we can do all of our calculations modulo~7 and work only with remainders
rather than having to juggle big numbers like 1,594,323. Obviously
$3^1\equiv3\ipmod7$. Next we multiply $3^1$ by~3 and get $3\times3=9$, which
has a remainder of~2 when divided by~7; so $3^2\equiv2\ipmod7$. To find~$3^3$,
rather than multiplying 9 by~3, we can simply multiply this remainder~2 by~3 to
get $3^3=3^2\times3\equiv2\times3=6\ipmod7$. For~$3^4$, we multiply this
remainder~6 by~3 to get $3^4=3^3\times3\equiv6\times3=18\equiv4\ipmod7$.
Continuing in this way, we can build up a table as before, calculating only
with remainders:
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&\vrule#&
	\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
$n$&&1&2&3&4&5&6&7&$\ldots$\cr
\omit&height2pt\cr
\noalign{\hrule}
\omit&height2pt\cr
$3^n\ipmod7$&&3&2&6&4&5&1&3&$\ldots$\cr
}}$$
We don't have to extend the table as far to see the pattern this time, because
we know (from the way we are calculating these remainders) that the pattern
will repeat once we've come back to where we started. For example, to
find~$3^8$, we multiply~$3^7$ (which is congruent to~3 modulo~7) by~3 to get
$3^8=3^7\times3\equiv3\times3=9\equiv2\ipmod7$, which is the same as~$3^2$.

Now that we have found the pattern, we can use the same reasoning as we used in
the first approach to see that the pattern of remainders will fully repeat
3,518~times, and go two numbers further, giving us a remainder of~2 when
$3^{21{,}110}$ is divided by~7.

The third approach is a further refinement. We begin this time by finding the
smallest positive integer power of~3 that is congruent to~1 modulo~7. So we
start with~$3^1$ and then find $3^2$,~$3^3$, and so on (using modular
arithmetic) until we get a remainder of~1. From what we have done before, we
know that 6 is the smallest such power of~3, because $3^6\equiv1\ipmod7$. We
can use this fact to compute the remainder when $3^{21{,}110}$ is divided by~7
by using modular arithmetic (modulo~7) and grouping the factors of~3 into
clusters of six, each of which is congruent to~1 modulo~7:
$$\def\six{(3{\times}3{\times}3{\times}3{\times}3{\times}3)}
\eqalign{
	3^{21{,}110}
	&=\underbrace{\strut3\times3\times3\times\cdots\times3}_{\rm21{,}110\;factors}\cr
	&=\underbrace{\strut\six\times\six\times\cdots\times\six}
		_{\rm3{,}518\;of\;these\;clusters}
		{}\times{}\underbrace{\strut3\times3}_{\clap{\scriptstyle\rm leftovers}}\cr
	&\equiv\underbrace{\strut1\times1\times\cdots\times1}_{\rm3{,}518\;factors}
		{}\times3\times3\pmod7\cr
	&=9\cr
	&\equiv2\pmod7.\cr
}$$
Any way we do it, we see that $3^{21{,}110}$ yields a remainder of~2 when it is
divided by~7. \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem In class we showed that the least common multiple of 10 and~12 is
$\lcm(10,12)=60$ and the greatest common divisor of 10 and~12 is
$\gcd(10,12)=2$. We then observed that $10\times12=120$ and $60\times2=120$.
Does this always happen? In other words, is it true that for {\it every\/}
possible pair of positive integers $a$ and~$b$,
$$a\cdot b=\lcm(a,b)\cdot\gcd(a,b)?$$
If so, explain why. If not, give a counterexample (that~is, give two positive
integers $a$ and~$b$ for which this statement is false).

\solution This equality is always true, for every possible pair of positive
integers $a$ and~$b$. To see why this is, we consider the prime factorizations
of $a$ and~$b$.

Suppose $p$ is a prime number that is a factor of $a$ or~$b$ (or both). Suppose
further that $a$ has exactly $m$~factors of~$p$ (that~is, $p^m\mid a$ but
$p^{m+1}\nmid a$) and that $b$ has exactly $n$~factors of~$p$. (It is possible
that one of $m$ or~$n$ is zero, if $p$ is not a factor of both $a$ and~$b$.)
Then their product~$ab$ has exactly $m+n$~factors of~$p$.

How many factors of~$p$ are in $\lcm(a,b)$ and $\gcd(a,b)$? To find the
greatest common divisor of $a$ and~$b$, we take as many factors of~$p$ as
possible without exceeding $m$ or~$n$. In other words, if $m<n$ then
$\gcd(a,b)$ has exactly $m$~factors of~$p$, and if $m\ge n$ then $\gcd(a,b)$
has exactly $n$~factors of~$p$.

Similarly, to find the least common multiple of $a$ and~$b$, we take the
smallest number of factors of~$p$ that is at least as large as both $a$
and~$b$. So if $m<n$ then $\lcm(a,b)$ has exactly $n$~factors of~$p$, and if
$m\ge n$ then $\lcm(a,b)$ has exactly $m$~factors of~$p$.

Therefore we have two cases. In the first case $m$~is less than~$n$, so
$\gcd(a,b)$ has exactly $m$~factors of~$p$, and $\lcm(a,b)$ has exactly
$n$~factors of~$p$. Then the product $\lcm(a,b)\cdot\gcd(a,b)$ has exactly
$m+n$~factors of~$p$. In the second case $m$~is greater than or equal to~$n$,
so $\gcd(a,b)$ has exactly $n$~factors of~$p$, and $\lcm(a,b)$ has exactly
$m$~factors of~$p$, meaning that the product $\lcm(a,b)\cdot\gcd(a,b)$ again
has exactly $m+n$~factors of~$p$.

Hence, in any case, $\lcm(a,b)\cdot\gcd(a,b)$ has exactly as many factors
of~$p$ as $ab$~does. Since $p$ represents an arbitrary prime factor, this
argument must remain true for {\it all\/} the prime factors of either $a$
or~$b$. Therefore the prime factorization of $\lcm(a,b)\cdot\gcd(a,b)$ is
exactly the same as the prime factorization of~$ab$, which means that $a\cdot
b=\lcm(a,b)\cdot\gcd(a,b)$. \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem A long hallway has 100~light bulbs, numbered 1 through~100. Each light
bulb has a pull string; when the string is pulled, the light bulb turns on if
it was off, and turns off if it was on. All of the light bulbs are initially
off.

One person walks into the hall, pulls every string, and walks out. Then a
second person enters, pulls the strings of light bulbs 2,~4, 6, 8, and so on,
and leaves. Next, a third person comes in, pulls strings 3,~6, 9, 12, and so
on, and exits. This pattern continues until 100~people have walked in, pulled
some of the strings, and walked out. (Note that the 100th person will pull only
string~100.)

After all 100~people have done this, which light bulbs are on? More
importantly, why?

\solution The first observation we make is that, at the end, the light bulbs
that are on are precisely those light bulbs whose strings were pulled an
{\it odd\/} number of times. This is a useful observation to make, even though
it doesn't immediately go very far in telling us which of the numbered light
bulbs will be on.

From some experimentation (perhaps considering only the first 25~light bulbs
rather than all~100), we see that the light bulbs that are on at the end are
numbers 1,~4, 9, 16, 25, and so on. This leads us to conjecture that it is the
perfect squares that will be on.

Let's consider a given string (say, the string for light bulb~12). Which people
pull this string? Well, string~12 is pulled by people 1,~2, 3, 4, 6, and~12.
Aha! Since each person pulls the strings that are multiples of his or her
number, each string will be pulled once for each of its divisors. Since 12 has
six divisors (including 12~itself), the string for light bulb~12 will be pulled
six times. Since 6 is an even number, this means that light bulb~12 will be
off.

From the observation we made at the start, we see that our conjecture is
equivalent to the following statement:
$$\displaylines{
	\hbox{Every perfect square has an odd number of divisors;}\cr
	\hbox{every number that is not a perfect square has an even number of divisors.}\cr
}$$
If we can establish that this statement is true, we will have an explanation
for the claim that the light bulbs that are on are precisely those whose
numbers are perfect squares.

Let's begin with the claim that every number that is not a perfect square has
an even number of divisors. (Let's continue using 12 as our example.) There is
a trick that is often useful when trying to show that some collection has an
even number of things: Try to find a way to pair them up. Is there a way that
we can pair up the divisors of~12? After some thought, we see that there is
indeed a very natural way to do this. For every divisor~$n$ of~12, the
number~$12/n$ is also a divisor of~12. So the divisors 1 and~12 can be paired
up, because $1\times12=12$; 2~and~6 can be paired up, because $2\times6=12$;
and 3~and~4 can be paired up, because $3\times4=12$. Since we are able to pair
up all of the divisors of~12 with no leftovers, we see that 12 has an even
number of divisors. It seems that this trick will work with the divisors of any
positive integer, which would show that every positive integer has an even
number of divisors.

But wait. We are also claiming that every perfect square has an odd number of
divisors, so this pairing-up trick must fail for the divisors of a perfect
square. Why? Let's consider 16 as an example. The divisors of~16 are 1,~2, 4,
8, and~16. If we try to pair them up, we put 1 with~16, because $1\times16=16$;
we put 2 with~8, because $2\times8=16$; and we put 4 with---oops. We would like
to put 4 with~4 (because $4\times4=16$), but then we aren't {\it pairing\/} it
with anything. This is the reason a perfect square has an odd number of
divisors: each of the divisors pairs up with some other divisor, {\it except\/}
the square root. Since we have one divisor left over after this pairing-up, a
perfect square must have an odd number of divisors.

Therefore, our final answer (and justification) goes like this: Every positive
integer~$a$ that is not a perfect square has an even number of divisors,
because every divisor~$n$ of~$a$ can be paired with the divisor~$a/n$, which is
an integer (since $n\mid a$) and is different from~$n$ (since $a$ is not a
perfect square). On the other hand, every perfect square~$b$ has an odd number
of divisors, because every divisor of~$b$ other than the square root can be
paired with another divisor of~$b$ as above, but the square root~$\sqrt b$ is
left over at the end.

Now, the string for a given light bulb will be pulled once for each of the
divisors of the number on the bulb, and at the end a light bulb will be on if
and only~if its string was pulled an odd number of times. Therefore, the light
bulbs that are on after all 100~people have gone through the hall are precisely
those bulbs marked with a perfect square. \qed

\nobreak\medskip

\noindent[See also ``Odd Divisors'' on page~184 of {\it Thinking
Mathematically}.]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Consider the polynomial function $f(x)=x^2+x+41$. Compute the values
$f(0)$,~$f(1)$, $f(2)$, $f(3)$, \dots,~$f(20)$. What can you say about the
{\it primality\/} of these numbers? (That~is, are they prime numbers or not?)
Does this pattern continue forever? Why or why not?

\nobreak\medskip

\noindent[This interesting property of this polynomial was discovered by the
Swiss mathematician Leonhard Euler (pronounced ``Oiler'') in~1772.]

\solution The values of~$f(x)$ for the first 40~nonnegative integer values
of~$x$ are given below.
$$\vcenter{\openup1\jot
\halign{\hfil$#{}$&&\hfil$#$, prime.&\qquad\hfil$#{}$\cr
f(0)=&41&f(10)=&151&f(20)=&461&f(30)=&971\cr
f(1)=&43&f(11)=&173&f(21)=&503&f(31)=&1033\cr
f(2)=&47&f(12)=&197&f(22)=&547&f(32)=&1097\cr
f(3)=&53&f(13)=&223&f(23)=&593&f(33)=&1163\cr
f(4)=&61&f(14)=&251&f(24)=&641&f(34)=&1231\cr
f(5)=&71&f(15)=&281&f(25)=&691&f(35)=&1301\cr
f(6)=&83&f(16)=&313&f(26)=&743&f(36)=&1373\cr
f(7)=&97&f(17)=&347&f(27)=&797&f(37)=&1447\cr
f(8)=&113&f(18)=&383&f(28)=&853&f(38)=&1523\cr
f(9)=&131&f(19)=&421&f(29)=&911&f(39)=&1601\cr
}}$$
Surely, with this much evidence, it seems a safe bet that $f(x)$ is prime for
all nonnegative integer values of~$x$. But this is not the case! Let's go just
two steps further and consider $f(41)$:
$$f(41)=41^2+41+41=41(41+1+1)=41\times43,$$
so $f(41)$ is composite. Therefore the answer to the question is no; the
pattern continues for quite a while, but not forever. In fact there are
infinitely many values of~$x$ for which $f(x)$ is composite (any multiple
of~41, for example).

It turns out that $f(40)$ is also composite, although this takes some cleverer
algebraic factoring to see:
$$f(40)=40^2+40+41=40^2+40+40+1=40^2+2(40)+1=(40+1)^2=41^2=41\times41.\eqno\hbox{\qed}$$

\nobreak\medskip

\noindent[This is a famous example of a false pattern that strongly appears to
be true if only the first few cases are investigated. Examples such as these
emphasize the importance of mathematical {\it proof}, rather than simply strong
evidence, to establish that conjectures are true.]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Use the definition of divisibility to prove the following statement
about integers $a$,~$b$, $c$, $x$, and~$y$, where $a\not=0$: If $a\mid b$ and
$a\mid c$, then $a\mid(bx+cy)$.

\solution Since $a\mid b$, there exists an integer~$d$ such that $b=ad$ (by the
definition of divisibility). Likewise, since $a\mid c$, there exists an
integer~$e$ (probably different from~$d$) such that $c=ae$. Therefore,
$$bx+cy=(ad)x+(ae)y=a(dx)+a(ey)=a(dx+ey).$$
Since $dx+ey$ is an integer, we see from the definition of divisibility that
$a\mid(bx+cy)$. \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (``The Cashier's Error,'' from {\it The Moscow Puzzles\/} by Boris~A.
Kordemsky, edited by Martin Gardner.)\enspace The customer said to the
cashier: ``I have 2~packages of lard at 9~cents; 2~cakes of soap at 27~cents;
and 3~packages of sugar and 6~pastries, but I don't remember the prices of the
sugar and pastries.''

``That will be \$2.92.''

The customer said: ``You have made a mistake.''

The cashier checked again and agreed.

How did the customer spot the error?

\solution The prices of the lard and soap are both multiples of 3~cents, so the
total price of the lard and soap is also a multiple of 3~cents. The quantities
of the sugar and pastries are both multiples of~3, so the total price of the
sugar and pastries must be a multiple of 3~cents. Therefore, the total of
everything at the end should also be a multiple of 3~cents. But it's not,
because 292~is not a multiple of~3 (using the rule for divisibility by~3:
$2+9+2=13$ is not a multiple of~3, so neither is~292). Therefore, the cashier
must have made an error. \qed

\nobreak\medskip

\noindent[This solution uses the ``two out of three theorem,'' Theorem~4.1(iii)
on page~105 of {\it Problem Solving Through Recreational Mathematics}, three
times.]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Use the Euclidean algorithm to find the greatest common divisor of
11,238,781 and 8,476,873.

\solution The process of the Euclidean algorithm is presented below in a table,
in the same way as the example in the ``Additional topics in number theory''
handout (available online at
{\tt http://www.math.cmu.edu\slash\char126bkell\slash21110-2010s\slash
numbers.html}).

$$\vbox{\offinterlineskip
\def\spaceamt{height1pt}
\def\rulespace{\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt\cr}
\def\tablerule{\rulespace\noalign{\hrule}\rulespace}
\hrule
\halign{&\vrule#&\quad\hfil\strut#\hfil\quad\cr
\rulespace
&&&$c$&&$d$&&$r$&\cr\tablerule
&Step~1&&11,238,781&&8,476,873&&&\cr\tablerule
&Step~2&&11,238,781&&8,476,873&&2,761,908&\cr\tablerule
&Step~4&&8,476,873&&2,761,908&&&\cr\tablerule
&Step~2&&8,476,873&&2,761,908&&191,149&\cr\tablerule
&Step~4&&2,761,908&&191,149&&&\cr\tablerule
&Step~2&&2,761,908&&191,149&&85,822&\cr\tablerule
&Step~4&&191,149&&85,822&&&\cr\tablerule
&Step~2&&191,149&&85,822&&19,505&\cr\tablerule
&Step~4&&85,822&&19,505&&&\cr\tablerule
&Step~2&&85,822&&19,505&&7,802&\cr\tablerule
&Step~4&&19,505&&7,802&&&\cr\tablerule
&Step~2&&19,505&&7,802&&3,901&\cr\tablerule
&Step~4&&7,802&&3,901&&&\cr\tablerule
&Step~2&&7,802&&3,901&&0&\cr
\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt&\omit&\spaceamt\cr
\noalign{\hrule}
\spaceamt&\omit&\spaceamt&\omit&\omit&\omit&\omit&\omit&\spaceamt\cr
&Step~3&&\multispan5\quad\hfil$\gcd(11{,}238{,}781,\,8{,}476{,}873)=3{,}901$\hfil\quad&\cr
\spaceamt&\omit&\spaceamt&\omit&\omit&\omit&\omit&\omit&\spaceamt\cr}\hrule}$$

\noindent Therefore the greatest common divisor of 11,238,781 and 8,476,873
is~3,901. \qed

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem Investigate the powers of~2 (1,~2, 4, 8, 16,~$\dots$) and classify
them as abundant, deficient, or perfect. Can you make a conjecture about these
numbers? (Make your conjecture as specific as you can.)

\solution A table listing the first eight powers of~2, their proper divisors,
the sums of their proper divisors, and their classification as abundant,
deficient, or perfect is given below.
$$\vbox{\offinterlineskip
\halign{\quad\hfil\strut#\hfil\quad&&\hfil\strut#\hfil\quad\cr
Number&Proper divisors&Sum&Classification\cr
\noalign{\vskip2pt\hrule\vskip2pt}
1&\it(none)&0&deficient\cr
2&1&1&deficient\cr
4&1, 2&3&deficient\cr
8&1, 2, 4&7&deficient\cr
16&1, 2, 4, 8&15&deficient\cr
32&1, 2, 4, 8, 16&31&deficient\cr
64&1, 2, 4, 8, 16, 32&63&deficient\cr
128&1, 2, 4, 8, 16, 32, 64&127&deficient\cr
}}$$

\noindent From this table we can make several conjectures.

{\nobreak\medskip\narrower

\proclaim Conjecture~1. The set of proper divisors of a power of~2 is the set
of all smaller powers of~2.

\proclaim Conjecture~2. The sum of the proper divisors of a power of~2 is
always one less than the power of~2 itself.

\proclaim Conjecture~3. Every power of~2 is deficient by exactly~1.

}

\noindent (Note that Conjecture~3 is just a rewording of Conjecture~2.) \qed

\nobreak\medskip

\noindent[In fact all three of these conjectures are true. Conjecture~1 can be
proved by considering the prime factorization of a power of~2 (can you see
how?). One way to prove Conjecture~2 is by using a technique called
{\it mathematical induction}, which we may talk about later in the course. And,
of course, if Conjecture~2 is true then Conjecture~3 must be true also.]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem (From {\it Mathematical Recreations and Essays\/} by W.\thinspace W.
Rouse Ball and H.\thinspace S.\thinspace M. Coxeter.)\enspace Prove that every
sum of two consecutive odd primes is the product of three integers all greater
than~1. For example, $7+11=2\times3\times3$, and $11+13=2\times3\times4$.

\nobreak\medskip

\solution Let $p$ and~$q$ be two consecutive odd primes. (In other words,
$p$~and~$q$ are both odd integers, they are both primes, and every integer
strictly between $p$ and~$q$ is composite.) Our goal is to show that $p+q$ can
be written as the product of three integers all greater than~1.

Since $p$ and~$q$ are both odd, their sum~$p+q$ is even. Therefore, $p+q$~is
divisible by~2, so $(p+q)/2$ is an integer. But $(p+q)/2$ is the
{\it average\/} of $p$ and~$q$, which must be a number strictly between $p$
and~$q$ (because $p\not=q$). Hence $(p+q)/2$ must be composite (because $p$
and~$q$ are consecutive primes). So we can write $(p+q)/2$ as the product of
two integers both greater than~1, say, $(p+q)/2=mn$.

Thus, we can write the sum~$p+q$ as
$$p+q=2\left(p+q\over2\right)=2(mn),$$
so $p+q$ is the product of 2,~$m$, and~$n$, each of which is an integer
greater than~1. \qed

\nobreak\medskip

\noindent[Note that this proof does not use the fact that $p$ and~$q$ are
themselves prime; it requires only that $p$ and~$q$ are both odd and that every
integer between $p$ and~$q$ is composite.]

\bigbreak %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem An eccentric sheep farmer has built an enclosure with four separate
pens, as shown below. In the center of the enclosure is a rather unusual
four-sided gate. Whenever three sheep enter the gate from three different
sides, the fourth side of the gate opens and all three sheep enter the fourth
pen.

If there are initially 24,~28, 32, and 36 sheep in the four pens, respectively,
is it possible that after some time has passed there will be an equal number of
sheep in each pen? What if there are initially 12,~14, 16, and 18 sheep in the
four pens, respectively? In each case justify your answer by demonstrating how
it can be done or by proving that it is impossible.

$$\convertMPtoPDF{homework-4-sheep-pen.mps}{0.8}{0.8}$$

\solution Suppose there are initially 24,~28, 32, and 36 sheep in the four
pens, so there are 120~sheep in all. If there are to be an equal number of
sheep in each of the four pens, there should be 30~sheep in each. One of the
pens must lose 6~sheep for this to happen. Each use of the gate can at best
decrease the number of sheep in this pen by~1, so we will need to use the gate
at least 6~times.

If our goal is to equalize the number of sheep in each pen, one sensible
strategy seems to be the following: Find the pen with the least number of sheep
(breaking ties arbitrarily), and move into it one sheep from each of the other
three pens. Repeat until all pens have the same number of sheep.

On the face of it, there seems to be no particular reason that this strategy
should always work; but if we try it on this specific example, it does work,
and more impressively it is able to achieve our goal with the minimum of 6~uses
of the gate, as shown below.
$$\vbox{\halign{\quad\hfil\strut${}#$\quad&&\hfil\strut${}#$\quad\cr
24&28&32&36\cr
+3&-1&-1&-1\cr
\noalign{\vskip2pt\hrule\vskip2pt}
27&27&31&35\cr
+3&-1&-1&-1\cr
\noalign{\vskip2pt\hrule\vskip2pt}
30&26&30&34\cr
-1&+3&-1&-1\cr
\noalign{\vskip2pt\hrule\vskip2pt}
29&29&29&33\cr
+3&-1&-1&-1\cr
\noalign{\vskip2pt\hrule\vskip2pt}
32&28&28&32\cr
-1&+3&-1&-1\cr
\noalign{\vskip2pt\hrule\vskip2pt}
31&31&27&31\cr
-1&-1&+3&-1\cr
\noalign{\vskip2pt\hrule\vskip2pt}
30&30&30&30\cr}}$$

\goodbreak

Now suppose there are initially 12,~14, 16, and 18 sheep in the four pens, so
there are 60~sheep in all. Our goal is to get 15~sheep in each pen. When we try
to use the previous strategy, we are repeatedly frustrated; it seems there is
no way to do it. Can we {\it prove\/} that it is impossible?

Here is one such proof, using modular arithmetic. We shall consider the
remainders when the number of sheep in each pen is divided by~4. For brevity,
we shall simply say ``remainders'' when we mean the remainders after the number
of sheep in each pen is divided by~4.

Let us consider how one use of the gate affects the remainders. Three of the
remainders are decreased by~1 (because three of the pens lose a sheep), while
the other remainder is increased by~3. But, modulo~4, adding~3 is the same as
subtracting~1! For example, $2-1\equiv1\ipmod4$ and $2+3\equiv1\ipmod4$. So
each use of the gate affects all four remainders the same way. If the four
remainders were equal before the gate was used, they will be equal after; and
if they were unequal before, they will be unequal after.

Initially we have 12,~14, 16, and 18 sheep in the four pens, so the remainders
start at 0,~2, 0, and~2. In particular, the starting remainders are
{\it unequal}.

Our goal is to have an equal number of sheep in each pen; specifically, we want
to have 15~sheep in each pen. Since $15\equiv3\ipmod4$, the remainders will all
be~3. The important thing is that, in our goal, all of the remainders are
{\it equal}.

Since a use of the gate cannot change unequal remainders to equal remainders,
there is no way to achieve our goal of an equal number of sheep in each pen if
we initially have 12,~14, 16, and 18 sheep in the four pens. \qed

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

\bye
