# Elementary Number Theory (Get Started Here)

## Introduction to Elementary Number Theory

Number Theory is a mathematical discipline concerned with the study of the natural numbers, also known as the positive whole numbers, or counting numbers. These are the numbers we all learn as children: 1, 2, 3, 4, 5, and so on. So, why would these be the object of a brand of higher mathematics? Surely we know everything there is to know about the natural numbers now, right? Well, not so fast.

Number Theory is concerned with the relationships between particular subsets of the natural numbers. Some examples of subsets would be the odd numbers, or the even numbers. The prime numbers are a subset – that is, a number greater than 1 whose only divisors are 1 and itself. The square numbers are the numbers whose square root is an integer: 1, 4, 9, 16, 25, and so on. Similarly, the cubes are the numbers whose cube root is an integer: 1, 8, 27, 64, 125, and so on. Many of these subsets will be familiar to you, but some will not. We will take a closer look at many such sets of numbers in the following articles.

### Questions Posed in Elementary Number Theory

Some examples of typical questions posed in number theory include “Can the sum of two squares be a square?” or “Are there infinitely many prime numbers?” We will look more closely at these and other such questions in the subsequent sections.

Let’s think about that first question for a moment. Can the sum of two squares be itself a square? If you think about it for a moment, the answer should be clear: $3^2 + 4^2 = 5^2$. So the answer to this question is “Yes!”. In fact, there are quite a few examples of squares that satisfy this requirement. These sets of square numbers have a special name: Pythagorean triples. However, can we say that same thing for cubes? Can the sum of two cubes be a cube? That’s a little trickier. What about higher powers? Can the sum of two fourth powers be itself a fourth power? We’re about to stumble on one of the most famous results in Number Theory. Let’s think about this a little more generally. Can the sum of two $n^{th}$ powers itself be an $n^{th}$ power, for $n$ greater than 2?

### Famous Problems in Elementary Number Theory

In general, the answer is “No!”. A result that is known as Fermat’s Last Theorem, and even though it was postulated by Pierre de Fermat in 1637, it actually was not proven to be true until 1994. The product of 357 years of hard work by many, many mathematicians! Its proof opened a whole new world of approaches to many other problems in number theory and related disciplines. If that doesn’t inspire you to reconsider the usefulness and utter awesomeness of number theory, I don’t know what will.

Stick with us in the following articles, and we hope to show you that number theory is the most amazing thing you can do with the natural numbers since Sesame Street.

### The Importance of Mathematical Induction to Number Theory

One of the most useful, and basic, ideas used in Number Theory is Mathematical Induction.  A proof technique that is very useful when working with the natural numbers, mathematical induction is a little like tipping over an infinite equally spaced line of dominos.

In order to utilize the Principle of Mathematical Induction, there are three steps which must be followed. First, the establishment of a “base case” – for example, if we suspect that a given statement is true for all natural numbers $n$, we should first check to see if it is true for one particular natural number – most often, this “base case” shows that a given statement is true when $n=1$.  Once this is proven by example to be so, this becomes the case upon which we can build an inductive hypothesis.

### Induction Process

The second step in the induction process is to state an inductive hypothesis.  To do this, we first make an assumption that our statement is true for some $n$.  Now, you may think that this is something like assuming that our statement is true in general before we’ve proven it – however, this is not the case.  Since we have established a base case, then we have to show that our statement is certainly true for some $n$ – even if $n=1$ is the only such $n$, this assumption is still valid.

From there, we can use induction to show that if our original statement is true for some n, then it must also be true for $n+1$.  From there, all possible cases tip over like a line of dominoes.  If a statement is true for 1, then it must be true for 2.  If true for 2, then true for 3; and so on.  In our article on the Principle of Mathematical Induction, we go into a little more detail on this subject, and present one of the “classic” induction proofs as an example.

### Special Integers

