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

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

Uniqueness of Factorization

I start this chapter with a question which intrigue d me when I was

a studen t: is there a meaningful mathematical statement about ﬁ -

nite ﬁelds which is proven by induction on the characteristic of a

ﬁeld?

Finally and many years later I got a partial answer: a meaning-

ful (and exceptionally important) statement about prime num bers

proven by induction on the size of prime number in question. The

following proof o f a classical result belongs to Peter Walker [90].

His proof uses division with r emainder, but not the Euclidean algo-

rithm f or ﬁndin g the greatest common divisor of two integers. It is

an elegant illustration to our discussion of induction and recursion

in Chapter 5 since division with remainder, in the form of l ong divi-

sion, remains the most important e xample of a recursive algorithm

in the whole elementary mathematics.

16.1 Uniqueness of factorization

So, we are concerned with the following well known property of

prime numbers.

Theorem 14. For all primes p, p | ab implies p | a or p | b.

Proof. We say that a prime p is genuin e if it satisﬁes the condition

p | ab implies p | a or p | b

for all integers a and b. We shall prove by induction on p that all

primes p are genuine.

BASIS OF INDUCTION. Number 2 is a genuine prime number.

Indeed if a product of two integers is even then at least one of the

multiplicands is e ven.

INDUCTIVE STEP. Let p be the least non-genuine prim e number

so that p | ab but p does not divide a and does not divide b .

155

156 16 Uniqueness of Factorization

Using division with remainder, we can write

a = mp + c

and

b = np + d

where 0 6 c, d < p. Of course, p | ab, so p | cd. If either c = 0 or

d = 0 then p divides a or b as required. If not, then both c and d

are at least 1 and can be factor ized in to primes: c = p

···p

and

d = q

···q

(existence of factorization can be p roved earlier). Now

p | cd an d for some inte ger u we have

up = p

···p

···q

where all p

, q

are less than p and are therefore genuine prime

numbers. Since none of p

, q

can divide p, they divide u and can

be cancele d out one by one from the equation, leaving an obviously

contradictory equality vp = 1. 

Following the standard development, Theorem 14 has the well-

known corollary.

Theorem 15. The Fundamental Theorem of Arithmetic. If a

natural number n is written as product of primes in two ways,

n = p

···p

and n = q

···q

then k = l and ea ch p

equals one of q

Children tend to treat this fact as an experimental one —because

that is how this is happening in nature. Uniqueness of factorization

of polynomials, however, is far less obvious.

Barry Mazur emphasizes the role of Theorem 14 and points out

[63] that

Not only is this property a characterization of prime n umber, but it

reﬂects a fundamental feature of prime numbers; in fact, such an

important characterizing feature of primality that there is much

to be gained in our understanding if we simply turn the tables on

the the way we introduce primes into our discussion, and make

the following new

Turn-Around Deﬁnition: A prime nu mber is a number

that has the property that whenever it divides a product

of two numbers, it divides one (or both) of the numbers.

It is a special case of a well known maxim of working mathe-

maticians’ philosop hy:

Really good theorems are th os e that end their life as deﬁnitions.

But it is time to turn to discussion of a child’s p erception of pri-

mality and uniqueness of factorization.

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

 ALEXANDRE V. BOROVIK

16.2 Dia log with AL 157

16.2 Dialog with AL

I read about the Fundamental Theorem of Arithmetic when I was

about 10 or 11. I felt very uncomfortable about the proof of the The-

orem. The statement seemed so obvious that the proof appeared

to be ab solutely redundant, n ot adding anything to understanding

and making me worry that I was missing something. I would then

have been much happier to accept the Theorem as a self-evident

axiom.

AB ( the author of this book):

Perhaps, there is indeed an intrinsic danger in proving obvious

things. But, at the same age of 10 or 11, would you accept as obvi-

ous another, and closely related f act:

If a p rime number divides a product of two integers, it divides

one of them?

For example, 13 divides 46189 and 46189 = 209 ×221. Hence 13

should divide at least one of 209 or 221. (Indeed, 13 ×17 = 221 an d

11 × 19 = 209.)

And a more general question: what was approximately the

boundary where you started to feel that a proof could be us eful? I

