Borovik A. Shadows of the Truth: Metamathematics of Elementary Mathematics

Подождите немного. Документ загружается.

13.3 A dialogue with Peter McBride 135

13.3 A dialogue with Peter McB ride

The previous se c tio n ﬁrst appeared as a post in my blog, and Peter

McBride responded to it with the following commen t:

The examples of student “errors” shown on the post you linked to

are, in f act, examples of the medieval-craft nature of pure math-

ematics, as noted 30 years ago by the computer scientist, Edsger

Dikstra. The discipl ine still has no systematic, agreed, industrial-

strength, notion of semantics: everything is still ad hoc. For in-

stance, in some cases it is correct to cancel the symbol “n” above

and below a fra ction line; in other cases ( when, for example, the

symbol “n” is embedded inside a “sine” function), it is not. Why

there is difference here is never explained, but bright students

somehow master it implicitly.

It is easy, very easy, for people who long ago mastered the un-

written and n on-formal semantics of pure mathematics to forget

how hard in fact this mastery is to acquire. For the rest of human-

ity, the lack of systematic treatment of the meaning and treatment

of apparently-random scratches on paper is part of what makes

the subject so difﬁcult to learn.

And that was my response:

Dear Peter,

what is actually tau ght to children when we think that we

teach them mathematics?

An analogy with (much younger) children mastering their

mother tongue could be helpful : we do not teach kids grammar,

they somehow pick the gra mmar themselves. Moreover, it is li kely

to be a disaster to try to teach formal grammar to three or four

years old kids. The same is happening in mathematics: even at

the elementary (primary) school level, mathematics is saturated

with sophisticated structures and rules wh ich are not made ex-

plicit to children. Children have to somehow pick these rules

from their teachers’ talk and their textbooks. (Their teachers, as

a rule, also have no explicit knowledge.) However, “systematic,

agreed, industrial-strength, notion of semantics” (and lambda cal-

culus could be a useful fragment of such formalization) will not

help child ren. I am not even certain that it could help teachers.

It is of no use to most working mathematicians, either—because

mathematicians have been selected by their ability to pick and fol-

low unstated rules of formal systems and conditioned do not care

much about people who cannot follow “the rules of the game”.

But we have to understand the “atomic” (and frequently un-

spoken) structures an d procedures of mathematical cognition for

the sake of health of our profession and our professi onal commu-

nity. In effect, the problem as described by you is about relati ons

between the mathematical community and non-mathematicians.

Peter McBride:

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

136 13 M athematics of Finger-Pointing

Well, Alexandre, I guess we disagree profoundly about this. I b e-

lieve students of mathematics, at whatever age, would beneﬁt

from all aspects of what they are being taught being made ex-

plicit, from the outset. I am sure, however (and this despite my

University Medal in the subject), that on this issu e I am in a mi-

nority among people with a university mathematics education. As

I said, it seems very easy for people who have somehow absorbed

the hidden rules without being taught them explicitly, to think

that everyone can do likewise. Everyone can’t, a nd no one should

have to.

The rules, and all of them, should be made explicit. But that

would mean mathematicians leaving their craft-based processes in

the pa st where they belong, and actually systematizing the disci-

pline. Hand-waving is easier. And, as a social anthropologist would

note, having unwritten rules allows an elite to keep its club small

and select.

What should be my response to that? In Chapter 6, What is a

minus sign anyway? I quoted there John Baldwin who said about

the ambiguity of the “minus” symbol as used in elementary mathe-

matics:

It is quite plausible that this is a distinction one should not make

for teachers or at leas t the question should be at what level you

want them to be aware of it.

And I agree with John Baldwin: it is unlikely that, as Peter

McBride states,

students of mathematics, at wh atever age, would beneﬁt from all

aspects of what they are being taught being made explicit, from the

outset.

We have to be realists: we have ﬁrst to teach the teachers—and this

is already a highly non-trivial task. I will put it that way: to m ake

“all aspects of what children are taught explicit”

is possible; but even if it was de sirable it wo uld require time and a

huge in vestment of political will and money. It is absolute ly unre-

alistic in the present sociopolitical climate.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

Numbers and Functions

14.1 Chinese Remainder Theorem

14.1.1 History

Some stories about mathematics are repeated again and again,

and, to save time, I simply qu ote from Cut the Knot

“According to D. Wells [ 91], the following problem was posed by

Sun Tsu Suan- Ching (4th century AD):

There are certain things whose number is unknown. Re-

peatedly divi ded by 3, the remainder is 2; by 5 the remain-

der is 3; and by 7 the remainder is 2. What will be the

number?

Oystein Ore [ 71] mentions another puzzle with a dramatic el-

ement from Brahma-Sphu ta-S i ddhanta (Brahma’s Correct Sys-

tem) by Brahmagupta (born 598 AD):

An old woman goes to market and a horse steps on her

basket and crushes the eggs. The rider offers to p ay for the

damages and asks her how many eggs she had brought.

She does not remember the exact number, but when she

had taken them out two at a time, there was one egg left.

The same happened when she picked them out three, four,

