chap4.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

L'emploi continuel de l'analyse combinatoire que je fais dans la
plupart de mes d\'emonstrations, a rendu cette "notation" indispensable.''
\par\hfill\dash---Ch.~"Kramp" [|kramp|]\g
composite numbers, the "factorial"s:
\begindisplay
n!
	= 1 \cdt 2 \cdt \ldots \cdt n \,
	= \prod_{k=1}^ n k \,,
					\qquad\hbox{integer $n \geq 0$.}
\eqno\eqref|n!|
\enddisplay
According to our convention for an empty product,
this defines $0!$ to be~$1$.
Thus $n! = (n-1)!\,n$ for every positive integer~$n$.
This is the number of permutations of $n$~distinct objects.
That is, it's the number of ways to arrange $n$~things in a row:
There are $n$~choices for the first thing;
for each choice of first thing, there are $n-1$~choices for the second;
for each of these $n(n-1)$ choices, there are $n-2$ for the third;
and so on,
giving $n(n-1)(n-2) \ldots (1)$ arrangements in all.
Here are the first few values of the "factorial" function.
\begindisplay \let\preamble=\tablepreamble
n&&0&1&2&3&4&5&6&7&8&9&10\cr
\noalign{\hrule}
n!&& 1 & 1 & 2 & 6 & 24 & 120 & 720 & 5040 & 40320 & 362880 & 3628800\cr
\enddisplay
It's useful to know a few factorial facts, like
the first six or so values, and
the fact that $10!$ is about $3{1\over 2}$ million plus change;
another interesting fact is
that the number of digits in~$n!$ exceeds~$n$ when $n\ge25$.

We can prove that $n!$ is plenty big by using something like "Gauss"'s trick
of Chapter~1:
\begindisplay
n!^2=(1\cdot2\cdot\ldots\cdot n)(n\cdot\ldots\cdot2\cdot1)=\prod_{k=1}^n
 k(n+1-k)\,.
\enddisplay
We have $n\le k(n+1-k)\le{1\over4}(n+1)^2$, since the quadratic polynomial
$k(n+1-k)={1\over4}(n+1)^2-\bigl(k-\half(n+1)\bigr)^2$ has its smallest value
at $k=1$ and its largest value at $k=\half(n+1)$. Therefore
\begindisplay
\prod_{k=1}^n n\le n!^2\le\prod_{k=1}^n{(n+1)^2\over4}\,;
\enddisplay
that is,
\begindisplay
n^{n/2}\le n!\le{(n+1)^n\over 2^n}\,.
\eqno\eqref|crude-factorial-bound|
\enddisplay
This relation tells us that the factorial function grows exponentially!!

To approximate~$n!$ more accurately for large~$n$
we can use "Stirling's formula",
which we will derive in Chapter~9:
\begindisplay
n!
	\sim \sqrt{2 \pi n} \left( {n\over e} \right)^{\! n} \,.
\eqno\eqref|stirling-approx|
\enddisplay
And a still more precise approximation tells us the asymptotic relative error:
Stirling's formula undershoots $n!$ by a factor of about~$1/(12n)$.
Even for fairly small~$n$ this more precise estimate is pretty good.
For example, Stirling's approximation~\thiseq\ gives a value near $3598696$
when $n=10$, and this is about $0.83\%\approx1/120$ too small.
Good stuff, asymptotics.

