“Everything is number.”

—Pythagoras, sixth century B.C.

A question is sometimes asked if mathematics is discovery or invention. Certainly many of the definitions were devised by mathematicians. However, the relationships of the terms and the characterizations are not arbitrary or purely descriptive but proven by logic.

The logic of mathematics and the logic of programming are similar, and improving skills in one will help the other. The beauty of a proof is similar to the beauty of a program.

Elementary number theory is a special branch of mathematics in that many of the proven theorems and many of the conjectures can be stated so that anyone with an elementary knowledge of algebra can understand them.

This textbook was developed to be used in a college mathematics and computer science program. However, it can be used at institutions with separate mathematics and computing majors. The material in this book is also suitable for a course at the high school level. The clever and esthetic argument drawn from this text will enhance a student’s admiration for the power of high school algebra.

The first author fell in love with mathematics in the fifth grade. The teacher said that in order to divide by a fraction, we must multiply by its reciprocal. Thus, to divide 8 by 2/3, we multiply by 3/2, obtaining 8 × 3/2 = 12. When asked why this works, the teacher replied, “Just do it.” That evening, the first author reasoned as follows. To divide 8 by 1/3, we clearly multiply by 3, since there are three “thirds” in each “one.” Thus, if each guest eats one third of a pizza pie, then 8 pies can feed 8 × 3, or 24 guests. On the other hand, if each guest eats two thirds of a pie, that is, if each guest eats twice as much, then only half as many guests (12 guests) can be fed. Thus, to divide 8 by 2/3, that is, to determine how many “2/3 of a pie” there are in 8 pies, we wind up multiplying by 3 and dividing by 2. In other words, we multiply by 3/2.

Every integer has its secret! The cube 125 (i.e., 5 × 5 × 5) is the sum of two squares in two different ways: 125 = 100 + 25 = 121 + 4. The number 55 is the sum of the first 10 numbers: 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = (1 + 10) + (2 + 9) + (3 + 8) + (4 + 7) + (5 + 6) = 5 × 11 = 55. The innocent-looking number, 16, is the only number that can be written as a^b and b^a where a and b are distinct positive integers: 16 = 2⁴ = 4². The list of wonders never ceases. Nor do the open questions that still challenge the entire world community of mathematicians. Is every even number except 2 the sum of two prime numbers? (A prime number is divisible only by itself and by 1.) We have 4 = 2 + 2, 6 = 3 + 3, 8 = 5 + 3, 10 = 7 + 3, 12 = 7 + 5, but no one knows whether the general conjecture made over 200 years ago is true! Is there always a prime number between consecutive squares? No one knows.

It is our hope that this book will inspire some students to dedicate themselves to mathematics and/or computer science. Perhaps we can pass the torch to some young reader (though neither author intends to relinquish it just yet!). At any rate, enjoy this book, and please do the exercises.

The only prerequisites to understanding the material presented here are high school algebra, very basic programming skills, and a willingness to work. Read with pencil and paper handy. When in doubt, you should reread, recalculate, and rethink to your heart’s content. In fact, scribble in the margins! In my opinion, that’s what they are there for. A marginal comment written by the great seventeenth-century French mathematician Fermat sparked an exciting and productive 300-year long search for a proof that ended within the last decade. Fermat asserted, without proof, that while the sum of two squares is often a square (16 + 9 = 25), this is never true for cubes, fourth powers, fifth powers, etc. In other words, the equation aⁿ + bⁿ = cⁿ has no solution in positive integers when n > 2.

Do also try the programming exercises. You can study the sample programs or try first on your own. It is like having a silent partner with perfect abilities at following directions.

Thanks to Anthony Delgado, Tim Bocchi, and Brian Phillips for their helpful suggestions.

Enjoy the adventure.