One well-known use of mathematical induction is proving various characteristics of sequences of numbers – and one of the most well-known sequences is the Fibonacci sequence. This sequence has appeared in popular culture from The Phantom Tollbooth to the Darren Aronofsky film Pi, and have been attributed to the legendary “golden ratio,” which is allegedly found throughout nature and in human creations since the dawn of time. So, what is this mystical sequence of integers?

### Fibonacci Numbers

Put simply, the Fibonacci sequence begins with 0 and 1, and then from there, each subsequent entry is the sum of the two previous.  Stated symbolically, we can build the Fibonacci numbers $f_n$ with the following recursion: $f_0 = 0,$ $f_1=1,$ $f_n=f_{n-1}+f_{n-2}$ for $n > 1$.

You may notice that in order to calculate a given Fibonacci number $f_n$, you have to know the values of the two previous Fibonacci numbers. Now, to calculate a relatively small Fibonacci number, it’s not too much of a problem to begin at 0 and work our way up.  However, for large Fibonacci numbers this gets a little unwieldy.  Thankfully, the Euler-Binet formula gives us a way to calculate a Fibonacci number without knowing the values of any of the others. Our article on the Fibonacci numbers has more information on this useful formula.

## Divisibility in the Integers

The concept of divisibility is one that is familiar to most people. We say that one number a is divisible by $b$ if $\frac{a}{b} = c$, and $c$ is an integer. In other words, if you divide $a$ by $b$ and have a zero remainder, then a is divisible by $b$.  Another way to say this, and write this, is with the notation $b \vert a$, which is read as “$b$ divides $a$.”  Now, among the integers, we can do many operations to them: add, subtract, and multiply them, for example, and the sum, difference or product of any two integers will itself be an integer.  However, the same is not true for division. Though 1 and 3 are integers, 1/3 is not.  Some say that the study of Number Theory is the study of divisibility.

Any natural number $n$, then, will have a finite number of divisors.  From this fact, we can talk about some other useful and interesting characteristics of divisibility.  For example, for integers $a, b$, and $c$, if $a \vert b$ and $b \vert c$, then $a \vert c$.  This and many other interesting properties of divisibility are discussed in our article on the subject.

### Prime Numbers

Related to divisibility are the concept of primes, and the idea of greatest common divisors.  A prime number, of course, is a natural number greater than 1 whose only divisors are 1 and itself.  The number 2 is prime, and has the distinction of being the only even prime. By definition, any even integer larger than 2 has 2 as a divisor, and is thus not prime.  We know that there are infinitely many prime numbers – however, identifying them is not always easy.  One of the classic methods to identify prime numbers is by using the Sieve of Eratosthenes, discussed in detail in our article on Prime Number Theorems.  Additionally, central to the study of Number Theory is the fact that every natural number greater than one has at least one prime divisor – a fact that will turn out to be, in a word, fundamental!

If a number is not prime, then it must be composite. When comparing two composite numbers, it is natural, and often useful, to ask what these two numbers may have in common.  The largest integer c that divides both integers a and b is called $\gcd (a,b)$, which is read, “The greatest common divisor of $a$ and $b$.”  This is another fact that seems relatively straightforward on the surface, and yet has surprising and useful implications in Number Theory. For example, the greatest common divisor of two given integers is always the least positive linear combination of these two integers. More on this concept in our article on the Greatest Common Divisor.

### Arithmetic has a Fundamental Theorem

Putting all of these Number Theory concepts together leads to something truly monumental in mathematics: The Fundamental Theorem of Arithmetic.  Since we have mentioned that every natural number greater than 1 has at least one prime divisor, the Fundamental Theorem of Arithmetic goes even farther, and states this:

Every natural number n greater than 1 can be uniquely written in the form: $$n =p_1^{e_1} p_2^{e_1} \cdots p_k^{e_k}$$ where $p_1 < p_2 < \dots < p_k$ are all prime numbers, and the $e_1 < e_2 < \cdots < e_k$ are natural numbers.

