Unit 3: Introduction to Number Theory
This unit is primarily concerned with the set of natural numbers 
. The axiomatic approach to 
will be postponed until the unit on recursion and mathematical induction. This unit will help you understand the multiplicative and additive structure of . This unit begins with integer representation: place value. This fundamental idea enables you to completely understand the algorithms we learned in elementary school for addition, subtraction, multiplication, and division of multi-digit integers. The beautiful idea in the Fusing Dots paper will enable you to develop a much deeper understanding of the representation of integers and other real numbers. Then, you will learn about the multiplicative building blocks, the prime numbers. The Fundamental Theorem of Arithmetic guarantees that every positive integer greater than 1 is a prime number or can be written as a product of prime numbers in essentially one way. The Division Algorithm enables you to associate with each ordered pair of non-zero integers - a unique pair of integers - the quotient and the remainder. Another important topic is modular arithmetic. This arithmetic comes from an understanding of how remainders combine with one another under the operations of addition and multiplication. Finally, the unit discusses the Euclidean Algorithm, which provides a method for solving certain equations over the integers. Such equations with integer solutions are sometimes called Diophantine Equations.
Completing this unit should take you approximately 32 hours.
Upon successful completion of this unit, you will be able to:
- express integers and rational numbers using base b notation, where b is an integer not equal to 0 or 1;
- state, identify, and interpret the meaning of certain famous number theory conjectures, including the Twin Prime Conjecture, Goldbach's Conjecture, the Riemann Hypothesis, the Fundamental Theorem of Arithmetic, and the Fundamental Theorem of Algebra;
- solve problems related to the digits of a number;
- find the prime factorization of composite numbers and use such factorizations to find the GCDs and the LCMs of two or more given integers;
- use modular arithmetic to find remainders;
- use the Euclidean Algorithm to solve integer linear equations in two unknowns;
- solve quadratic equations in Z6, Z7, and Z11; and
- solve basic Diophantine equations.
3.1: Place Value Notation
Read this essay, paying special attention to the exercises at the end. You may find the second half of this reading very difficult. You can access the solutions for selected problems here. Don't worry about understanding all of the details your first time through the reading. Instead, concentrate on the material in the first five sections of the document, and then attempt to generally understand the subsequent sections on Fusing Dots.
Review this presentation. This information will most likely serve as a review of place value.
3.2: Prime Numbers
Read this page, which includes a good overview of prime numbers and also a list of unsolved problems. Pay special attention to the unsolved problems 1 and 2.
Read this entry on prime numbers, which will give you an idea of the connections between number theory and other areas of mathematics.
3.2.1: An Infinitude of Primes
Read the entire webpage on Euclid's proof of the infinitude of primes. Be sure you understand why the prime
is not already in the list of primes; if necessary, re-read this text a few times until you have fully grasped this concept.
3.2.2: Conjectures about Primes
Read this page to get an idea of some of the many unsolved problems about prime numbers.
3.2.2.1: The Twin Prime Conjecture
Read this page. Take note of the definition of Brun's constant. Also note that this is related to the Intel's famous $475 million recall of Pentium chips. Please also feel free to click on the link to "Enumeration to 1e14 of the twin primes and Brun's constant" link at the end of the page to read associated content.
3.2.2.2: Goldbach's Conjecture
Read this brief article to learn about the Goldbach conjecture. Problems like this are the subject of intense work by mathematicians around the world, and progress is made nearly every year towards solving them.
3.2.2.3: The Riemann Hypothesis
3.3: Fundamental Theorem of Arithmetic (FTA)
Watch this brief video, which provides an informative, though far less technical, introduction to the Fundamental Theorem of Arithmetic.
Read these pages for information about the Fundamental Theorem of Arithmetic (FTA). Please note that we are going to postpone the proof of FTA until the end of Unit 4.
Read this entire article on the fundamental theorem of arithmetic. The article may take more time to read than some others.
Read this page. In particular, focus on the exercise in the reading. Do not be intimidated by the notation in the essay, just read it down to the part on ideals.
3.4: Modular Arithmetic, the Algebra of Remainders
Watch these lectures, which address the concepts outlined earlier. Then, if you chose to work through the Ken-Ken material in subunit 1.2, go to section 9 of the paper "Using Ken-Ken to Build Reasoning Skills" from subunit 1.2, and re-read the section to recall how to use modular arithmetic as a strategy for Ken-Ken puzzles.
3.4.1: Division by 3, 9, and 11
Watch these videos, which will help you understand the divisibility rules for 3, 9, and 11.
3.4.2: Building the Field Z?
Read this entire essay, paying special attention to understanding the operations ⊕ and ⊗ (read 'oplus' and 'otimes') in Z? and Z?. Then, work the problems 1 and 4 on Z??. You may check your solutions here.
3.4.3: Square Roots in Modular Arithmetic
3.4.3.1: The Addition of Remainders
Try to solve the problem before checking the solution. This problem asks: what is the units' digit of the 2012th Fibonacci number? See if you can work this using your understanding that remainders work perfectly with respect to addition. After you have attempted this problem, review the solution on this page.
3.4.3.2: The Multiplication of Remainders
By now, the following type of problem should be familiar: what is the units digit of the expression 72012 × 132011? See if you can work this using your understanding that remainders work perfectly with respect to multiplication. In other words, if you know the remainder when N is divided by d, then you can find the remainder when N3 is divided by d.
The solution to this question is mentioned below, but please only check it after you have attempted the problem.
Solution: The solution to the initial problem mentioned above is that the remainder when N3 is divided by d is the same as when r3 is divided by d, where r is the remainder when N is divided by d.
3.5: Functions in Number Theory
3.5.1: The Floor and the Ceiling Functions
3.5.2: The Greatest Common Divisor (GCD) and Least Common Multiple (LCM) of Two Integers
Read this page, paying special attention to the relationship between the GCD and LCM.
3.5.3: The Sigma-Function, Summing Divisors
Read this article, paying special attention to Sections 3 and 4, where you will learn about geometry of the divisors of an integer. Complete the problems on the document above, and then check your answers here.
3.6: The Euclidean Algorithm
- Euclid's Algorithm
- An Interactive Illustration
- Euclid's Game
- Binary Euclid's Algorithm
- GCD and the Fundamental Theorem of Arithmetic
Read each of these pages for information on the Euclidean Algorithm.
- Euclid's Algorithm
Read this proof of the FTA.
- Massachusetts Institute of Technology: Dr. Srini Devadas and Dr. Eric Lehman's "Number Theory I" URL
Read this lecture, which provides an introduction to decanting (see the Die Hard example on pages 5-7) and the Euclidean algorithm.
Read this paper. This is an easier version of this technique. Solutions to selected problems can be found here.
3.6.1: Another Look at the Division Algorithm
Review the section on "Division Algorithm" again, and then attempt the 3 sample problems in the lecture.
3.6.2: Solving Ax + By = C over the Integers
Read this lecture, which discusses solving an integer divisibility type of equation. You should focus on solving linear Diophantine equations. In particular, you should be able to find a single solution and then generate all solutions from the one you found.
