Please note: This book is currently undergoing revision (I'm teaching out of it this semester), so there is a better version — for example, a number of typos have been removed — to be found here. Unfortunately, this more current version is in flux, so only the PDF is available. The source files will be polished and put on the web (on this very page) probably in August of 2015.

 Yet Another Introductory Number Theory Textbook   Jonathan A. Poritz   after Wissam Raji       Department of Mathematics and Physics Colorado State University, Pueblo 2200 Bonforte Blvd. Pueblo, CO 81001, USA E-mail: jonathan@poritz.net Web: www.poritz.net/jonathan

This is the website associated with the textbook whose cover page is above.

If you just want the PDF of the book, here it is.

If you want some more details, here are a few of the first pages:

### Preface

This is a first draft of a free (as in speech, not as in beer) (although it is free as in beer as well) undergraduate number theory textbook. It was used for Math 319 at Colorado State University – Pueblo in the spring semester of 2014. Thanks are hereby offered to the students in that class — Megan Bissell, Tennille Candelaria, Ariana Carlyle, Michael Degraw, Daniel Fisher, Aaron Griffin, Lindsay Harder, Graham Harper, Helen Huang, Daniel Nichols, and Arika Waldrep — who offered many useful suggestions and found numerous typos. I am also grateful to the students in my Math 242 Introduction to Mathematical Programming class in that same spring semester of 2014 — Stephen Ciruli, Jamen Cox, Graham Harper, Joel Kienitz, Matthew Klamm, Christopher Martin, Corey Sullinger, James Todd, and Shelby Whalen — whose various programming projects produced code that I adapted to make some of the figures and examples in the text.

The author gratefully acknowledges the work An Introductory Course in Elementary Number Theory by Wissam Raji [see www.saylor.org/books/] from which this was initially adapted. Raji's text was released under the Creative Commons CC BY 3.0 license, see creativecommons.org/licenses/by/3.0. This work is instead released under a CC BY-SA 4.0 license, see creativecommons.org/licenses/by-sa/4.0. (The difference is that if you build future works off of this one, you must also release your derivative works with a license that allows further remixes over which you have no control.)

This version: 7 May 2014 11:04MDT. Note this text will be frequently updated and improved as the author has time, particularly during and immediately after semesters in which it is being used in a class. Therefore please check back often to the website, which is www.poritz.net/jonathan/share/yaintt/.

This work is dedicated to my insanely hardworking colleagues at Colorado State University – Pueblo whose dedication to their students, their scholarship, and their communities is an inspiration. While I was working on the first version of this book, those colleagues stood up to some of the most benighted, ignorant administrative nonsense I have seen in the more than thirty years I have been involved in higher education. As MLK said, "The arc of the moral universe is long, but it bends towards justice." — It is selfless, intelligent, hard work like yours that is doing the bending.

Jonathan A. Poritz; 7 May 2014; Pueblo, Colorado, USA

### Release Notes

This version of YAINTT has a particular emphasis on connections to cryptology. The cryptologic material appears in Chapter 4 and §§5.5 and 5.6, arising naturally (I hope) out of the ambient number theory. The main cryptologic applications — being the RSA cryptosystem, Diffie-Hellman key exchange, and the ElGamal cryptosystem — come out so naturally from considerations of Euler's Theorem, primitive roots, and indices that it renders quite ironic G.H. Hardy's assertion of the purity and eternal inapplicability of number theory.

Note, however, that once we broach the subject of these cryptologic algorithms, we take the time to make careful definitions for many cryptological concepts and to develop some related ideas of cryptology which have much more tenuous connections to the topic of number theory. This material therefore has something of a different flavor from the rest of the text — as is true of all scholarly work in cryptology (indeed, perhaps in all of computer science), which is clearly a discipline with a different culture from that of "pure" mathematics. Obviously, these sections could be skipped by an uninterested reader, or remixed away by an instructor for her own particular class approach.

Caution: In good Bourbaki [A fictional mathematician and author of many (non-fictional -- they really exist) fine mathematics texts, such as [Bou04]] style, where this symbol appears in the text below, it indicates a place where the reasoning is intricate and difficult to follow, or calls attention to a common misinterpretation of some point.

This version, in PDF form, can be found at
https://www.poritz.net/jonathan/share/yaintt.pdf
while all the files to create custom versions can be found at
https://www.poritz.net/jonathan/share/yaintt/
— have fun with it, that's the point of the Creative Commons!

### Contents

Preface
Release Notes
1. Well-Ordering and Division
1.1 The Well-Ordering Principle and Mathematical Induction
1.2 Algebraic Operations with Integers
1.3 Divisibility and the Division Algorithm
1.4 Representations of Integers in Different Bases
1.5 The Greatest Common Divisor
1.6 The Euclidean Algorithm
2. Congruences
2.1 Introduction to Congruences
2.2 Linear Congruences
2.3 The Chinese Remainder Theorem
2.4 Another Way to Work with Congruences: Equivalence Classes
2.5 Euler's $\phi$ Function
3. Primes Numbers
3.1 Basics and the FTA
3.2 Wilson's Theorem
3.3 Multiplicative Order and Applications
3.4 Another Approach to Fermat's Little and Euler's Theorems
4. Cryptology
4.1 Some Speculative History
4.2 The Caesar Cipher and Its Variants
4.3 First Steps into Cryptanalysis: Frequency Analysis
4.4 Public-Key Crypto: the RSA Cryptosystem
4.5 Digital Signatures
4.6 Man-in-the-Middle Attacks, Certificates, and Trust
5. Indices = Discrete Logarithms
5.1 More Properties of Multiplicative Order
5.2 A Necessary Digression: Gauss's Theorem on Sums of Euler's Function
5.3 Primitive Roots
5.4 Indices
5.5 Diffie-Helman Key Exchange
5.6 The ElGamal Cryptosystem
6. Index

#### For Customization/Remix:

If you are interested in adapting this text to your own purposes, feel free.

The files you will need are all in this directory (folder) of this website. They are:

1. yaintt.tex — the main TeX file: take a look at the moderately detailed instructions for customization which appear as comments at the head of this file
2. refs.bib — the raw material for the bibliography (to be run through bibtex)
3. the following image files:

#### Hardcopy

You can buy a physical copy, if that's your thing, from the on-demand printing service Lulu at this link for \$6 (plus shipping and handling).

I make 61¢ profit for each such sale: I'm happy to reimburse you that amount if you will personally contact me.

#### Keep in touch...

If you use this textbook, as a student, teacher, or otherwise, I would be happy to hear back from you about your experience. And certainly if you find typos or have any suggestions of any kind to improve the book, I would be particularly grateful.

Absolutely the best way to contact me is by e-mail, see my address immediately below.