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.

Subscribe Now

Tonelli Shanks Algorithm by Example Square roots Ranunculus flower root bound As plants grown in containers mature their developing roots eventually will run out of space scaled 1

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.

stamp printed by Switzerland shows Leonhard Euler Mathematician circa 2007 scaled 1

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.

RSA Rivest Shamir Adleman cryptosystem Cryptography and Network Security scaled 1

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 Examples Included Fresh chicken eggs in a basket scaled 1

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 Week days signpost scaled 1

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.

A lines and curves are dizzying but oh so beautiful The wonderful blue sky added extra pizazz scaled 1

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 made into a linear network with data points scaled 1

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.

New York Manhattan 5th ave Big street cast iron clock on skyscrapers background scaled 1

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.

High voltage power lines and lattice crosses under a blue sky with wispy white clouds scaled 1

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.

The shabby and cracked wall of an old building of blocks and bricks scaled 1

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.

Transport Layer Security Secure Socket Layer TLS SSL cryptographic protocols provide secured communications scaled 1

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 1

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

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

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 Golden ratio 3d rendering scaled 1

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

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 Made Easy With Lots of Examples

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 Colored fraction dices on blank white paper notebook on wooden desk selective focus on dices

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 Collage of primary numbers from two to twenty three scaled 1

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.

Subscribe to Dave4Math

Receive free updates from Dave with the latest news!
  • This field is for validation purposes and should be left unchanged.