But let's get back to primes.
We'd like to determine, for any given prime~$p$, the largest
power of~$p$ that divides~$n!$;
that is, we want the exponent of~$p$ in $n!$'s unique factorization.
We denote this number by~$\epsilon_p(n!)$,
and we start our investigations with
the small case $p=2$ and $n=10$.
Since $10!$ is the product of ten numbers,
$\epsilon_2(10!)$ can be found by
summing the powers-of-2 contributions of those ten numbers;
this calculation corresponds to summing the columns of the following array:
\begindisplay\def\preamble{\bigstrut\hfil$##$\ &\vrule##&%
 \ \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \hfil$##$\hfil&%
 \ \vrule##&\ \hfil$##$\hfil}\offinterlineskip
&& 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 &&\hbox{powers of $2$} \cr
\omit&height 2pt&&&&&&&&&&&&\cr
\noalign{\hrule}
\omit&height 2pt&&&&&&&&&&&&\cr
\hbox{divisible by $2$}&&& \hbox{x} && \hbox{x} && \hbox{x} && \hbox{x}
				&& \hbox{x} &&5 = \lfloor 10/2 \rfloor \cr
\hbox{divisible by $4$}&&&&& \hbox{x} &&&& \hbox{x}
					&&&&2 = \lfloor 10/4 \rfloor \cr
\hbox{divisible by $8$}&&&&&&&&& \hbox{x} &&&&1 = \lfloor 10/8 \rfloor \cr
\omit&height 2pt&&&&&&&&&&&&\cr
\noalign{\hrule}
\omit&height 2pt&&&&&&&&&&&&\cr
\hbox{powers of $2$}&& 0 & 1 & 0 & 2 & 0 & 1 & 0 & 3 & 0 & 1 &&8\cr
\enddisplay
(The column sums form what's sometimes called the {\it "ruler function"\/}
\g A powerful ruler.\g
$\rho(k)$, because of their similarity to
`\thinspace\vbox{\hrule \unitlength=.015625in
 \def\\#1{\vrule depth#1\unitlength width.5\unitlength\kern1.5\unitlength}
 \hbox{\\6\\1\\2\\1\\3\\1\\2\\1\\4\\1\\2\\1\\3\\1\\2\\1\\5%
          \\1\\2\\1\\3\\1\\2\\1\\4\\1\\2\\1\\3\\1\\2\\1\\6\kern-1.5\unitlength}
 \kern0pt}\thinspace', the lengths of lines
marking fractions of an inch.)
The sum of these ten~sums is~$8$;
hence $2^8$ divides~$10!$ but $2^9$ doesn't.

There's also another way:
We can sum the contributions of the rows.
The first row marks the numbers that contribute a power of~$2$
(and thus are divisible by~$2$);
there are $\lfloor 10/2 \rfloor = 5$ of them.
The second row marks those that contribute an additional power of~$2$;
there are $\lfloor 10/4 \rfloor = 2$ of them.
And the third row marks those that contribute yet another;
there are $\lfloor 10/8 \rfloor = 1$ of them.
These account for all contributions,
so we have $\epsilon_2(10!) = 5+2+1 = 8$.

For general~$n$ this method gives
\begindisplay
 \epsilon_2(n!)
	= \left\lfloor {n\over 2} \right\rfloor +
		\left\lfloor {n\over 4} \right\rfloor +
		\left\lfloor {n\over 8} \right\rfloor + \cdots
	= \sum_{k \geq 1} \left\lfloor {n\over 2^k} \right\rfloor \,.
\enddisplay
This sum is actually finite, since the summand is zero when $2^k > n$.
Therefore it has only $\lfloor \lg n \rfloor$ nonzero terms,
and it's computationally quite easy.
For instance, when $n=100$ we have
\begindisplay
 \epsilon_2(100!)
	= 50 + 25 + 12 + 6 + 3 + 1
	= 97 \,.
\enddisplay
\looseness=-1
Each term is just the floor of half the previous term.
This is true for all~$n$,
because as a special case of~\equ(3.|rational-in/out|)
we have $\lfloor n/2^{k+1} \rfloor
		= \bigl\lfloor \lfloor n/2^k \rfloor /2 \bigr\rfloor$.
It's especially easy to see what's going on here
 when we write the numbers in binary:
\begindisplay\def\preamble{\hfil$##$&${}=\hfil(##)_2$&${}=\hfil##$}%
\postdisplaypenalty=10000
100			& 1100100	& 100	\cr
\lfloor 100/2 \rfloor	& 110010	& 50	\cr
\lfloor 100/4 \rfloor	& 11001		& 25	\cr
\lfloor 100/8 \rfloor	& 1100		& 12	\cr
\lfloor 100/16 \rfloor	& 110		& 6	\cr
\lfloor 100/32 \rfloor	& 11		& 3	\cr
\lfloor 100/64 \rfloor	& 1		& 1	\cr
\enddisplay
We merely drop the least significant bit from one term to get the next.

The binary representation also shows us how to derive another
formula,
\begindisplay
\epsilon_2(n!)=n-\nu_2(n)\,,
\eqno\eqref|2-factors|
\enddisplay
where $\nu_2(n)$ is the number of $1$'s in the binary representation of~$n$.
"!sideways addition" "!nu function $\nu_d$"
This simplification works
because each $1$ that contributes $2^m$ to the value
of~$n$ contributes $2^{m-1}+2^{m-2}+\cdots+2^0=2^m-1$
 to the value of $\epsilon_2(n!)$.

Generalizing our findings to an arbitrary prime~$p$, we have
\begindisplay
\epsilon_p(n!)
	= \left\lfloor {n\over p} \right\rfloor
		+ \left\lfloor {n\over p^2} \right\rfloor
		+ \left\lfloor {n\over p^3} \right\rfloor + \cdots
	= \sum_{k \geq 1} \left\lfloor {n\over p^k} \right\rfloor
\eqno
\enddisplay
by the same reasoning as before.

About how large is $\epsilon_p(n!)$?
We get an easy (but good) upper bound by simply removing the floor
from the summand and then summing an infinite geometric progression:
\begindisplay \openup3pt
\epsilon_p(n!)
	&< {n\over p} + {n\over p^2} + {n\over p^3} + \cdots \cr
	&= {n\over p}
		\left( 1 + {1\over p} + {1\over p^2} + \cdots\, \right) \cr
	&= {n\over p} \left( {p\over p-1} \right) \cr
\noalign{\smallskip}
	&= {n\over p-1} \,.
\enddisplay
For $p=2$ and $n=100$ this inequality says that $97 < 100$.
Thus the upper bound~$100$ is not only correct,
it's also close to the true value~$97$.
In fact, the true value $n-\nu_2(n)$ is $\sim n$ in general, because
$\nu_2(n)\le\lceil@\lg n\rceil$ is "asymptotic"ally
much smaller than~$n$.

When $p=2$ and~$3$ our formulas give
$\epsilon_2(n!)\sim n$ and $\epsilon_3(n!)\sim n/2$,
so it seems reasonable that every once in awhile
$\epsilon_3(n!)$ should be exactly half as big as $\epsilon_2(n!)$.
For example, this happens when $n=6$ and $n=7$, because
$6!=2^4\cdt3^2\cdt5=7!/7$. But nobody has yet proved that
such coincidences happen infinitely often.

The bound on~$\epsilon_p(n!)$ in turn gives us
a bound on~$p^{\epsilon_p(n!)}$, 
which is $p$'s contribution to $n! \mskip2mu$:
\begindisplay 
p^{\epsilon_p(n!)}
	< p^{n/(p-1)} \,.
\enddisplay
And we can simplify this formula (at the risk of greatly loosening
the upper bound) by noting that $p\le2^{p-1}$; hence
$p^{n/(p-1)}\le(2^{p-1})^{n/(p-1)}=2^n$.
In other words,
the contribution that any prime makes to~$n!$ is less than~$2^n$.

We can use this observation
 to get another proof that there are infinitely many primes.
For if there were only the $k$~primes $2$,~$3$, \dots,~$P_k$, then
we'd have $n! < (2^n)^k = 2^{nk}$ for all $n>1$, since each prime
can contribute at most a factor of~$2^n-1$.
But we can easily contradict the inequality $n!<2^{nk}$
 by choosing $n$ large enough,
say $n = 2^{2k}$. Then
\begindisplay
n!<2^{nk}=2^{2^{2k}k}=n^{n/2}\,,
\enddisplay
contradicting the inequality $n!\ge n^{n/2}$ that we derived
in \eq(|crude-factorial-bound|).
There are infinitely many primes, still.

We can even beef up this argument to get a crude bound on $\pi(n)$,
the number of primes not exceeding~$n$.
Every such prime contributes a factor of less than~$2^n$ to $n!$; so,
as before,
\begindisplay
 n!
	< 2^{n\pi(n)} \,.
\enddisplay
If we replace $n!$ here by Stirling's approximation \eq(|stirling-approx|),
which is a lower bound, and take logarithms, we get
\begindisplay
\textstyle n@\pi(n)>n\lg(n/e)+\half\lg(2\pi n)\,;
\enddisplay
hence
\begindisplay
\pi(n)>\lg(n/e)\,.
\enddisplay
This lower bound is quite weak, compared with the actual value $\pi(n)\sim
n/\!@\ln n$, because $\log n$ is much smaller than $n/\!@\log n$ when
$n$ is large. But we didn't have to work very hard to get it,
and a bound is a bound.

\beginsection 4.5 Relative Primality

When $\gcd(m,n)=1$, the integers $m$ and $n$ have no prime factors
in common and we say that they're {\it "relatively prime"}.

This concept is so important in practice, we ought to have a special
"notation" for it; but alas, number theorists haven't agreed on a very
good one yet. Therefore we cry: {\sc Hear us, O Mathematicians of the World!
Let us not wait any longer! We can make many
formulas clearer by adopting a new notation now! Let us agree to
\g Like perpendicular lines don't have a common direction,
perpendicular numbers don't have common factors.\g
write `$@m\rp n$', and to say ``$@m$~is "prime to"~$n$,\qback'' if
\tabref|nn:rp|%
$m$ and~$n$ are relatively prime}. In~other words,
let us declare that
\begindisplay
m\rp n\quad\iff\quad\hbox{$m,n$ are integers and $\gcd(m,n)=1$}.
\eqno\eqref|rp-def|
\enddisplay

A fraction $m/n$ is in lowest terms if and only if $m\rp n$. Since
we reduce fractions to lowest terms by casting out the largest common
factor of numerator and denominator, we suspect that, in general,
\begindisplay
m/\!\gcd(m,n)\;\rp\;n/\!\gcd(m,n)\,;
\eqno\eqref|cast-out|
\enddisplay
and indeed this is true. It follows from a more general
law, $\gcd(km,kn)=k\gcd(m,n)$, proved in exercise~|gcd-prod|.

The $\rp$ relation has a simple formulation when we work with the
"prime-exponent
representation"s of numbers, because of the gcd rule \eq(|gcd-exp|):
\begindisplay
m\rp n\qquad\iff\qquad \min(m_p,n_p)=0\quad\hbox{for all $p$}.
\eqno