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.
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.
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.
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.
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.
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.
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 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.
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.