feel that this el usive boundary is one of the most intriguing things

in mathematical education.

AL:

I would consider the statement “If a prime number di vides a prod-

uct of two integers, it divides one of them” as equally obvious to

FTA and n ot requiring any proof.

For me then, these statements were approximately at the same

level of transpa rency as commutativity of multiplication: you don’t

need to prove it, you just put coins into a rectangular sh ape on the

desk and you see that, indeed, multiplication is commutative, it is

a “law of nature”. Of course to get a similar feeling for FTA (or your

statement on product of two numbers) you need more playing with

numbers and that was what I was doing at th e time. The proof of

FTA appeared th en as an attempt to reduce one obvious thing to

other equally obvious th ings. For the contrast, approximately at

the same time I found the proof of the irrationality of square root

of 2 very exciting, it was a real proof!

The question about boundaries is a quite delicate one. In a

sense I still have this strange feeling about the proof of FTA, but

only when I think ab out it as a statement about “proper”, or “real”,

AL is male, Russian, was taught mathematics in Russian. Grad uated

from the Mechanical and Mathematical Department of Moscow State

University. PhD in (theoretical) computer science. He is now a lecturer

in computer science.

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

 ALEXANDRE V. BOROVIK

158 16 Uniqueness of Factorization

or “just” natural numbers in a semi-formal setting. In university,

of course I learned in a broader algebrai c and logical context and

that is then when I started to see that the proof of FTA does make

a sense. One may have Euclidean and non-Euclidean rings, and

FTA may have its explanation via more fundamental concepts. Or,

you may ﬁx some axiomatic system an d ask whether FTA is deriv-

able, or i ndependent—not that I was thin king about the particular

status of FTA at the time, but at least I saw the framework where

the proof of FTA does make sense.

AB:

And what woul d you say about an in tentionally elaborate and

beautiful proof of a self -evident statement, like Theorem 14?

AL:

Concerning the proof of the divisibility lemma by induction over

prime numbers, if I saw it when I was a schoolboy I would deﬁ-

nitely have the same reaction. The basis of induction is very simi-

lar to the statement, so, again, it is a reduction of “obvious” to “ob-

vious”. And I still feel a bit uncomfortable about the proof now, be-

cause of some vagueness in the distincti on b etween what is taken

for granted and what is to be proven. Ideally, I would like to see

an expli cit list of principles (axioms) needed to carry out the proof.

16.3 Generalizations

It is instructive to transfer the inductive proof Theorem 14 to poly-

nomials. Let F be a ﬁeld and F [x] the ring of polynomials over F

in single variable x. A polynomial is called irreducible if it cannot

be written as a product of two polynomials, both of which are of

strictly smaller degree. Notice that we can divide polynomials with

remainder and use induction on degree of polynomials to repeat the

proof of Theorem 14 in this new context.

Theorem 16. For all irreducible polynomials p(x),

p(x) | a(x)b(x)

implies p(x) | a(x) or p(x) | b(x).

Of course, this observation can be generalized further. Indeed,

degree of polynomial is an Euclidean function on the ring of po ly-

nomials F [x] over a ﬁeld F . Therefore the previo us observation is a

special case of a more general standard result of algebra:

Euclidean domain is a unique fa ctorization domain.

I leave details (with a brief reminder o f deﬁnitions) to the reader

as Exer c ise 16.2 at the end of this chapter.

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

 ALEXANDRE V. BOROVIK

16.4 The Fermat Theorem for polynomials 159

16.4 The Fermat Theorem for polynomials

To demonstrate the role of the uniqueness of factorization, we shall

prove a version of the Fermat Theor em—it will imme diately con-

tinue the them e started in Section 15.4 where we successfully

solved the Pythag orean Equation

+ b

= c

in terms of polynomials a, b, c ∈ Z[u, v].

Theorem 17. Let n > 2. There is no a, b, c in C[x] such that

+ b

= c

with coprime a and b, at least one of w hich is nonconstant.

Proof. The following p r oof was communicated to me by Oleg

Belegrade k. Suppose not. Choose a counterexample with

max{deg(a), deg(b)} > 0

and as small as possible. Let ǫ

, . . . , ǫ

be all nth complex roots of

−1. Then