ﬁve, and six at a time, but when she took them seven at a

time they came out even. Wha t is the smallest number of

eggs she could have had?

Problems of this kind are all examples of what universally be-

came known as the Chinese Remainder Theorem. In mathematical

parlance the problems can be stated as ﬁnding x, given its remain-

ders of division by several numbers m

, m

, . . . , m

:”

http://www.cut-the-knot.org/blue/chinese.shtml

137

138 14 Numbers a nd Functions











x ≡ b

(mod m

)

x ≡ b

(mod m

)

(14.1)

In this bo ok, we shall treat the case when m

, m

, . . . , m

are

pairwise relatively prime:

, m

) = 1 for i 6= j.

Notice that Br ah magupta’s problem is not covered by this case; I

leave that problem as an exercise to my readers.

14.1.2 Simultaneous Congruences

We aim to prove one of the olde st theorems of Number Theory. But

ﬁrst we need a simple property of simultaneous cong ruences.

Theorem 12. x ≡ y (mod m

) for i = 1, 2, . . . , r if and only if

x ≡ y (mod [m

, m

, . . . , m

]).

Here

, m

, . . . , m

]

denotes the least common multiple of m

, . . . , m

Proof.

If x ≡ y (mod m

) for i = 1, 2, . . . , r, then

| (y − x) for i = 1, 2, . . . , r.

That is, y −x is a common multiple of m

, m

, . . . , m

, and therefore

, m

, . . . , m

] | (y − x).

This implies

x ≡ y (mod [m

, m

, . . . , m

]).

On the other hand, if

x ≡ y mod [m

, m

, . . . , m

]

then