### Prime Numbers are Building Blocks

In other words, every natural number greater than 1 can be written as a product of powers of primes! That’s not only important – it’s vital! Without it, arithmetic would simply not work the way it does! You can read more about the Fundamental Theorem of Arithmetic and other topics related to divisibility below.

## Congruence

Another important component of Number Theory, which many may be unfamiliar with, is the idea of congruence modulo $n$.  What does this mean?  In short, a set of numbers modulo n is a set that “resets” back to zero every $n$ units.  Think about the odometer on your car.  If you’ve ever driven a car for a long time, or otherwise owned a high mileage vehicle, you may have had an odometer that turned past the “100,000” mile mark, and clicked back to all zeros. If this has happened to you, your odometer operates modulo 100,000. Minutes and seconds work modulo 60, and if you measure the distance in degrees around a circle, you’ll find that the angles work modulo 360.

A little more abstractly, think about the integers modulo 5. That would include 1, 2, 3, 4, and 0 – once we get to 5, the sequence resets. To talk about congruence modulo 5 for any number, simply divide that number by 5: the remainder is the new value modulo 5.  In other words, 13 is congruent to 3 modulo 5 – because when we divide 13 by 5, we have a remainder of 3.

### Congruence Makes Divisibility Questions Easier to Work With

Number Theorists use many theorems and lemmas related to congruence in order to learn many things about the way modular arithmetic works, and the way the natural numbers in general operate.  Many such congruence theorems can be found in our article, Congruence Theorems and Their Proofs.

Another excellent example of congruence is in the days of the week, which can be expressed as an integer modulo 7.  Using this, and a few other facts, there is a concise formula to determine the day of the week for any given date on the Gregorian calendar.  Some of the many applications of congruence can be found in both abstract and applied interpretations of Number Theory.

### Yes, Number Theory Can Be Applied

For instance, divisibility tests rely on congruence theorems in order to help us quickly and easily determine if one number is divisible by another.  One well-known example is the divisibility test for 3 (and powers of 3): a number n is divisible by 3 precisely when the sum of its digits is divisible by 3. This test is fairly straightforward and can often be performed mentally, but some are a little more involving.

Some other famous results related to congruence include Wilson’s Theorem, Fermat’s Theorem, and Euler’s Totient Function, which gives the count of numbers less than or equal to $n$ which are relatively prime to $n$ – that is, the count of every number $a<n$ such that $\gcd (a,n) = 1$.  For more details on these and other results related to congruence, consult the informative articles below.

## Number Theory Brought to You By

Elementary number theory may very well be one of the oldest subjects of mathematics. Roughly put, number theory is the mathematical treatment of questions related to the integers; that is, the numbers $0, \pm 1, \pm 2, \pm 3 …$ and people have been manipulating them for thousands of years.

### The Ancients

The Ancient Greeks, in particular, Euclid (third century) and the Pythagoreans (sixth century B.C.) dedicated a considerable amount of attention to them; as well as Archimedes (third century). Indeed, one of the most important sets of numbers, the prime numbers; hold a key position in number theory since they are the building blocks of the integers; and perhaps the first question that comes to mind is whether there are infinitely many prime numbers. A proof of this amazing fact can be found in Euclid’s famous book: The Elements.

### The Masters

Pierre de Fermat and Leonard Euler rekindled interest in number theory in the seventeenth and eighteenth centuries by using new (among others, calculus-related) techniques to arrive at important new results. Each new theorem of course, has led to many new questions and conjectures; and one of the fascinating aspects of number theory is that many unresolved questions can be understood with only a minor background in the subject. Even today there are many open problems; and some have substantial rewards for a solution!