= (a + ǫ

b)(a + ǫ

b) ···(a + ǫ

b).

As a and b are coprime, the p olynomials a + ǫ

b are nonzero and

pairwise coprime. Since C[x] is a unique factorization domain,

a + ǫ

b = f

for some f

∈ C[x]. For i 6= j, at least one of f

, f

is nonconstant;

otherwise a, b would be constant; also

0 < max{deg(f

), deg(f

)} < max{deg(a); deg(b)}.

Since all f

are in Ca+Cb, any three of them are linearly dependent

over C. Let, say,

αf

+ βf

= f

Then α 6= 0 or β 6= 0, and

(γf

)

+ (δf

)

= f

where γ

= α, δ

= β, wh ich contradicts to the choice of a, b. 

I leave it as an exercise to the reader to expand the statement

to the 2-v ariable case.

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

 ALEXANDRE V. BOROVIK

160 16 Uniqueness of Factorization

Exercises

Exercise 16.1 Prove Theorem 16 using ind uction on degree of the poly-

nomial p(x).

Exercise 16.2 Recall that a Euclidean function on a ring R i s a function

g : R → {0 } ∪ N

such that f or any two elements a and b 6= 0 in R, we can write

a = qb + r

with q, r ∈ R in such a way that we have either r = 0 or g(r) < g(b).

An Euclidean domain is a commutative ring without zero divisors (in-

tegral domain) and with an Euclidean function.

A deﬁnition of a uni que factorization domain is a bit longer since it

should take into account behavior of the ring of polynomial where non-zero

constant polynomia ls divide any other polynomial. To that end, we say an

element of a commutative ring R a unit if it is invertible. An element p ∈ R

is cal led irreducible if p cannot be written as a product of two non-units.

for a and b arbitrary elements of R. Two irreducible elements a and b are

associated if a divides b and b divides a (like, for example, polynomials x+1

and 2x + 2 in R[x]).

An integral domain R is a unique factorization domain if every non-

zero non-unit r ∈ R can be written as a product of irreducible elements of

r = p

···p

and this representation is unique in the following sense: if

, . . . , q

are irreducible an d

x = q

···q

then k = l and each p

is a ssociated to some q

Prove that an Euclidean domain is a unique factorization domain.

Exercise 16.3 Generalize Theorem 17 to polynomials over arbitra ry

ﬁelds [78, Lecture XIII]:

Let n > 2 and let K be a ﬁeld of characteristic not dividing n.

There is no a, b, c in K[x] such that

+ b

= c

with coprime a and b, at least one of which is nonconstant.

Exercise 16.4 Prove Fermat’s Theorem in the 2-variable case: there are

no non-constant polynomials x, y, z ∈ C[u, v] with coprime x and y that

satisfy

+ y

= z

for some n > 2.

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

 ALEXANDRE V. BOROVIK

Pedagogical Intermission: Factorization

One of my correspo ndents, Frances Bell kindly contributed the fol-

lowing observation:

One of the things that I learned from my fairly brief experience in

teaching maths in school was that many children need to switch

between rote an d constructive learning, and to rehearse what they

know in different settings. For example, it would be very difﬁcult

for a child to factorize in algebra without ﬂuency in arith metic

factors. My aunt studied algebra in her late seventies (having left

school at 14) and found factorization fai rly easy because of her

excellent arithmetic skills unlike her young classmates who lack

proﬁciency with their ti mes tables.

My husba nd told me how the old UK money system LSD

with

240 pennies in a pound (and even half pennies and farthings) con-

tained so many useful factors that children could relate to real

coins.

Frances Bell refers to an intimate re lation between factor iza-

tion in algebra and in arithmetic which manifests itself at a sub-

conscious level in schoolchildren’s mathematical activities. The is-

sue becomes even more interesting when children h ave to explicate

this relation. Of cour se, it c ould be a very challenging task. Here

are two examples from “olympiad” or “extension” type pro blems:

(a) The number

100000000003000000000000700000000021

is the product of two smaller natural nu mbers. Find them.

(b) How many of the integers

11, 1001, 100001, 10000001, . . .

are primes?

Due to one of the many idiosyncrasies of the traditional British English,

