Elementary Number Theory with Programming E-Book

Marty Lewinter

• Herausgeber: John Wiley & Sons
• Kategorie: Wissenschaft und neue Technologien
• Sprache: Englisch

Seitenzahl: 341

Veröffentlichungsjahr: 2015

Beschreibung

A highly successful presentation of the fundamental concepts of number theory and computer programming

Bridging an existing gap between mathematics and programming, Elementary Number Theory with Programming provides a unique introduction to elementary number theory with fundamental coverage of computer programming. Written by highly-qualified experts in the fields of computer science and mathematics, the book features accessible coverage for readers with various levels of experience and explores number theory in the context of programming without relying on advanced prerequisite knowledge and concepts in either area.

Elementary Number Theory with Programming features comprehensive coverage of the methodology and applications of the most well-known theorems, problems, and concepts in number theory. Using standard mathematical applications within the programming field, the book presents modular arithmetic and prime decomposition, which are the basis of the public-private key system of cryptography. In addition, the book includes:

• Numerous examples, exercises, and research challenges in each chapter to encourage readers to work through the discussed concepts and ideas
• Select solutions to the chapter exercises in an appendix
• Plentiful sample computer programs to aid comprehension of the presented material for readers who have either never done any programming or need to improve their existing skill set
• A related website with links to select exercises
• An Instructor’s Solutions Manual available on a companion website

Elementary Number Theory with Programming is a useful textbook for undergraduate and graduate-level students majoring in mathematics or computer science, as well as an excellent supplement for teachers and students who would like to better understand and appreciate number theory and computer programming. The book is also an ideal reference for computer scientists, programmers, and researchers interested in the mathematical applications of programming.

Leseprobe

ELEMENTARY NUMBER THEORY WITH PROGRAMMING

MARTY LEWINTER

JEANINE MEYER

Copyright © 2016 by John Wiley & Sons, Inc. All rights reserved

Published by John Wiley & Sons, Inc., Hoboken, New JerseyPublished simultaneously in Canada

No part of this publication may be reproduced, stored in a retrieval system, or transmitted in any form or by any means, electronic, mechanical, photocopying, recording, scanning, or otherwise, except as permitted under Section 107 or 108 of the 1976 United States Copyright Act, without either the prior written permission of the Publisher, or authorization through payment of the appropriate per-copy fee to the Copyright Clearance Center, Inc., 222 Rosewood Drive, Danvers, MA 01923, [phone], fax [phone], or on the web at www.copyright.com. Requests to the Publisher for permission should be addressed to the Permissions Department, John Wiley & Sons, Inc., 111 River Street, Hoboken, NJ 07030, [phone], fax [phone], or online at http://www.wiley.com/go/permissions.

Limit of Liability/Disclaimer of Warranty: While the publisher and author have used their best efforts in preparing this book, they make no representations or warranties with respect to the accuracy or completeness of the contents of this book and specifically disclaim any implied warranties of merchantability or fitness for a particular purpose. No warranty may be created or extended by sales representatives or written sales materials. The advice and strategies contained herein may not be suitable for your situation. You should consult with a professional where appropriate. Neither the publisher nor author shall be liable for any loss of profit or any other commercial damages, including but not limited to special, incidental, consequential, or other damages.

For general information on our other products and services or for technical support, please contact our Customer Care Department within the United States at [phone], outside the United States at [phone] or fax [phone].

Wiley also publishes its books in a variety of electronic formats. Some content that appears in print may not be available in electronic formats. For more information about Wiley products, visit our web site at www.wiley.com.

Library of Congress Cataloging-in-Publication Data:

Lewinter, Marty, 1950–    Elementary number theory with programming / Marty Lewinter, Jeanine Meyer.        pages    cm    Includes index.

    ISBN 978-1-119-06276-9 (cloth)1.  Number theory.    2.  Number theory–Problems, exercises, etc.    3.  Computer programming.    I.  Meyer, Jeanine.    II.  Title.    III.  Title: Number theory with programming.    QA241.L5815 2015    512.7–dc23

              2015000699

The first author dedicates this book to his son and fellowmathematician, Anthony Delgado

The second author dedicates this book to her mother,Esther Minkin, of blessed memory

PREFACE

“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 ab and ba where a and b are distinct positive integers: 16 = 24 = 42. 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 an + bn = cn 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.

Marty Lewinter, PhD MathematicsJeanine Meyer, PhD Computer ScienceJune 2014

WORDS

In a secret chamber of my heartWhere there’s no room for a lie,Not even one small tiny part,Where there’s found no alibi,In that closely guarded centerBehind thick walls that none can scale,Where deceit may never enterAnd hypocrisy will fail,There’s a truth that’s carved in stone,One that took some time to chisel—Monolithic, cold, alone—Yet it makes my spirit sizzle.

Often have I, silent, prayedThe solemn holy words unspoken,Words that I have not betrayed—And to this day my faith’s unbroken.

Remember what you now shall readWords you ne’er again might see.Take them with you—pay them heed—Reflect on them most carefully.

“Do not trust the words of others—Parents, teachers, friends, or brothers.Alone the wine of wisdom drink,For truth comes but to those who think.

And when some people bully you,Dictating what to think or do,Fight them with the battle cryThat guards your mind with the sacred word: why?”

Copyright M. Lewinter 2014

1SPECIAL NUMBERS: TRIANGULAR, OBLONG, PERFECT, DEFICIENT, AND ABUNDANT

We start our introduction to number theory with definitions, properties, and relationships of several categories of numbers.

TRIANGULAR NUMBERS

Triangular numbers are those that can be written as the sum of a consecutive series of (whole) numbers beginning with 1. Thus 6 is triangular because it is the sum of the first three numbers: 6 = 1 + 2 + 3. The first few triangular numbers are 1, 3, 6, 10, 15, 21, 28, 36, 45, and 55. We denote the nth triangular number by tn. Thus t5 = 1 + 2 + 3 + 4 + 5 = 15. More generally,

(1.1)

Our first program, calculating a specific triangular number, shows the format of an HTML document. The first line specifies the doctype. The rest is an html element, starting with <html> and ending with </html>. Within the html element is a head element and a body element. In this case, the body element is empty. The head element contains a meta tag specifying the character type (it can be omitted), a title, and a script element. All the action is in the script element.

The code makes use of standard programming constructs such as variables and functions and for-loops (if you don’t understand what these terms are, please consult any beginner book on programming. Shameless plug: go to The Essential Guide to HTML5: Using Games to Learn HTML5 and JavaScript, http://www.apress.com/9781430233831).

The specific triangular number we want is specified in the coding by setting the variable n. This is termed hard-coding. The computation is done using a for-loop. The for-loop adds up the values from 1 to n, exactly following Equation 1.1. The built-in method document.write writes out the result.

The challenge in Exercise 1 is to compare coding using Equation 1.1 versus Equation 1.2. The challenge is that computers are very fast. I use the built-in Date function with the method getTime to get the number of milliseconds from a base date at the start and after the computation. It turns out that computing the millionth triangular number takes 3 ms! You can experiment with different values. Using the formula given in would be much, much faster. Give it a try.