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.

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!

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
Index