After Fermat and Euler, Carl Friedrich Gauss, one of the greatest mathematicians of all time, gave the first modern treatment of number theory. He defined the notion of congruence, and distinguished its importance; in fact, it’s his notation and approach of number theory that we use today. Gauss’s many achievements in number theory are well documented; and it’s Gauss who coined the phrase “number theory is the queen of the sciences”. Interestingly enough, even in an elementary course of number theory, other fields of mathematics can come into play, such as the complex numbers, geometry, and abstract algebra.

### Number Theory is Alive and an Active Area of Research

Erdos was one of the most prolific publishers of papers in mathematical history, comparable only with Leonhard Euler; Erdos published more papers, while Euler published more pages. He wrote around 1,475 mathematical articles in his lifetime, mostly with co-authors. He strongly believed in and practiced mathematics as a social activity, having 511 different collaborators in his lifetime.

A famous conjecture formulated in 1948 by Paul Erdos and Ernst Straus states that any fraction of the form $\frac{4}{n}$ where $n$ is a positive  integer, can be rewritten as the sum of three unit fractions. It is believed that for $n>4$ unique solutions to the following Diophantine equation can be found  $$\frac{4}{n}=\frac{1}{x}+\frac{1}{y}+\frac{1}{z}$$ where $x,y,$ and $z$ are positive integers.

It suffices to find one counterexample to disprove the Erdos-Strauss conjecture. However, some people believe a counterexample will not be found.  Consider, though that it suffices to check among the primes because if $n=p k$ where $p$ is a prime and if $$\frac{4}{p}=\frac{1}{x_0}+\frac{1}{y_0}+\frac{1}{z_0}$$ is known then $$\frac{4}{n}=\frac{4}{ k p}=\frac{1}{k x_0}+\frac{1}{k y_0}+\frac{1}{k z_0}.$$ So if the Erdos-Strauss conjecture is proven true for all prime numbers then it will also hold for all composite numbers.

If you’ve ever wondered if 46,548 is divisible by 7, then Introduction to Number Theory is for you.

## Introduction to Elementary Number Theory

Introduction to Elementary Number Theory is a friendly guide for the study of integers, proof writing, mathematical induction, divisibility, congruence equations, and more. This book is full of examples and exercises, perfect for undergraduate students studying math and computer science, as well as advanced high school students studying mathematics.

## The Natural Numbers

In the first chapter The Natural Numbers, readers will find two sections which are Mathematical Induction and Fibonacci Numbers. In the first section, we see a collection of other topics, such as the strong form of mathematical induction, the well-ordering axiom (principle), and the relationship between the two. The rest of the chapter is about Fibonacci numbers. The author introduces them, some identities, and gives several examples. Then, the author moves on to the Euler-Binet formula, the prime conjecture, and closes with how the Fibonacci sequence can grow.

### What You’ll Learn in The Natural Numbers

• The Principle of Mathematical Induction
• Well-Ordering Axiom
• Examples Using Mathematical Induction
• Induction Principles
• Arithmetic and Geometric Progressions
• The Strong Form of Induction
• The Equivalence
• Introduction to the Fibonacci Numbers
• Fibonacci Identities
• More Examples on Fibonacci Numbers
• The Euler-Binet Formula
• The Fibonacci Prime Conjecture
• The Growth of the Fibonacci Sequence
• Axioms for the Natural Numbers
• The Successor Function
• The Universal Property of Natural Numbers
• The Axioms for Presburger Arithmetic
• The Good News for Presburger Arithmetic
• The Bad News for Presburger Arithmetic
• The Axioms for Peano’s Arithmetic
• Multiplication
• The Good News for Peano’s Arithmetic
• The Bad News for Peano’s Arithmetic

This course focuses on the Natural Numbers, especially the Principle of Mathematical Induction. So, we concentrate on the well-ordering axiom, applying mathematical induction, and the strong form of mathematical induction. After we work out many examples, we then work through that induction, the well-ordering axiom, and strong induction are logically equivalent. Next, the infamous Fibonacci numbers are covered in detail, including proving several Fibonacci identities using mathematical induction.

