Andy Liu - Arithmetical Wonderland

Arithmetical Wonderland

c 2015 by

The Mathematical Association of America, Inc.

Library of Congress Catalog Card Number 2015950206

Print edition ISBN 978-0-88385-789-2

Electronic edition ISBN 978-1-61444-119-9

Printed in the United States of America

Current Printing (last digit):

Arithmetical Wonderland

Andrew C. F. Liu

University of Alberta

Published and Distributed by

The Mathematical Association of America

Council on Publications and Communications

Jennifer J. Quinn, Chair

Committee on Books

Fernando Gouvea, Chair

Classroom Resource Materials Editorial Board

Susan G. Staples, Editor

Jennifer Bergner

Caren L. Diefenderfer

Christina Eubanks-Turner

Christopher Hallstrom

Cynthia J. Huffman

Brian Paul Katz

Paul R. Klingsberg

Brian Lins

Mary Eugenia Morley

Philip P. Mummert

Darryl Yong

CLASSROOM RESOURCE MATERIALS

Classroom Resource Materials is intended to provide supplementary classroom material for studentslaboratory exercises, projects, historical information, textbooks with unusual ap-proaches for presenting mathematical ideas, career information, etc. 101 Careers in Mathematics, 3rd edition edited by Andrew Sterrett Archimedes: What Did He Do Besides Cry Eureka?, Sherman Stein Arithmetical Wonderland, Andrew C. F. Liu

Calculus: An Active Approach with Projects, Stephen Hilbert, Diane Driscoll Schwartz, Stan Seltzer, John Maceli, and Eric Robinson

Calculus Mysteries and Thrillers, R. Grant Woods

Conjecture and Proof, Mikl os Laczkovich

Counterexamples in Calculus, Sergiy Klymchuk

Creative Mathematics, H. S. Wall

Environmental Mathematics in the Classroom, edited by B. A. Fusaro and P. C. Kenschaft Excursions in Classical Analysis: Pathways to Advanced Problem Solving and Undergraduate

Research, by Hongwei Chen

Explorations in Complex Analysis, Michael A. Brilleslyper, Michael J. Dorff, Jane M. McDougall, James S. Rolf, Lisbeth E. Schaubroeck, Richard L. Stankewitz, and Kenneth Stephenson

Exploratory Examples for Real Analysis, Joanne E. Snow and Kirk E. Weller Exploring Advanced Euclidean Geometry with GeoGebra , Gerard A. Venema Game Theory Through Examples , Erich Prisner

Geometry From Africa: Mathematical and Educational Explorations, Paulus Gerdes The Heart of Calculus: Explorations and Applications, Philip Anselone and John Lee Historical Modules for the Teaching and Learning of Mathematics (CD), edited by Victor Katz

and Karen Dee Michalowicz

Identication Numbers and Check Digit Schemes, Joseph Kirtland

Interdisciplinary Lively Application Projects, edited by Chris Arney Inverse Problems: Activities for Undergraduates, Charles W. Groetsch Keeping it R.E.A.L.: Research Experiences for All Learners, Carla D. Martin and Anthony

Tongen

Laboratory Experiences in Group Theory, Ellen Maycock Parker

Learn from the Masters, Frank Swetz, John Fauvel, Otto Bekken, Bengt Johansson, and Victor Katz

Math Made Visual: Creating Images for Understanding Mathematics, Claudi Alsina and Roger B. Nelsen

Mathematics Galore!: The First Five Years of the St. Marks Institute of Mathematics, James Tanton

Methods for Euclidean Geometry, Owen Byer, Felix Lazebnik, and Deirdre L. Smeltzer Ordinary Differential Equations: A Brief Eclectic Tour, David A. Sanchez Oval Track and Other Permutation Puzzles, John O. Kiltinen

Paradoxes and Sophisms in Calculus, Sergiy Klymchuk and Susan Staples A Primer of Abstract Mathematics, Robert B. Ash

Proofs Without Words, Roger B. Nelsen

Proofs Without Words II, Roger B. Nelsen

Rediscovering Mathematics: You Do the Math, Shai Simonson

She Does Math!, edited by Marla Parker

Solve This: Math Activities for Students and Clubs, James S. Tanton

Student Manual for Mathematics for Business Decisions Part 1: Probability and Simulation, David Williamson, Marilou Mendel, Julie Tarr, and Deborah Yoklic

Student Manual for Mathematics for Business Decisions Part 2: Calculus and Optimization, David Williamson, Marilou Mendel, Julie Tarr, and Deborah Yoklic

Teaching Statistics Using Baseball, Jim Albert

Visual Group Theory, Nathan C. Carter

Which Numbers are Real?, Michael Henle

Writing Projects for Mathematics Courses: Crushed Clowns, Cars, and Coffee to Go, Annalisa Crannell, Gavin LaRose, Thomas Ratliff, and Elyn Rykken

MAA Service Center

P.O. Box 91112

Washington, DC 20090-1112

1-800-331-1MAA FAX: 1-301-206-9789

Contents

Preface to a Preliminary Edition ix

Introduction xi

0 Review of Arithmetic

0.1 Counting Numbers

0.2 Integers

0.3 Inequalities

0.4 Extras

1 Divisibility

1.1 Basic Properties of Divisibility

1.2 The Arithmetic of Divisibility

1.3 Divisibility Problems

1.4 Extras

2 Congruence

2.1 The Division Algorithm

2.2 Basic Properties and Arithmetic of Congruence

2.3 Congruence and Divisibility

2.4 Extras

3 Common Divisors and Multiples

3.1 Greatest Common Divisors and the Euclidean Algorithm

3.2 Relatively Prime Numbers

3.3 Least Common Multiples

3.4 Extras

4 Linear Diophantine Equations

4.1 Bezoutian Algorithm

4.2 Homogeneous and Non-homogeneous Equations

4.3 Linear Diophantine Problems

4.4 Extras

viii Contents

5 Prime Factorizations

5.1 Prime and Composite Numbers

5.2 Fundamental Theorem of Arithmetic

5.3 Applications of the Fundamental Theorem of Arithmetic

5.4 Extras

6 Rational and Irrational Numbers

6.1 Fractions

6.2 Decimals

6.3 Real Numbers

6.4 Extras

7 Numeration Systems

7.1 Arithmetic in Other Bases

7.2 Conversion between Bases

7.3 Applications of Other Bases

7.4 Extras

Appendix: A Legacy of Martin Gardner

Solution to Odd-numbered Exercises

Index

About the Author

Preface to a Preliminary Edition by Martin Gardner

Andy Liu, since 1980 a distinguished professor of mathematics at the University of Alberta, Edmonton, Canada, is one of the worlds leading experts in problem solving. He is also noted for what has been called a unique ability to present difcult concepts in a clear and logical manner. His extremely bright young pupils, of both genders, are constantly winning prizes in tough mathematics competitions.

Andy has won many awards, the most recent being the 2003 Adrien Pouliot Award from the Canadian Mathematical Society for his contribution to Canadian mathematics education, and the 2004 Deborah and Franklin Tepper Haimo Award from the Mathematical Association of America for his excellence in mathematics teaching. He has edited a Book Review column for Crux Mathematicorum and a Problem Corner for Math Horizons .

Andy has nally drawn upon his vast experience as a teacher of elementary mathematics to produce the textbook you now holda book that covers everything a talented student would want to know about arithmetic. The books wealth of stimulating problems starts with divisibility testssimple rules for every integer up to 12, except 7to a nal chapter on numeration systems. Along the way are topics not usually found in such textbooks, such as the chapter on Diophantine Equations. Every problem is clearly stated, and every answer and every proof easy to understand.