x ≡ y (mod m

since

| [m

, m

, . . . , m

] | x − y.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

14.1 Chinese Remainder Theorem 139

14.1.3 Algorithm

Theorem 13. C hinese Remainder Theorem. Let

, m

, . . . , m

denote k positive integers that are relatively prime in pairs and let

, b

, . . . , b

denote any k integers. Then the c ongruences (14.1) have commo n

solution s. Any two solutions are congruent mo dulo m

···m

Proof.

Writing

M = m

···m

we see that

is an integer and that



, m



= 1.

Therefore, by the Euclid’s Algorithm [EXPAND!], there are in-

tegers a

such that





≡ 1 mod m

Clearly, if i 6= j, then





≡ 0 (mod m

Now we de ﬁne x

j=1

. (14.2)

Then we have

≡

j=1

≡

≡ a

(mod m

so that x

is a common solution of the original congruences.

If x

and x

are both c ommon solutions of

x ≡ b

(mod m

), i = 1, 2, . . . , k,

then x

≡ x

(mod m

) for i = 1, 2, . . . , k and hence x

≡ x

(mod M) by Theorem 12. This completes the proof. 2

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

140 14 Numbers a nd Functions

14.1.4 Example

Returning to Sun Tsu Suan-Ching, w e can now write a general for-

mula for solving systems of simultaneous congruences











x ≡ b

(mod 3)

x ≡ b

(mod 5)

x ≡ b

(mod 7)

(14.3)

Our gene r al solution in this case is j ust

x ≡ 5 · 7 · a

· b

+ 3 · 7 · a

· b

+ 3 · 5 · a

· b

(mod 3 · 5 · 7),

where a

, a

are chosen to satisfy











5 · 7 · a

≡ 1 (mod 3)

3 · 7 · a

≡ 1 (mod 5)

3 · 5 · a

≡ 1 (mod 7)

so we can take (in this simple example, by direct inspection, in a

general case—using Euclid’s Algorithm)

= 2, a

= 1, a

= 1

and have the answer

x ≡ 70b

+ 21b

+ 15b

(mod 105).

With the original values b

= 2, b

= 3, b

= 2 we get

x ≡ 70 · 2 + 21 · 3 + 15 · 2 = 233 (mod 105).

The smallest o f in ﬁnitely many positive solu tions is x = 23.

14.2 The Lagrange Interpolation Formula

Let us n ow perform some no tational tricks. The formula





≡ 1 (mod m

)

means that a

is the multiplicative inverse of M/m

modulo m

; let

us denote it





−1

mod m

Then the solution for the Chinese Remainder Problem (14.3) can

be written as

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

14.2 The Lagrange Interpolation Formula 141

j=1





−1

mod m

· b

. (14.4)

Now let us turn our attention to the Lagrange Interpolation Prob-

lem: given k distinct points a

, . . . , a

, k > 2, ﬁnd a polynomial f(t)

of degree k − 1 which takes at these points given values b

, . . . , b

correspondingly:











f(a

) = b

f(a

) = b

(14.5)

And here, remainders appear at the scen e. If we divide a poly-

nomial f (t) by degree one polynomial t − a w ith remainder,

f(t) = (t − a)g(t) + b,

we instantly see that the value f(a) of f (t) at t = a is b:

f(a) = (a − a)g(a) + b = b.

Therefore, using the “modulus” notation for equality of remainders

borrowed from number theory, we can rewrite our problem (14.5)











f(t) ≡ b

(mod t − a

)

f(t) ≡ b

(mod t − a

)

(14.6)

We rewrote the Lagrange Interpolation Problem exactly in the

same form as the Chinese Reminder Proble m. You would agree that

it is natural to try to solve the former by em ulating the solution

(14.4) of the latter. To that end, d enote

(t) = t − a

, . . . , m

(t) = t − a

and

M(t) = m

(t) ···m

(t) = (t − a

) ···(t − a

We have

M(t)

(t)

= m

(t) ···m

j−1

(t) · m

j+1

(t) · m

(t)

= (t − a

) ···(t − a

j−1

) · (t − a

j+1

) ···(t − a

)

(notice that, in the expressions on the righ t hand side, the terms

(t) and (t − a

) are absent).

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

142 14 Numbers a nd Functions

The remainder of the po lynomial

M(t)

(t)

modulo t−a

is its value

at t = a

M(t)

(t)

≡



M(t)

(t)



t=a

(mod t − a

)

= [(t − a

) ···(t − a

j−1

) · (t − a

j+1

) ···(t − a

)]

t=a

= (a

− a

) ···(a

− a

j−1

) · (a

− a

j+1

) ···(a

− a

)

Moreove r, the remainders upon division by t −a

are just real num-

bers, and their m ultiplicative inverses are nothing but ordinary in-

verses; hence



M(t)

(t)



−1

mod t−a

− a

) ···(a

− a

j−1

) · (a

− a

j+1

) ···(a

− a

)

Now we can assemble all bits of formula (14.4) together:

f(t) =

j=1

(t − a

) ···(t − a

j−1

) · (t − a

j+1

) ···(t − a

)

− a

) ···(a

− a

j−1

) · (a

− a

j+1

) ···(a

− a

)

· b

(14.7)

This is the famous Lagrange Interpolation Formula.

14.3 Numbers as functions

We have seen that the Chinese Remainder Theorem and the La-

grange Interpo lation Formula are the same procedure applied to

two dif ferent rings: the ring Z of integers in the f ormer and the

ring R[t] of polyno mials in one variable in the latter.

It is essential in the set-up of the Lagrange Interpolation For-

mula that polynomials are treated as functions from R to R: for

every point a ∈ R, there is a value f (a) of polynomial f (t) at t = a.

The map

: R[t] → R

f(t) 7→ f (a)

is a homomorph ism: it preserves addition and multiplication:

(f(t) + g(t)) = v

(f(t)) + v

(g(t))

(f(t) · g(t)) = v

(f(t)) · v

(g(t)),

or, in more elemen tary notation,

[f + g](a) = f (a) + g(a), [f · g](a) = f (a) · g(a).

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

14.3 Numbers as functions 143

It is important for modern understanding of algebra and number

theory that integ ers can be treated as a kind of function. For the

domain, it is convenien t to take the set of all prime nu mbers, it

even has special notation Spec Z. The range is trickier: there is no

single range, but at every “point” p ∈ Spec Z , the “function” m ∈ Z

takes values in the ﬁeld of remainders Z/pZ modulo p:

m : p 7→ “m (mod p)”.

It does not matter much that ﬁelds vary from one “point” to an-

other: we multiply and add functions pointwise!

[In a later chapter, I will try to use this analogy be-

tween numbers and functions and try to explain what Non-

Standard Real Numbers and Non-Standard Analys is are.]

Exercises

We can use the Chines e Remainder T heorem to prove an important prop-

erty of Euler’s function φ(n). Recall that φ(n) is deﬁned for natural num-

bers n and is equal to the number of natu ral numbers which a re smaller

or equal than n and coprime to n. In particular,

φ(1) = 1, φ(2) = 1, φ(3) = 2, φ(4) = 2, φ(5) = 4, φ(6) = 2.

Exercise 14.1 Let m and n be any two positive, relatively prime numbers.

Then

φ(nm) = φ(n)φ(m).

Exercise 14.2 Give the following interpretation of the Chinese Remainder

Theorem:

If m

and m

are relatively prime then

Z/m

Z ≃ Z/m

Z × Z/m

(direct product of rings).

Exercise 14.3 Give examples showing that if the moduli m

, . . . , m

are

not relatively prime in pairs, then there may be not any solution of the con-

gruences.

Exercise 14.4 Generalise the Chinese Remainder Theorem to the case of

non-relatively prime moduli m

, . . . , m

and solve Brahmagupta’s Problem.

Exercise 14.5 (David Pierce) Make Figure 14.1 i nto a proof of the Chinese

Remainder Theorem for two moduli:

If (m

, m

) = 1 then every system of two congruences

(

x ≡ b

(mod m

)

x ≡ b

(mod m

)

has a solution.

SHADOWS OF THE TRUTH VER. 0.813 23-DEC-2010/7:19

 ALEXANDRE V. BOROVIK

Fig. 14. 1 . Make this diagram into a proof of the Chinese Remainder Th e-

orem (Exercise 14.5). See R. P. Burn, “ Pathways to Number Theory”

(CUP).