After that, we begin a more formal approach to the natural numbers. In other words, we take the natural numbers system and form a list of axioms and show that the natural numbers are universal with these properties.

In addition, in this course, we extend the list of axioms to include a total function called addition. Then we prove several properties of addition, showing that this total function is the usual addition that we are familiar with. As a result, this system is called Presburger Arithmetic, and we discuss its logical foundations.

Finally, in this course, we extend our natural numbers system to involve both addition and multiplication. In doing so, this system is called Peano Arithmetic, which is the basis for the standard natural number system. After that, we discuss its logical foundations.

## Introducing the Integers

The second chapter covers six main topics. They include divisibility, prime numbers, greatest common divisors, Euclidean Algorithm, Fundamental Theorem of Arithmetic, and Linear Diophantine Equations. In the first subsection, you will find that the author defines divisibility, then delves into the divisibility lemmas. After that, the Division algorithm is explained while using it in several examples. The section on prime numbers deals with the sieve of Eratosthenes, prime divisors, and infinitude of primes.

The third section on greatest common divisors has two subdivisions, i.e., Bezout’s identity and relatively prime integers. After the author introduces the Euclidean Algorithm in the next subsection, several lemmas are studied. The penultimate part of this chapter is about the Fundamental Theorem of Arithmetic. Within it, the author characterizes primes, provides proof of the Fundamental Theorem, and then visits the topic of least common multiples. The final section of the second chapter deals with Linear Diophantine Equations of different types, i.e., two and multivariable, and how to solve them.

## What You’ll Learn in Divisibility in the Integers

• Definition of Divisibility
• Divisibility Lemmas
• The Division Algorithm
• Examples Using the Division Algorithm
• Sieve of Eratosthenes
• Prime Divisors
• Infinitude of Primes
• Definition of Greatest Common Divisors
• Bezout’s Identity
• Relatively Prime
• Euclidean Algorithm Lemma
• Euclid’s Algorithm
• The Fundamental Theorem of Arithmetic
• Characterization of Primes
• Proof of the Fundamental Theorem
• Least Common Multiples
• What are Diophantine Equations?
• Two Variable Linear Diophantine Equations
• Solving Linear Diophantine Equations
• Multivariable Linear Diophantine Equations

### Description

This course is a continuation of the course entitled The Natural Numbers. You are required to know mathematical induction for this course.

This course begins with the definition of divisibility in the integers and then discusses the division algorithm in great detail. We then discuss the prime numbers (the fundamental building blocks of the integers).

Then we examine the greatest common divisors of two integers and how to find them using the Euclidean algorithm. After this, we state and prove the fundamental theorem of arithmetic. Towards the end of the course, we include linear Diophantine equations. We emphasize solvability and solve many examples.

## Any Introduction to Elementary Number Theory Should Concentrate on Congruence

### What You’ll Learn in Congruence in the Integers

• Definition and Examples of Congruences
• Congruence Lemmas
• Least Positive Residues
• Modular Arithmetic
• Solving Linear Congruence Equations
• The Inverse of a Integer Modulo n
• Linear System of Congruence Equations
• Chinese Remainder Theorem I
• Chinese Remainder Theorem II
• Congruence Reduction
• Simple Examples of Polynomial Congruence
• Hensel’s Lifting Theorem
• Solving Polynomial Congruences
• Divisibility Tests
• Days of the Week
• Wilson’s Theorem
• Fermat’s Little Theorem
• Euler’s Totient Function
• Solving Euler Functional Equations
• Reduced Residue Systems
• Euler’s Theorem and Its Proof
• The Legendre Symbol
• Properties of the Legendre Symbol
• The Law of Quadratic Reciprocity
• Euler’s and Gauss’s Criterion
• A Proof of the Law of Quadratic Reciprocity
• The Tonelli–Shanks Theorem
• Examples of Tonelli–Shanks Algorithm