chap4.tex

Concrete_Mathematics_2nd_Ed_TeX_Source_Code

How about Question~1? That's easy, now that we understand the
fundamental connection between tree nodes and $2\times2$ matrices.
Given a pair of positive integers $m$ and~$n$, with $m\rp n$, we can
find the position of $m/n$ in the Stern--Brocot tree by ``"binary search"''
as follows:
\begindisplay \postdisplaypenalty=10000
&S:=I\,;\cr
&\hbox{{\bf while} \ $m/n\ne f(S)$ \ {\bf do}}\hidewidth\cr
&\hbox{\qquad{\bf if} \ $m/n<f(S)$ \ }&
 \hbox{\bf then} \ &\bigl(\hbox{output}(L); \ \ &S:=SL\bigr)\cr
&&\hbox{\bf else} \ &\bigl(\hbox{output}(R); \ \ &S:=SR\bigr)\,.\cr
\enddisplay
This outputs the desired string of $L$'s and $R$'s.

There's also another way to do the same job, by changing $m$ and~$n$ instead
of maintaining the state~$S$. If $S$~is any $2\times2$ matrix, we have
\begindisplay
f(RS)=f(S)+1
\enddisplay
because $RS$ is like $S$ but with the top row added to the bottom row.
(Let's look at it in slow motion:
\begindisplay
S=\pmatrix{n&n'\cr m&m'\cr}\,;\qquad RS=\pmatrix{n&n'\cr m+n&m'+n'\cr}\,;
\enddisplay
hence $f(S)=(m+m')/(n+n')$ and $f(RS)=\bigl((m+n)+(m'+n')\bigr)/(n+n')$.)
If we carry out the binary search algorithm on a fraction $m/n$
with $m>n$, the first output will be~$R$; hence the subsequent behavior
of the algorithm will have $f(S)$ exactly $1$~greater than if we had
begun with $(m-n)/n$ instead of $m/n$. A similar property holds for~$L$,
and we have
\begindisplay \openup6pt
&{m\over n}=f(RS)&\qquad\iff\qquad{m-n\over n}=f(S)\,,&\qquad\hbox{when $m>n$};\cr
&{m\over n}=f(LS)&\qquad\iff\qquad{m\over n-m}=f(S)\,,&\qquad\hbox{when $m<n$}.\cr
\enddisplay
This means that we can transform the binary search algorithm to the following
matrix-free procedure:
\begindisplay
&\hbox{{\bf while} \ $m\ne n$ \ {\bf do}}\hidewidth\cr
&\hbox{\qquad{\bf if} \ $m<n$ \ }&
 \hbox{\bf then} \ &\bigl(\hbox{output}(L); \ \ &n:=n-m@\bigr)\cr
&&\hbox{\bf else} \ &\bigl(\hbox{output}(R); \ \ &m:=m-n\bigr)\,.\cr
\enddisplay
For example, given $m/n=5/7$, we have successively
\begindisplay\def\preamble{&\hfil$##$\hfil\ }
m=&\ 5&&5&&3&&1&&1\cr
n=&\ 7&&2&&2&&2&&1\cr
\hbox to0pt{\hss output\hss}&&L&&R&&R&&L\cr
\enddisplay
in the simplified algorithm.

"Irrational numbers" don't appear in the Stern--Brocot tree, but all the rational
numbers that are ``close'' to them do. For example, if we try the binary
search algorithm with the number $e=2.71828\ldots\,$, instead of with a fraction
$m/n$, we'll get an infinite string of $L$'s and $R$'s that begins
\begindisplay
RRLRRLRLLLLRLRRRRRRLRLLLLLLLLRLR\,\ldots\,.
\enddisplay
We can consider this infinite string to be the representation of~$e$ in
the "Stern--Brocot number system", just as we can represent $e$ as
an infinite decimal $2.718281828459\!\ldots\,$ or as an infinite binary fraction
$(10.101101111110\ldots\,)_2$. Incidentally, it turns out that
$e$'s representation has a regular pattern in the Stern--Brocot system:
\begindisplay
e=RL^0RLR^2LRL^4RLR^6LRL^8RLR^{10}LRL^{12}RL\,\ldots\,;
\enddisplay
this is equivalent to a special case of something that "Euler"~[|euler-e-cf|]
discovered when he was 24 years old.

From this representation we can deduce that the fractions
\begindisplay
\unitlength=15pt
\countdef\m=0 \countdef\mp=2 \countdef\n=4 \countdef\np=6
\m=0 \mp=1 \n=1 \np=0
\def\\#1{\if #1R\advance\m\mp \advance\n\np{\number\m\over\number\n}
 \else\advance\mp\m \advance\np\n{\number\mp\over\number\np}\fi
 ,\mskip-8mu\raise\unitlength\hbox{$\scriptstyle#1$}}
\textstyle
\\R\\R\\L\\R\\R\\L\\R\\L\\L\\L\\L\\R\\L\\R\\R\\R\\R
\ldots
\enddisplay
are the simplest rational upper and lower approximations to $e$.
For if $m/n$ does not appear in this list, then some fraction in this list
whose numerator is $\le m$ and whose denominator is $\le n$ lies
between $m/n$ and~$e$. For example, $27\over10$ is not as simple
an approximation as ${19\over7}=2.714\ldots\,$, which appears in the
list and is closer to~$e$. We can see this because the Stern--Brocot
tree not only includes all rationals, it includes them in order, and
because all fractions with small numerator and denominator appear
above all less simple ones. Thus, ${27\over10}=RRLRRLL$ is less than
${19\over7}=RRLRRL$, which is less than $e=RRLRRLR\ldots\,$.
Excellent approximations can be found in this way. For example,
${1264\over465}\approx2.718280$ agrees with $e$ to six decimal places;
we obtained this fraction from the first 19 letters of $e$'s Stern--Brocot
representation, and the accuracy is about what we would get with
19~bits of $e$'s binary representation.

We can find
the infinite representation of an irrational number $\alpha$
by a simple modification of the matrix-free binary search procedure:
\begindisplay
&\hbox{\bf if} \ \alpha<1 \ &\hbox{\bf then} \ &\bigl(\hbox{output}(L); \ \
 &\alpha:=\alpha/(1-\alpha)\bigr)\cr
&&\hbox{\bf else} \ &\bigl(\hbox{output}(R); \ \ &\alpha:=\alpha-1\bigr)\,.\cr
\enddisplay
(These steps are to be repeated infinitely many times, or until we get
tired.) If $\alpha$ is rational, the infinite representation obtained
in this way is the same as before but with $RL^\infty$ appended at the
right of $\alpha$'s (finite) representation. For example, if $\alpha=1$,
we get $RLLL\ldots\,$, corresponding to the infinite sequence of fractions
${1\over1}$, $2\over1$, $3\over2$, $4\over3$, $5\over4$, \dots, which
approach $1$ in the limit. This situation is exactly analogous to
ordinary binary notation, if we think of $L$~as~$0$ and $R$~as~$1$:
Just as every real number~$x$ in $[@0\dts1)$ has an infinite binary
representation $(.b_1b_2b_3\ldots\,)_2$ not ending with all $1$'s,
every real number $\alpha$ in $[@0\dts\infty)$ has an infinite Stern--Brocot
representation $B_1B_2B_3\ldots$ not ending with all $R$'s. Thus we have
a one-to-one order-preserving correspondence between $[@0\dts1)$ and
$[@0\dts\infty)$ if we let $0\leftrightarrow L$ and $1\leftrightarrow R$.

There's an intimate relationship between "Euclid's algorithm" and the
Stern--Brocot representations of rationals. Given $\alpha=m/n$,
we get $\lfloor m/n\rfloor$ $R$'s, then $\bigl\lfloor n/(m\bmod n)
\bigr\rfloor$ $L$'s, then $\bigl\lfloor(m\bmod n)\big/\bigl(n\bmod
(m\bmod n)\bigr)\bigr\rfloor$ $R$'s, and so on. These numbers
$m\bmod n$, $n\bmod(m\bmod n)$, \dots~are just the values examined in
Euclid's algorithm. (A little fudging is needed
at the end to make sure that there aren't infinitely many
$R$'s.) We will explore this relationship further in Chapter~6.

\beginsection 4.6 `mod': The Congruence Relation

"Modular arithmetic" is one of the main tools provided by number theory.
"!mod, congruence relation"
\g \noindent\llap{``}Numerorum congruentiam hoc signo, $\=$, in posterum
denotabimus, modulum ubi opus erit in clausulis adiungentes,
$-16\=9\break ({\rm mod.\,}5)$,
$-7\=\break15\ ({\rm mod.\,}11)$.''\par
\hfill\dash---C.\thinspace F. "Gauss" [|gauss-disq|]\g
We got a glimpse of it in Chapter~3 when we used the binary
operation `mod', usually as one operation amidst others in an expression.
In this chapter we will use `mod' also with entire equations, for
which a slightly different notation is more convenient:
\begindisplay
a\=b\pmod m\qquad\iff\qquad a\bmod m=b\bmod m\,.
\eqno\eqref|pmod-def|
\enddisplay
For example, $9\=-16$ (mod~$5$), because $9\bmod5=4=(-16)\bmod5$.
The formula `$a\=b$ \tmod m' can be read ``$a$~is congruent to~$b$
modulo~$m$.\qback'' The definition makes sense when $a$, $b$, and~$m$
are arbitrary real numbers, but we almost always use it with integers only.

Since $x\bmod m$ differs from $x$ by a multiple of~$m$, we can
understand "congruences" in another way:
\begindisplay
a\=b\pmod m\qquad\iff\qquad \hbox{$a-b$ is a multiple of $m@$}.
\eqno\eqref|alt-pmod-def|
\enddisplay
For if $a\bmod m=b\bmod m$, then the definition of `mod' in
\equ(3.|bmod-def|) tells us that $a-b=a\bmod m+km-(b\bmod m+lm)=(k-l)m$
for some integers $k$ and~$l$. Conversely if $a-b=km$, then $a=b$ if
$m=0$; otherwise
\begindisplay
a\bmod m=a-\lfloor a/m\rfloor m&=b+km-\bigl\lfloor(b+km)/m\bigr\rfloor m\cr
&=b-\lfloor b/m\rfloor m=b\bmod m\,.
\enddisplay
The characterization of $\=$ in \thiseq\ is often easier to apply than
\eq(|pmod-def|). For example,
we have $8\=23$ \tmod5 because $8-23=-15$ is a multiple of~$5$; we don't
have to compute both $8\bmod5$ and $23\bmod5$.

The congruence sign `$\,\=\,$' looks conveniently like `$\,=\,$',
\g\noindent\llap{``}I feel fine today modulo a slight headache.''\par
\hfill\dash---The "Hacker"'s\par\hfill Dictionary [|hackers-dict|]\g
because congruences are almost like equations. For example, congruence is an
{\it"equivalence relation"\/}; that is, it satisfies the reflexive
law `$a\=a$', the symmetric law `$a\=b\;\Rightarrow\;b\=a$', and the
transitive law `$a\=b\=c\;\Rightarrow\;a\=c$'. All these properties are
easy to prove, because any relation `$\=$'
that satisfies `$a\=b\iff f(a)=f(b)$' for some function~$f$ is
an equivalence relation. (In our case, $f(x)=x\bmod m$.) Moreover, we can
add and subtract congruent elements without losing congruence:
\begindisplay
a\=b\And c\=d\qquad\implies\qquad a+c\=b+d\qquad\pmod m\,;\cr
a\=b\And c\=d\qquad\implies\qquad a-c\=b-d\qquad\pmod m\,.\cr
\enddisplay
For if $a-b$ and $c-d$ are both multiples of $m$, so are
$(a+c)-(b+d)=(a-b)+(c-d)$ and $(a-c)-(b-d)=(a-b)-(c-d)$.
Incidentally, it isn't necessary to write `\tmod m' once for every
appearance of `$\,\=\,$'; if the modulus is constant, we need to
name it only once in order to establish the context. This is one of the
great conveniences of congruence notation.

Multiplication works too, provided that we are dealing with integers:
\begindisplay
a\=b\And c\=d\qquad\implies\qquad ac\=bd\qquad&\hbox{\tmod m}\,,\cr
&\hbox{integers $b,c$}.
\enddisplay
Proof: $ac-bd=(a-b)c+b(c-d)$. Repeated application of this
multiplication property now allows us to take powers:
\begindisplay
a\=b\qquad\implies\qquad a^n\=b^n\qquad\pmod m\,,
 \qquad&\hbox{integers $a,b$;}\cr
&\hbox{integer $n\ge0$}.
\enddisplay
For example, since $2\=-1$ \tmod3, we have $2^n\=(-1)^n$ \tmod3;
this means that $2^n-1$ is a multiple of~$3$ if and only if $n$~is even.

Thus, most of the algebraic operations that we customarily do with
equations can also be done with congruences. Most, but not all.
The operation of division is conspicuously absent. If $ad\=bd$
\tmod m, we can't always conclude that $a\=b$. For example,
$3\cdt2\=5\cdt2$ \tmod4, but $3\not\=5$.

We can salvage the cancellation property for congruences, however, in the
common case that $d$ and~$m$ are relatively prime:
\begindisplay
ad\=bd\;\iff\;a\=b\qquad&\hbox{\tmod m}\,,
\eqno\eqref|cancel-mod|\cr
&\hbox{integers $a,b,d,m$ and $d\rp m$}.
\enddisplay
For example, it's legit to conclude from $15\=35$ \tmod m that $3\=7$
\tmod m, unless the modulus~$m$ is a multiple of~$5$.

To prove this property, we use the extended gcd law \eq(|''|) again,
finding $d'$ and~$m'$ such that $d'd+m'm=1$. Then if $ad\=bd$ we can
"!congruences, division with" "!inverse modulo $m$"
multiply both sides of the congruence by $d'$, obtaining $ad'd\=bd'd$.
Since $d'd\=1$, we have $ad'd\=a$ and $bd'd\=b$; hence $a\=b$.
This proof shows that the number $d'$ acts almost like $1/d$ when
congruences are considered \tmod m; therefore we call it the
``inverse of~$d$ modulo~$m$.\qback''

Another way to apply division to congruences is to divide the modulus
as well as the other numbers:
\begindisplay
ad\=bd\!\!\pmod{md}\iff a\=b\!\!\pmod m\,,\quad\hbox{for $d\ne0$}.
\eqno\eqref|divide-mod|
\enddisplay
This law holds for all real $a$, $b$, $d$, and $m$, because it depends only
on the distributive law $(a\bmod m)d=ad\bmod md$: We have
$a\bmod m=b\bmod m\allowbreak
 \iff(a\bmod m)d=(b\bmod m)d\iff ad\bmod md=bd\bmod md$.
Thus, for example, from $3\cdt2\=5\cdt2$ \tmod4 we conclude that
$3\=5$ \tmod2.

We can combine \eq(|cancel-mod|) and \eq(|divide-mod|) to get a general
law that changes the modulus as little as possible:
\begindisplay
&ad\=bd\pmod{m}\cr
&\quad\iff a\=b\quad\Bigl({\rm mod}\,\,{m\over\gcd(d,m)}\Bigr)\,,
	\quad\hbox{integers $a,b,d,m$}.
\eqno\eqref|divide-gcd-mod|
\enddisplay
For we can multiply $ad\=bd$ by $d'$, where $d'd+m'm=\gcd(d,m)$; this
gives the congruence $a\cdt\gcd(d,m)\=b\cdt\gcd(d,m)$ \tmod m, which can
be divided by $\gcd(d,m)$.

Let's look a bit further into this idea of changing the modulus. If we
know that $a\=b$ \tmod{100}, then we also must have $a\=b$ \tmod{10},
or modulo any divisor of~$100$. It's stronger to say that $a-b$ is a multiple
of~$100$ than to say that it's a multiple of~$10$. In general,
\begindisplay
a\=b\pmod{md}\quad\implies\quad a\=b\pmod m\,,
 \quad\hbox{integer $d$},
\eqno
\enddisplay
because any multiple of $md$ is a multiple of $m$.

Conversely, if we know that $a\=b$ with respect to two small moduli,
\g Modulitos?\g
can we conclude that $a\=b$ with respect to a larger one? Yes; the
rule is
\begindisplay
&\hbox{$a\=b$ \tmod m}\And\hbox{$a\=b$ \tmod n}\cr
&\qquad\iff\hbox{$a\=b$ $\bigl($mod $\lcm(m,n)\bigr)$}\,,
	\qquad\hbox{integers $m,n>0$}.
\eqno\eqref|two-moduli|
\enddisplay
For example, if we know that $a\=b$ modulo $12$ and $18$, we can
safely conclude that $a\=b$ \tmod{36}. The reason is that if
$a-b$ is a common multiple of~$m$ and~$n$, it is a multiple of
$\lcm(m,n)$. This follows from the principle of unique factorization.

The special case $m\rp n$ of this law is extremely important, because
$\lcm(m,n)=mn$ when $m$ and~$n$ are relatively prime. Therefore we
will state it explicitly:
\begindisplay
&\hbox{$a\=b$ \tmod{mn}}\cr
&\iff\hbox{$a\=b$ \tmod m}\!\!\And\!\!\hbox{$a\=b$ \tmod n}\,,
	\quad\hbox{if $m\rp n$}.
\eqno\eqref|rp-moduli|
\enddisplay
For example, $a\=b$ \tmod{100} if and only if $a\=b$ \tmod{25} and
$a\=b$ \tmod{4}. Saying this another way, if we know $x\bmod25$
and $x\bmod4$, then we have enough facts to determine $x\bmod100$.
This is a special case of the {\it"Chinese Remainder Theorem"\/}
(see exercise~|chinese-remainders|), so called because it was
discovered by "Sun Ts\u u" in China, about {\sc a.d.}\thinspace350.

The moduli $m$ and $n$ in \thiseq\ can be further decomposed into
relatively prime factors