chap4.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

% Chapter 4 of Concrete Mathematics
% (c) Addison-Wesley, all rights reserved.
\input gkpmac
\refin bib
\refin chap2
\refin chap3

\pageno=102
\beginchapter 4 Number Theory

INTEGERS ARE CENTRAL to the discrete mathematics we are emphasizing in
this book. Therefore we want to explore the {\it"theory" of "numbers"},
an important branch of mathematics concerned with the properties of
integers.

We tested the number theory waters in the previous chapter, by introducing
\g In other words, be prepared to drown.\g
binary operations called `mod' and `gcd'. Now let's plunge in and
really immerse ourselves in the subject.

\beginsection 4.1 Divisibility

We say that $m$ divides $n$ (or $n$ is "divisible" by $m$) if $m>0$
and the ratio $n/m$ is an integer. This property underlies all of
number theory, so it's convenient to have a special "notation" for it.
We therefore write
\tabref|nn:div|%
\begindisplay
m\divides n\quad\iff\quad m>0\!\!\And\!\!\hbox{$n=mk$ for some integer $k$}\,.
\eqno\eqref|div-def|
\enddisplay
(The notation `$m@\vert@n$' is actually much more common than `$m\divides n$'
in current mathematics literature. But vertical lines are overused\dash---%
for absolute values, set delimiters, conditional probabilities, etc.\dash---%
and backward slashes are under\-used. Moreover, `$m\divides n$' gives an
impression that $m$ is the denominator of an implied ratio. So we shall
boldly let our divisibility symbol lean leftward.)

If $m$ does not divide $n$ we write `$m\ndivides n$'.

There's a similar relation, ``$n$ is a "multiple" of~$m$,\qback'' which
means almost the same thing except that $m$~doesn't have to be positive.
In this case we simply mean that $n=mk$ for some integer~$k$. Thus, for
\g\noindent\llap{``}\dots\ no integer is divisible by~$-1$ (strictly speaking).''\par
\hfill\dash---"Graham", "Knuth",\par\hfill and "Patashnik" [|conc-math|]\g
example, there's only one multiple of~$0$ (namely~$0$), but nothing is
divisible by~$0$.
Every integer is a multiple of~$-1$, but no integer is divisible
by~$-1$ (strictly speaking).
 These definitions apply when $m$ and~$n$ are any real
numbers; for example, $2\pi$ is divisible by~$\pi$.
But we'll almost always be using them when $m$ and~$n$ are
integers. After all, this is number theory.

The {\it "greatest common divisor"\/} of two integers $m$ and~$n$ is the
\g In Britain we call this `hcf' ("highest common factor").\g
largest integer that divides them both:
\begindisplay
\gcd(m,n)=\max\,\{\,k\mid k\divides m\And k\divides n\,\}\,.
\eqno\eqref|gcd-def|
\enddisplay
For example, $\gcd(12,18)=6$. This is a familiar notion, because it's the
common factor that fourth graders learn to take out of a fraction
"!gcd"
$m/n$ when reducing it to lowest terms: $12/18=(12/6)\big/(18/6)=2/3$.
Notice that if $n>0$ we have $\gcd(0,n)=n$, because any positive
number divides~$0$, and because
$n$~is the largest divisor of itself. The value of $\gcd(0,0)$ is
undefined.

Another familiar notion is the {\it "least common multiple"},
\g Not to be confused with the greatest common multiple.\g
"!lcm"
\begindisplay
\lcm(m,n)=\min\,\{\,k\mid\hbox{$k>0$},\quad
 m\divides k\And n\divides k\,\}\,;
\eqno\eqref|lcm-def|
\enddisplay
this is undefined if $m\le0$ or $n\le0$. Students of arithmetic recognize
this as the least common denominator, which is used when adding fractions
with denominators $m$ and~$n$. For example, $\lcm(12,18)=36$, and
fourth graders know that
${7\over12}+{1\over18}={21\over36}+{2\over36}={23\over36}$.
The lcm is somewhat analogous to the gcd, but we don't give it equal time
because the gcd has nicer properties.

One of the nicest properties of the gcd is that it is easy to compute,
using a 2300-year-old method called {\it "Euclid's algorithm"}.
"!algorithm, Euclid's"
To calculate $\gcd(m,n)$, for given values
$0\le m<n$, Euclid's algorithm uses the recurrence
\begindisplay
\gcd(0,n)&=n\,;\cr
\gcd(m,n)&=\gcd(n\bmod m,\,m)\,,\qquad\hbox{for $m>0$}.
\eqno\eqref|euclid|
\enddisplay
Thus, for example, $\gcd(12,18)=\gcd(6,12)=\gcd(0,6)=6$. The stated recurrence
is valid, because any common divisor of $m$ and~$n$ must also be a common
divisor of both $m$ and the number $n\bmod m$,
which is $n-\lfloor n/m\rfloor m$. There doesn't seem
to be any recurrence for $\lcm(m,n)$ that's anywhere near as simple as
this. (See exercise~|gcd-times-lcm|.)

Euclid's algorithm also gives us more: We can extend it so that it will compute
integers $m'$ and~$n'$ satisfying
\begindisplay
m'm+n'n=\gcd(m,n)\,.
\eqno\eqref|''|
\enddisplay
\g(Remember that $m'$ or $n'$ can be negative.)\g
Here's how. If $m=0$, we simply take $m'=0$ and $n'=1$. Otherwise we let
$r=n\bmod m$ and apply the method recursively with $r$~and~$m$ in place
of $m$~and~$n$, computing $\overline r$ and $\overline m$ such that
\begindisplay
\overline r\,r+\overline m\,m=\gcd(r,m)\,.
\enddisplay
Since $r=n-\lfloor n/m\rfloor m$ and $\gcd(r,m)=\gcd(m,n)$,
this equation tells us that
\begindisplay
\overline r\,\bigl(n-\lfloor n/m\rfloor m\bigr)+\overline m\,m=\gcd(m,n)\,.
\enddisplay
The left side can be rewritten to show its dependency on $m$ and $n$:
\begindisplay
\bigl(\overline m-\lfloor n/m\rfloor@\overline r@\bigr)\,m+\overline r\, n
=\gcd(m,n)\,;
\enddisplay
hence $m'=\overline m-\lfloor n/m\rfloor\overline r$ and
 $n'=\overline r$ are the integers we need in \thiseq. For example, in our
favorite case $m=12$, $n=18$, this method gives $6=0\cdt0+1\cdt6=1\cdt6+0\cdt12
=(-1)\cdt12+1\cdt18$.

But why is \thiseq\ such a neat result? The main reason is that there's a
sense in which the numbers $m'$ and~$n'$
actually {\it prove\/} that Euclid's algorithm has produced the correct
answer in any particular case. Let's suppose that our computer
has told us after a lengthy calculation that $\gcd(m,n)=d$ and that
$m'm+n'n=d$; but we're skeptical and think that there's really a greater
common divisor, which the machine has somehow overlooked. This cannot be,
however,
because any common divisor of $m$ and~$n$ has to divide $m'm+n'n$;
so it has to divide~$d$; so it has to be $\le d$. Furthermore we can
easily check that $d$ does divide both $m$ and $n$. (Algorithms that
"!certificate of correctness"
output their own proofs of correctness are called {\it "self-certifying"}.)

We'll be using \thiseq\ a lot in the rest of this chapter. One of its
important consequences is the following mini-theorem:
\begindisplay
k\divides m\And k\divides n\qquad\iff\qquad k\divides\gcd(m,n)\,.
\eqno\eqref|div-gcd|
\enddisplay
(Proof: If $k$ divides both $m$ and~$n$, it divides $m'm+n'n$,
so it divides $\gcd(m,n)$. Conversely, if $k$ divides $\gcd(m,n)$, it
divides a divisor of~$m$ and a divisor of~$n$, so it divides both
$m$ and~$n$.) We always knew that any common divisor of $m$ and~$n$ must be
{\it less than or equal to\/} their gcd; that's the definition of greatest
common divisor. But now we know that any common divisor is, in fact,
{\it a divisor of\/} their gcd.

Sometimes we need to do sums over all divisors of~$n$. In this case
it's often useful to use the handy rule
\begindisplay
\sum_{m\divides n}a_m=\sum_{m\divides n}a_{n/m}\,,\qquad
 \hbox{integer $n>0$,}
\eqno\eqref|swap-div|
\enddisplay
which holds since $n/m$ runs through all divisors of~$n$ when $m$ does.
For example, when $n=12$ this says that $a_1+a_2+a_3+a_4+a_6+a_{12}=
a_{12}+a_6+a_4+a_3+a_2+a_1$.

There's also a slightly more general identity,
\begindisplay
\sum_{m\divides n}a_m=\sum_k\sum_{m>0}a_m\[n=mk]\,,
\eqno\eqref|sum-div|
\enddisplay
which is an immediate consequence of the definition \eq(|div-def|).
If $n$ is positive, the right-hand side of~\thiseq\ is $\sum_{k\divides n}
a_{n/k}$; hence \thiseq\ implies \eq(|swap-div|).
And equation \thiseq\ works also when $n$ is negative. (In such cases,
the nonzero terms on the right occur when $k$ is the negative of
a divisor of~$n$.)

Moreover, a "double sum" over divisors can be ``interchanged'' by the law
\begindisplay
\sum_{m\divides n}\,\sum_{k\divides m}a_{k,m}=
\sum_{k\divides n}\,\sum_{l\divides(n/k)}a_{k,kl}\,.
\eqno\eqref|interch-div|
\enddisplay
For example, this law takes the following form when $n=12$:
\begindisplay \def\\#1#2{a_{#1,#2}} \def\@{{12}}
&\\11\,+\,(\\12+\\22)\,+\,(\\13+\\33)\cr
&\qquad\qquad+\,(\\14+\\24+\\44)\,+\,(\\16+\\26+\\36+\\66)\cr
&\qquad\qquad+\,(\\1\@+\\2\@+\\3\@+\\4\@+\\6\@+\\\@\@)\cr
\noalign{\vskip2pt}
&\quad=(\\11+\\12+\\13+\\14+\\16+\\1\@)\cr
&\qquad\qquad+\,(\\22+\\24+\\26+\\2\@)\,+\,(\\33+\\36+\\3\@)\cr
&\qquad\qquad+\,(\\44+\\4\@)\,+\,(\\66+\\6\@)\,+\,\\\@\@\,.\cr
\enddisplay

We can prove \thiseq\ with Iversonian manipulation. The left-hand side is
\begindisplay
\sum_{j,l}\,\sum_{k,m>0}a_{k,m}\[n=jm]\[m=kl]=\sum_j\sum_{k,l>0}a_{k,kl}\[n=jkl]\,;
\enddisplay
the right-hand side is
\begindisplay
\sum_{j,m}\,\sum_{k,l>0}a_{k,kl}\[n=jk]\[n/k=ml]=
\sum_m\sum_{k,l>0}a_{k,kl}\[n=mlk]\,,
\enddisplay
which is the same except for renaming the indices.
This example indicates that the techniques we've learned in Chapter~2 will
come in handy as we study number theory.

\beginsection 4.2 Primes

A positive integer~$p$ is called {\it "prime"\/} if it has just two
divisors, namely
$1$~and~$p$. {\sl Throughout the rest of this chapter, the letter~$p$
will always stand for a prime number, even when we don't say so explicitly.}
\g How about the p in `explicitly'?\g
By convention, $1$~isn't prime, so the sequence of primes starts out like this:
\begindisplay
 2,\,3,\,5,\,7,\,11,\,13,\,17,\,19,\,23,\,29,\,31,\,37,\,41,\, \ldots \,.
\enddisplay
"!Seaver, George Thomas"
Some numbers look prime but aren't, like $91$ ($=7\cdt13$) and
$161$ ($=7\cdt23$). These numbers and others that have three or more divisors
are called {\it "composite"}. Every integer greater than~$1$ is either prime
or composite, but not both.

Primes are of great importance,
 because they're the fundamental building blocks
of all the positive integers. Any positive integer~$n$ can be written as a
product of primes,
\begindisplay\advance\abovedisplayskip-5pt \advance\belowdisplayskip-2pt
n=p_1\ldots p_m=\prod_{k=1}^m p_k\,,\qquad p_1\le\cdots\le p_m\,.
\eqno\eqref|prime-factors|
\enddisplay
 For example,
$12=2\cdt2\cdt3$; $11011=7\cdt11\cdt11\cdt13$; $11111=41\cdt271$.
"!Seaver, George Thomas"
(Products denoted by $\prod$ are analogous to sums denoted by $\sum$, as
"!product $\prod$"
explained in exercise~2.|prod-analogies|.
If $m=0$, we consider this to be an "empty product", whose value is~$1$
by definition; that's the way $n=1$ gets represented by \thiseq.) Such
a factorization is always possible because if $n>1$ is not prime it has
a divisor $n_1$ such that $1<n_1<n$; thus we can write $n=n_1\cdt n_2$,
and (by induction) we know that $n_1$ and $n_2$ can be written as
products of primes.

Moreover, the expansion in \thiseq\ is {\it unique\/}: There's only one
"!unique factorization" "!factorization into primes"
way to write $n$ as a product of primes in nondecreasing order. This
statement is
called the "Fundamental Theorem of Arithmetic", and it seems so obvious
that we might wonder why it needs to be proved. How could there be two
different sets of primes with the same product? Well, there can't, but
the reason {\it isn't\/} simply ``by definition of prime numbers.\qback''
For example, if we consider the set of all real numbers of the
form $m+n\sqrt{10}$ when $m$ and $n$ are integers, the product of any
two such numbers is again of the same form, and we can call such
a number ``prime'' if it
can't be factored in a nontrivial way. The number $6$ has two representations,
$2\cdt3=(4+\sqrt{10}\,)(4-\sqrt{10}\,)$;
yet exercise~|nonunique-factors| shows that
$2$, $3$, $4+\sqrt{10}$, and $4-\sqrt{10}$ are all ``prime''
in this system.

Therefore we should prove rigorously that \thiseq\ is unique. There is certainly
only one possibility when $n=1$, since the product must be empty in that case;
so let's suppose that $n>1$ and that all smaller
numbers factor uniquely. Suppose we have two factorizations
\begindisplay
n=p_1\ldots p_m=q_1\ldots q_k\,,\qquad p_1{\le}\cdots{\le} p_m\And
q_1{\le}\cdots{\le} q_k\,,
\enddisplay
where the $p$'s and $q$'s are all prime.
We will prove that $p_1=q_1$.
If not, we can assume that $p_1<q_1$, making
$p_1$ smaller than all the $q$'s. Since $p_1$ and $q_1$ are prime,
their gcd must be~$1$; hence Euclid's self-certifying algorithm
gives us integers $a$ and $b$ such that $ap_1+bq_1=1$. Therefore
\begindisplay
ap_1q_2\ldots q_k\,+\,bq_1q_2\ldots q_k=q_2\ldots q_k\,.
\enddisplay
Now $p_1$ divides both terms on the left, since $q_1q_2\ldots q_k=n$;
hence $p_1$ divides the right-hand side, $q_2\ldots q_k$.
Thus $q_2\ldots q_k/p_1$ is an integer, and $q_2\ldots q_k$ has a prime
factorization in which $p_1$ appears. But $q_2\ldots q_k<n$, so it has a
unique factorization (by induction).
This contradiction shows that $p_1$ must be equal to~$q_1$ after all.
Therefore we can divide both of $n$'s factorizations by $p_1$, obtaining
$p_2\ldots p_m=q_2\ldots q_k<n$. The other factors must likewise be equal
(by induction), so our proof of uniqueness is complete.

Sometimes it's more useful to state the Fundamental Theorem in
\g It's the factorization, not the theorem, that's unique.\g
another way: {\sl Every positive integer can be written uniquely in the form}
\begindisplay \advance\belowdisplayskip-3pt
n\;=\;\prod_p p^{n_p}\,,\qquad\hbox{where each $n_p\ge0$}.
\eqno\eqref|primepower-factors|
\enddisplay
The right-hand side is a product over