# Number Theory

## Soak up as much number theory as you can, from mathematical induction to solving polynomial congruences and everything in between.

Number Theory, sometimes called Elementary Number Theory, is a course that undergraduate students take at a college or university. This course is concerned with the study of the integers and often serves an additional purpose –an introduction to writing mathematical proofs. Topics include an in-depth analysis of mathematical induction and divisibility. Following this, the Euclidean algorithm and the Fundamental Theorem of Arithmetic are essential. After that, students will often learn linear congruence equations and systems of linear congruence equations. Special theorems on congruence such as Fermat’s and Euler’s theorem are of significant interest as they are useful, especially in computer science.

## Tonelli-Shanks Algorithm (by Example)

Okay, so you understand how to check if a quadratic congruence is solvable, but how do you find the solutions? In this article, I cover the Tonelli-Shanks algorithm by working through several examples. I also give a complete solution to a general quadratic congruence equation.

In this article, I cover topics related to solving quadratic congruences. In particular, I explain quadratic residues and the Legendre symbol in detail.

## Euler’s Totient Function and Euler’s Theorem

Many people have celebrated Euler’s Theorem, but its proof is much less traveled. In this article, I discuss many properties of Euler’s Totient function and reduced residue systems. As a result, the proof of Euler’s Theorem is more accessible. I also work through several examples of using Euler’s Theorem.

## Fermat’s Theorem (and Wilson’s Theorem)

Maybe you have heard of Wilson’s Theorem? But did you know that’s is converse also holds. In this article, I prove both Wilson’s Theorem, its converse, and Fermat’s Theorem. Then you will also see many examples using Fermat’s theorem.

## Chinese Remainder Theorem

This definitive guide covers proofs, examples, algorithms, applications, and the Chinese Remainder Theorem history. It also includes links to additional resources such as online articles, courses, books, and tutors to help students learn from various sources. Professionals can also use these resources to increase their knowledge of the field or help structure courses for their students.

## Applications of Congruence (in Number Theory)

So you probably know a divisibility test for 2, 3, and 5. But what about 7, 11, 13, or even larger primes? In this article, I go over divisibility tests. Including how to create your own. I also discuss the Days of the Week problem, where you are to determine the day of the week from a given date very quickly.

## Polynomial Congruences with Hensel’s Lifting Theorem

The idea behind solving polynomial congruence equations is that we can reduce a congruence equation to an equivalent system of congruence equations using prime factorization. We then 1) solve each equation modulo a prime number (by brute force), 2) use Hensel’s Lifting theorem, and then 3) piece together the solutions using the Chinese Remainder Theorem. We provide several nontrivial examples many of which are workable by hand.

## Linear Congruences and Their Solvability

In this article, you will learn what linear congruences are and when they are solvable. How to solve them will also be covered in detail. I discuss an ad hoc method, using the Euclidean algorithm, and using the inverse of an integer.

## Congruence Theorems (and Their Proofs)

In this article, I discuss modular congruence. I demonstrate the congruence is an equivalence relation, and I prove several lemmas concerning the basic properties of congruence. Towards the end, I go over modular arithmetic and its properties.

## Diophantine Equations (of the Linear Kind)

In this article, I discuss what Diophantine Equations are and the difficulting of solving them. Then, I detail how to solve two-variable linear diophantine equations. Towards the end, I solve a multi-variable linear Diophantine equation concerning pennies, dimes, and quarters.

## Fundamental Theorem of Arithmetic

In this article, I prove one of the most celebrated theorems in all of mathematics. But first, I explain why this theorem is both fundamental and unique. I also explore some applications and discuss the least common multiple and their connection to greatest common divisors.

## Euclidean Algorithm (by Example)

The Euclidean Algorithm is to find the greatest common divisor of two given integers. In this article, you will see this critical algorithm proven in detail. Further, I will show you how to use these computations to solve linear congruence equations and linear Diophantine equations. While this algorithm has been around a while, it is the key to much success.

## Greatest Common Divisors (and Their Importance) [Video]

We discuss several simple lemmas for greatest common divisors and linear combinations. I then prove Bezout’s identity to show that the greatest common divisor of two integers is the smallest linear combination. We also work through several elementary facts concerning relatively prime integers, and I present many examples.

## Prime Numbers (Theorems and the Infinitude of Primes) [Video]

We discuss the difference between composites and prime numbers and then show how to find prime numbers using Eratosthenes’ sieve. We then prove the infinitude of prime numbers and show that every natural number has a prime divisor by assuming the well-ordering axiom.

## Divisibility (and the Division Algorithm) [Video]

The notion of divisibility is motivated and defined. We work through many examples and prove several simple divisibility lemmas –crucial for later theorems. We also discuss linear combinations, and I present the division algorithm with its proof. Afterward, I demonstrate the importance of the division algorithm through examples.

## Number Theory (Get Started Here)

Number Theory has a long and exciting history. To help understand what Number Theory is all about, in this article, we describe a few basic ideas of Number Theory. From divisibility and mathematical induction to Euler’s theorem and solving polynomial congruence equations, Number Theory can be both highly practical and applicable yet also extremely difficult and abstract. Number Theory also provides us with a playground where students can master proof-writing while learning some very exciting applications of the theory. The Law of Quadratic Reciprocity and the much more recent Tonelli-Shanks algorithm are such examples.

## Fibonacci Numbers (and the Euler-Binet Formula) [Video]

This article introduces the Fibonacci numbers and shows how to use mathematical induction to prove several Fibonacci identities. I then develop the Euler-Binet Formula involving the golden-ratio. Afterward, I discuss the Fibonacci Prime Conjecture and the growth of the Fibonacci sequence.

## Mathematical Induction (With Lots of Examples) [Video]

I work through several examples of writing a proof by Mathematical Induction (for beginners). I concentrate on cases that demonstrate how to use mathematical induction to prove a statement true for all natural numbers. Afterward, I discuss Strong Induction and show how to use it. Then well-known arithmetic and geometric progressions formulas are proven using induction. Towards the end, I confirm that the Well-Ordering Axiom, Mathematical Induction, and Strong Induction are all logically equivalent.

## Greatest Common Divisors (and Their Importance)

In this article, I define Greatest Common Divisors, and I explore Bezout’s theorem. After working through the proof of Bezout’s Theorem, I discuss relatively prime, mutually relatively prime, and pairwise relatively prime integers. You will see many examples and learn about linear combinations.

## Prime Number Theorems (Infinitude of Primes)

We discuss prime numbers and how to find them using the sieve of Eratosthenes. Thereafter, we will then prove important prime number theorems including infinitude of prime numbers. Finally, we will show that every natural number has a prime divisor by assuming the well-ordering axiom.