Chapter 7 First Steps With General Congruences
One can say a lot more about solving congruences. However, congruences also play a crucial role in solving all manner of other number-theoretic problems.
In this chapter we collate a significant number of interesting results that the congruence framework affords us. Among them are some of the most important results we have access to at this early stage, including Fermat's Little Theorem and Lagrange's Theorem on polynomials.
Summary: First Steps With General Congruences
Although we cannot as easily fully solve more general congruences than linear ones, there are many useful and elementary results to explore.
As a prelude, we explore Question 7.1.1 about when we have square roots of \(\pm 1\text{,}\) modulo \(n\text{.}\)
-
Can we use some of the methods from linear congruences for polynomials?
We can combine solutions to polynomials in a similar way to the Chinese Remainder Theorem (Fact 7.2.2).
In Hensel's Lemma we see how to use a solution modulo a prime power to create a solution modulo a higher power of the same prime.
A key approach in solving congruences is to remember that the nature of the solutions may also be expressed in terms of a congruence. Fact 7.3.2 is a first good example of this, giving a complete analysis of square roots of one.
We next see in Lagrange's Theorem for Polynomials that when our modulus is prime, solutions of polynomials are limited more closely by our previous experience.
Two towering theorems giving theoretical tools to harness more complex congruences are Wilson's Theorem and Fermat's Little Theorem.
Finally, we explore Mordell curves again in an effort to motivate a deeper understanding of Epilogue: Why Congruences Matter.
The Exercises focus on polynomial congruences, but include a little practice of Fermat's Little Theorem. After this we have alternate combinatorial proofs provided of Fermat's Little Theorem and Wilson's Theorem; see especially the section on Counting motivation.