LSD is an a bbreviation for “pounds, shillings, pence”.

161

162 17 Pedagogical Intermission: Factorization

Potentially able students need to be challenged to think ﬂexibly

and to make connections—such as the simple (but logically subtle

and elusive) connection here between factorization in algebra and

in integer arithme tic.

The ﬁrst of the two problems was chosen from a ﬁrst year uni-

versity course on number theory and cryptography that I taught

for some years in Manchester. When building their own toy im-

plementations of the RSA cryptographic system, students have to

produce, with the help of the MATLAB software package, products

n = pq of two large p rime numbers p and q, sufﬁciently big so that

n cannot be factorized by the standard routines of MATLAB. A sur-

prising number of students end up with nu mbers like the one in the

problem. When explicitly prompted, only two or three students in

a class of 30 could see why inte gers such as that in (a) are instantly

factorizable into two smaller factors.

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

 ALEXANDRE V. BOROVIK

Being in Control

Science is most fun when it’s stil l in its infancy.

Vilayanur Ramachandran [370, p. xiv]

To avoid any possible misunderstanding, I feel that I have to

make the following qualifying remarks:

• I am neither a philosopher nor a psychologist.

• This book is not about philosophy of mathematics, it is about

mathematics.

• This book is not about psychology of mathematics, it is about

mathematics.

• This book is not about mathematical education, it is about

mathematics.

In this chapter, I encroach onto the sacred grounds of develop-

mental psychology, w hich was not my original intention. The chap-

ter was not part of the draft p lan of the book. But when I started

to receive childhood testimonies from my correspondents, I discov-

ered a recurrent theme in the stories which I tentatively labeled

as being in control (I use the words suggested by Leo Harrington,

see the next section). I decided to simply report these stories with

minimal comme nt on m y part.

18.1 Leo Harrington: Who is in control?

As I have already said, my thanks go to Leo Harrington

who

helped me to cry stallize a them e which goes through many child-

hood stories: a child’s instinctive urge to be in contro l of the math-

LH is male, American, professor of mathematical logic in an American

university.

163

164 18 Bein g i n C ontrol

ematics he or she is being taught. But LH’s story is best told in his

own word s:

I have three stories that I think of as related. My stories may not

be of th e kind you want, since they involve no mathematics; but for

me they involve some very primitive meta-mathemati cs, namely:

who is in control of the meta-mathematics.

This is my mother’s memory, not mine. When I was three my

mother pushed my baby cart and me to a store. At the time prices

were given by little plastic numbers below the item. When we

got home my clothes revealed lots of p lastic numbers. My mother

made me return them.

When I was nine in third grade I came home from school with

a card full of nu mb ers which I had been told to memorize by to-

morrow. I s at on my bed crying; the only time I ever cried over an

assignment. The card was the multiplication table.

When I was around twelve, i n grade school, a magazine article

said how many (as a decimal number) babies were born in the

world each second. The teacher asked for someone to calculate how

many babies were born each year. I volunteered and went to th e

blackboard. When I had found how many babies were born each

day, the number had a .5 at the end. The teacher said to forget the

.5. I erased the .5.

One of the components of the emotional and ae sthetic attrac-

tiveness of mathematics is the speciﬁc feeling of being in control

of something intangible, elusive, complex, and the self-conﬁdence

that grows from that feeling. In this chapter, I assemble stories

about being, or not be in g, in control of mathematics and of rela-

tions with other people arising from mathematics. Children can be

surprisingly sensitive to issues of control.

A partial explanation of this phenom enon touches the autistic

spectrum and the peculiarly skewed positioning of many mathe-

maticians on it. Simon Baro n-Cohen (famous for his suggestion

that mathematicians should avoid marriages between them be-

cause of a higher risk of producing autistic offspring) emphasizes

that [244, p. 139]:

People with autism not only notice such small details and some-

times can retrieve this information in an exact manner, but they

also love to predict and control the world.

Remarkably, the memories that are described by mathemati-

cians as their ﬁrst memor ies of mathematics are frequently memo-

ries of attempting to contro l the world.

Listen to Victor Maltcev:

I remember three episodes of a mathematical nature in my child-

hood:

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

 ALEXANDRE V. BOROVIK