Mathematical Conversations

Multicolor Problems, Problems in the Theory of Numbers, and Random Walks

E. B. Dynkin, V. A. Uspenskii

• Publisher: Dover Publications
• Year: 2013
• Print ISBN: 9780486453514
• eBook ISBN: 9780486154916
• Topic: Mathematics
• Subtopic: Algebra
• Index: Mathematics

Combining three books into a single volume, this text comprises Multicolor Problems, dealing with several of the classical map-coloring problems; Problems in the Theory of Numbers, an elementary introduction to algebraic number theory; and Random Walks, addressing basic problems in probability theory.
The book's primary aim is not so much to impart new information as to teach an active, creative attitude toward mathematics. The sole prerequisites are high-school algebra and (for Multicolor Problems) a familiarity with the methods of mathematical induction. The book is designed for the reader's active participation. The problems are carefully integrated into the text and should be solved in order. Although they are basic, they are by no means elementary. Some sequences of problems are geared toward the mastery of a new method, rather than a definitive result, and others are practice exercises, designed to introduce new concepts. Complete solutions appear at the end.

SECTION TWO
Problems in the Theory of Numbers

1. The Arithmetic of Residue Classes

1. ARITHMETIC, MODULO m, OR m-ARITHMETIC¹

When we add two one-digit numbers we obtain either a onedigit number, for example,

or a two-digit number,

We now consider only the last digit in the case of two-digit sums, and we write

With this new definition of addition, the sum of two one-digit numbers is always a one-digit number.

When we multiply two one-digit numbers we likewise obtain either a one-digit number:

or a two-digit number:

Again, we shall consider only the last digit of a two-digit product, and we write

With this new definition of multiplication, the product of two onedigit numbers is always a one-digit number. Though the operations introduced here are different from those that we call ordinary addition and multiplication, the formulas of ordinary algebra that contain only the symbols for addition and multiplication and an arbitrary number of parentheses hold also for the new operations.² In particular, the following formulas hold:

as well as the formulas

and others. Hence, the use of the customary symbols cannot lead to a misunderstanding.

In this way, we have constructed a new arithmetic, which differs from ordinary arithmetic and yet resembles it in many respects. This new arithmetic will be helpful in the solution of many problems in ordinary arithmetic and algebra.

We have begun to develop the arithmetic of residue classes, modulo 10, or more briefly, 10-arithmetic. It contains only the numbers 0, 1, 2, 3, 4, 5, 6, 7, 8, 9. Let us set up the addition and multiplication tables of this 10-arithmetic:

We make one additional remark. Suppose that we have any equality of ordinary arithmetic which contains, besides numbers, only addition sighs, multiplication signs, and parentheses, and we replace every number by its last digit. We then obtain an equation that holds in 10-arithmetic. For example, we can obtain from the equalities of ordinary arithmetic,

the equalities of 10-arithmetic,³

Problem 1. Exh...

Table of contents

• Cover
• Title Page
• Copyright Page
• Contents
• Section I: Multicolor Problems
• Section II: Problems in the Theory of Numbers
• Section III: Random Walks