Congruences are mathematical relationships where two integers A and B are considered congruent modulo n (written as A ≡ B mod n) if they have the same remainder when divided by n, meaning n divides their difference (A - B). This concept partitions all integers into n congruence classes based on remainders from 0 to n-1, enabling arithmetic operations (addition, subtraction, multiplication) within these classes. Congruences simplify solving Diophantine equations by revealing patterns in remainders, such as proving that x² - 7y² = 3 has no integer solutions because squares modulo 7 can only yield remainders of 0, 1, 2, or 4, never 3.
Congruences and Modular Arithmetic in Number Theory
Added:The concept of divisibility of integers, including the mathematical definition and notation for 'a divides b'.
The Division Algorithm (Euclidean division), specifically how to express an integer in terms of a quotient and a remainder.
Basic algebraic properties of integers, including addition, subtraction, and multiplication involving negative numbers.
Solving linear congruences and finding modular multiplicative inverses.
The Chinese Remainder Theorem (CRT) for solving systems of simultaneous congruences with different moduli.
Fermat's Little Theorem and Euler's Totient Theorem, which govern modular exponentiation.
Real-world applications in cryptography, such as the RSA cryptosystem and Diffie-Hellman key exchange.
36.7K views967likes12:26Original Release: 2024-02-06
Congruences are a powerful mathematical tool that can help you identify patterns and streamline large calculations.
But before we dive into the mathematical definition of congruences, let's motivate the idea with an example.
Consider the equation x squared minus 7y squared equals 3.
The graph of this equation is a hyperbola.
Each point on a hyperbola is a solution to the equation.
So the graph is a picture of all real solutions.
This problem becomes more challenging in number theory because here the goal is to find all integer solutions.
In other words, are there any points on a hyperbola where both coordinates are integers?
When looking for just the integer solutions, you call this a diophantine equation.
One way to solve this is to rewrite the equation as x squared equals 7y squared plus 3.
Once we're looking for integer solutions, we can assume the left and right hand sides are both integers.
On the right hand side, we have a multiple of 7 plus 3.
This means that x squared will have a remainder of 3 when you divide it by 7.
But look at the remainders of the first 100 squares when you divide by 7.
There is a clear pattern.
If you divide the square of an integer by 7, then you get 0, 1, 2, or 4.
While we won't show it here, this pattern does continue forever.
That's important.
But you never get a remainder of 3.
So there are no solutions to the diophantine equation.
The key to this solution was to observe a pattern in the remainders of squares when you divide by 7.
Namely, there are only 4 possible remainders.
But if you look more closely, you'll see the remainders repeat in a block of 7.
Now, to be responsible mathematicians, we'd still want to show that this pattern does hold, but for now, it's enough to see the pattern.
This is an example of how working with remainders enables you to solve what appears to be a challenging problem.
Let's use this as a springboard into the world of congruences.
Because you're watching this video, we think you might enjoy math, science, and programming.
And that means you should check out our website, socratica.com.
We have courses, merch, handouts, articles, and more.
There's so much to learn, and we'll help you learn more.
Now on with the show.
To define congruences, let's explore divisibility by 7 in more detail.
Here are a bunch of integers, both positive and negative.
If you divide each integer by 7, you get a remainder between 0 and 6.
Even when you divide a negative number by 7, you still get a remainder between 0 and 6.
You group the integers into sets by the remainder.
The first will be all the integers with a remainder of 0 when you divide by 7.
The next will be those with a remainder of 1, then 2, and so on.
So every integer can be put into one of 7 remainder sets.
In each set, the integers are 7 apart, but the patterns go much, much deeper.
If you pick any number from one set, and add it to an integer from another set, then the sum is always in the same set.
Try this a few times to feel the excitement yourself.
This also works for subtraction, and it even works for multiplication.
But division, sadly, is different.
When you divide one integer by another, you may not get an integer.
So let's set aside division for now, and focus on the other three operations.
The big idea is this.
These remainder sets can be treated as standalone mathematical objects that you can add, subtract, and multiply.
And we can study these objects and look for interesting patterns and properties.
Let's give each of these 7 sets a name.
When you add any number with a remainder of 3, divided by 7, to any number from the remainder 5 set, you always get an integer in the remainder 1 set.
We could write this as R3 plus R5 equals R1.
And as we saw earlier, you can write down similar expressions for subtraction and multiplication.
For example, R2 minus R4 equals R5.
And R3 times R3 equals R2.
It's almost as if we've created a new way to do arithmetic.
Remainder arithmetic.
Here are the addition, subtraction, and multiplication tables for these 7 remainder sets.
Don't forget that we had to put aside division for the time being.
In mathematics, when you do arithmetic with the remainder sets, we call it modular arithmetic.
There is also some notation that is used when talking about modular arithmetic.
What this notation says is that A and B are in the same remainder set when you divide by n.
This expression is called a congruence.
If two numbers A and B are in the same remainder set when you divide by 7, we write it like this.
You read this aloud as A is congruent to B mod 7.
This is the mathematical way to say that A and B have the same remainder when you divide by 7.
The symbol with three lines is called the congruence symbol.
The number inside parentheses is called the modulus.
That's why we write mod inside parentheses.
It's short for modulus.
So here, the modulus is 7.
So far we focused on the number 7 as a way to motivate the idea of congruences.
But now it's time to talk about congruences and modular arithmetic in a more general sense.
Let's take all of the integers and look at the remainders when you divide by a positive integer n.
Each integer will have a remainder between 0 and n-1 when you divide by n.
We can partition the whole numbers into n sets based on the remainders.
Above, we call these remainder sets, but in number theory you call them congruence classes.
Like before, you can add, subtract, and multiply two numbers from congruence classes and the result will always be in the same class.
So the following statements mean the same thing.
A and B have the same remainder when you divide by n.
A and B are in the same congruence class.
A is congruent to B mod n.
These terms and notation will eventually become second nature to you.
It's now time to see some examples.
Let's look at some congruences and determine if they're true or false.
Is 30 congruent to 12 mod 9?
Yes.
When you divide 30 by 9, you get a remainder of 3, and the same goes for 12.
Is 52 congruent to 92 mod 10?
Yes.
You divide either number by 10, the remainder is 2.
And what about this congruence?
35 is congruent to negative 1 mod 6.
This is also true.
If you divide 35 by 6, you get a remainder of 5.
And if you divide negative 1 by 6, you get a quotient of negative 1 and also a remainder of 5.
Is A congruent to A mod 16?
This is also true, even though we don't know the value of A, since both sides of the congruence are the same, they'll have the same remainder.
How about this congruence?
14 is congruent to 6 mod 5.
This is false, dividing both numbers by 5.
14 has a remainder of 4, and 6 has a remainder of 1.
So these two are not congruent mod 5.
When the congruence is not true, you draw a slash through the congruence symbol.
There's a useful trick to check if two numbers are congruent.
But we did several divisions to see if each congruence was correct or not.
We divided both sides by the modulus and checked if the remainders were the same.
Another way you can check is by subtracting the two numbers, the order doesn't matter, then divide by the modulus.
If the remainder is zero, then the congruence is correct.
For example, is 103 congruent to 37 mod 11?
If you subtract the two numbers, you get 66.
When you divide 66 by the modulus 11, you get a remainder of zero.
In other words, 66 is a multiple of 11, so this is correct.
To see why this trick works, look at the general case, a is congruent to b mod n.
If this is true, then dividing a and b by n will give you the same remainder r.
So a equals n times q1 plus r, and b equals n times q2 plus r, where the q's are the quotients.
If you subtract these two expressions, you get a minus b equals n times the quantity of q1 minus q2.
So a minus b is a multiple of n.
We've shown that if a is congruent to b mod n, then it's true that n divides a minus b.
However, it's also important to flip this statement and show the reverse is true.
That is, if n divides a minus b, then a is congruent to b mod n.
To see this, let's assume that n divides a minus b.
Next, suppose that when you divide a by n, the remainder is r1, and when you divide b by n, the remainder is r2.
This means a equals n times q1 plus r1, and b equals n times q2 plus r2.
So a minus b equals n times the quantity of q1 minus q2 plus the quantity of r1 minus r2.
If n divides a minus b on the left, then n divides the right hand side too.
n divides the first term since it's a multiple of n.
This means that n has to divide r1 minus r2.
But since the remainders are both between 0 and n minus 1, the only way n can divide this evenly is if their difference is 0.
This means r1 equals r2.
The remainders are the same.
So a is congruent to b mod n.
Since n divides a minus b means that a and b have the same remainder when you divide by n, and vice versa, some people will define a is congruent to b mod n as saying a and b have the same remainder when you divide by n, while others will define it to mean n divides a minus b.
Both definitions are fine, they mean the same thing.
One common way to visualize modular arithmetic is with a clock, but not just any clock.
The number of numbers on the clock will depend on the modulus.
Imagine we're working modulus 9.
Any integer divided by 9 will have a remainder between 0 and 8.
So let's label the clock with the numbers from 0 to 8.
We will count up by going clockwise, and count down by going counterclockwise.
We already have the integers 0 through 8, so let's pick up from there.
The next whole number on the clock would be 9, then 10, then 11, and so on.
We keep counting up and writing each number next to the corresponding remainder.
With this technique, each positive integer appears next to its remainder.
So each sector of the clock contains the numbers in each congruence class.
And if we start at 0 and count down by going counterclockwise, we can place each negative integer into the correct congruence class.
Next, you'll learn how to work with congruences in much the same way as working with equations.
Then you'll be ready to use congruences to solve more complex problems.
You'll also see how congruences are used in the real world.
That's right, they're out there, just waiting to be recognized.
Up Next
94:23
Orbital Mechanics: Vector Analysis, Reference Frames, Vectrix
@SRLabCarleton
26.5K views•2020-12-23
28:10
Gain Recalibration in Hippocampal Path Integration: Math Theory
@1024kyz
144 views•2020-07-02
10:44
Fourier Series Introduction: The Big Idea Explained
@DrTrefor
387K views•2021-05-03
6:00
The Mathematical Impossibility of Accurate World Maps
@Vox
23.3M views•2016-12-02
Related Study Plans & Knowledge Roadmaps
Structured learning paths in Mathematics
mathematics
Non-Euclidean Geometry: Models & Geodesics
01Euclid's Fifth Postulate and the Birth of New Geometries
02Hyperbolic Space and the Poincaré Disk Model
03Geodesics: Defining Straight Lines in Curved Spaces
+ 2 more learning modules
15h5 modules
Explore Roadmap
mathematics
Knot Theory — Moves, Coloring & Polynomials
01Introduction to Topology and Knots
02Reidemeister Moves & Knot Equivalence
03Knot Invariants and Tricolorability
+ 2 more learning modules
12h5 modules
Explore Roadmap
mathematics
Category Theory: Functors, Monads & FP
01Mathematical Foundations: Functions, Composition & Types
02Introduction to Category Theory: Objects & Morphisms
03Functors: Mapping Between Categories
+ 2 more learning modules
12h5 modules
Explore Roadmap
mathematics
Complex Analysis: Residues & Contour Integrals
01Foundations of Complex Numbers
02Complex Functions and Holomorphic Properties
03Complex Integration and Cauchy's Theorem
+ 2 more learning modules
18h5 modules
Explore Roadmap