The Central Idea
Let \(n\) be a positive integer. Two integers \(a\) and \(b\) are congruent modulo \(n\) when they leave the same remainder after division by \(n\).
We write
\[ \boxed{a\equiv b\pmod n}. \]This is read “\(a\) is congruent to \(b\) modulo \(n\).”
A First Example
Divide \(17\) and \(5\) by \(12\).
\[ 17=12(1)+5 \]and
\[ 5=12(0)+5. \]Both leave remainder \(5\). Therefore,
\[ \boxed{17\equiv5\pmod{12}}. \]Another Equivalent Definition
Congruence modulo \(n\) can also be defined using divisibility:
\[ \boxed{ a\equiv b\pmod n \iff n\mid(a-b) }. \]In other words, \(a\) and \(b\) are congruent modulo \(n\) exactly when their difference is divisible by \(n\).
Checking the First Example by Divisibility
We claimed
\[ 17\equiv5\pmod{12}. \]Subtract:
\[ 17-5=12. \]Since
\[ 12\mid12, \]the congruence is confirmed.
When Congruence Fails
Consider whether
\[ 17\equiv6\pmod{12}. \]Their difference is
\[ 17-6=11. \]Since
\[ 12\nmid11, \]we conclude
\[ \boxed{17\not\equiv6\pmod{12}}. \]The Modulus
In
\[ a\equiv b\pmod n, \]the positive integer \(n\) is called the modulus.
The modulus determines the cycle length used to compare integers.
For example, modulo \(5\),
\[ 0,\ 1,\ 2,\ 3,\ 4 \]are the possible remainders.
Canonical Remainders
For modulus \(n\), every integer is congruent to exactly one number in
\[ \boxed{0,1,2,\ldots,n-1}. \]These are the standard nonnegative remainders modulo \(n\).
For example, modulo \(7\), every integer is congruent to exactly one of
\[ 0,\ 1,\ 2,\ 3,\ 4,\ 5,\ 6. \]Reducing an Integer Modulo \(n\)
To reduce an integer modulo \(n\), divide by \(n\) and keep the remainder.
For example,
\[ 43=7(6)+1. \]Therefore,
\[ \boxed{43\equiv1\pmod7}. \]Negative Integers in Modular Arithmetic
Negative integers can also be reduced to standard nonnegative remainders.
Consider
\[ -3\pmod7. \]Since
\[ -3+7=4, \]we have
\[ \boxed{-3\equiv4\pmod7}. \]Many Integers Can Represent the Same Remainder
Modulo \(5\),
\[ \ldots,-9,-4,1,6,11,16,\ldots \]all differ from one another by multiples of \(5\).
Therefore,
\[ \boxed{ \cdots\equiv-9\equiv-4\equiv1\equiv6\equiv11\equiv16\pmod5 }. \]Congruence Is Not Ordinary Equality
The statement
\[ 17\equiv5\pmod{12} \]does not mean
\[ 17=5. \]It means the two integers occupy the same remainder position in a cycle of length \(12\).
Congruence is therefore a relationship relative to a chosen modulus.
Changing the Modulus Can Change the Relationship
The integers \(17\) and \(5\) satisfy
\[ 17\equiv5\pmod{12}. \]But modulo \(7\),
\[ 17\equiv3\pmod7 \]while
\[ 5\equiv5\pmod7. \]Therefore,
\[ 17\not\equiv5\pmod7. \]Congruence must always be interpreted together with its modulus.
Clock Arithmetic
A clock provides a familiar model of modular arithmetic.
On a \(12\)-hour clock, moving forward \(12\) hours returns to the same position.
Therefore,
\[ 15\equiv3\pmod{12}. \]A time labeled \(15\) hours after a reference point occupies the same clock position as \(3\) hours after that point.
Example: Clock Addition
Suppose it is \(9\) o'clock. What clock position occurs \(7\) hours later?
\[ 9+7=16. \]Reduce modulo \(12\):
\[ 16\equiv4\pmod{12}. \]Therefore the clock reads
\[ \boxed{4}. \]Addition Preserves Congruence
If
\[ a\equiv b\pmod n \]and
\[ c\equiv d\pmod n, \]then
\[ \boxed{a+c\equiv b+d\pmod n}. \]Congruent values may therefore be replaced by simpler representatives before adding.
Example: Modular Addition
Compute
\[ 38+47\pmod9. \]Reduce first:
\[ 38\equiv2\pmod9 \]and
\[ 47\equiv2\pmod9. \]Therefore,
\[ 38+47\equiv2+2\equiv4\pmod9. \]Thus
\[ \boxed{38+47\equiv4\pmod9}. \]Subtraction Preserves Congruence
Under the same assumptions,
\[ \boxed{a-c\equiv b-d\pmod n}. \]For example,
\[ 29-17=12 \]and
\[ 12\equiv2\pmod5. \]Therefore,
\[ \boxed{29-17\equiv2\pmod5}. \]Multiplication Preserves Congruence
If
\[ a\equiv b\pmod n \]and
\[ c\equiv d\pmod n, \]then
\[ \boxed{ac\equiv bd\pmod n}. \]This makes modular arithmetic especially useful for simplifying large products.
Example: Modular Multiplication
Compute
\[ 37\cdot28\pmod5. \]Reduce each factor:
\[ 37\equiv2\pmod5 \]and
\[ 28\equiv3\pmod5. \]Then
\[ 37\cdot28\equiv2\cdot3=6\equiv1\pmod5. \]Therefore,
\[ \boxed{37\cdot28\equiv1\pmod5}. \]Powers Preserve Congruence
If
\[ a\equiv b\pmod n, \]then for every positive integer \(k\),
\[ \boxed{a^k\equiv b^k\pmod n}. \]This follows by repeated multiplication.
Example: Reducing Before Exponentiation
Compute
\[ 13^4\pmod5. \]Since
\[ 13\equiv3\pmod5, \]we may write
\[ 13^4\equiv3^4=81\pmod5. \]Since
\[ 81\equiv1\pmod5, \]we conclude
\[ \boxed{13^4\equiv1\pmod5}. \]Reduce Early and Often
Modular arithmetic allows intermediate values to be reduced whenever doing so simplifies the calculation.
For example,
\[ 18^3\pmod7. \]First reduce:
\[ 18\equiv4\pmod7. \]Then
\[ 4^2=16\equiv2\pmod7, \]so
\[ 4^3\equiv2\cdot4=8\equiv1\pmod7. \]Therefore,
\[ \boxed{18^3\equiv1\pmod7}. \]Congruence Is Reflexive
Every integer is congruent to itself modulo \(n\):
\[ \boxed{a\equiv a\pmod n}. \]This follows because
\[ a-a=0 \]and every positive integer \(n\) divides \(0\).
Congruence Is Symmetric
If
\[ a\equiv b\pmod n, \]then
\[ \boxed{b\equiv a\pmod n}. \]If \(n\mid(a-b)\), then \(n\mid-(a-b)=b-a\).
Congruence Is Transitive
If
\[ a\equiv b\pmod n \]and
\[ b\equiv c\pmod n, \]then
\[ \boxed{a\equiv c\pmod n}. \]Since \(n\mid(a-b)\) and \(n\mid(b-c)\), divisibility of sums gives
\[ n\mid[(a-b)+(b-c)]=a-c. \]Congruence as an Equivalence Relation
Because congruence modulo \(n\) is reflexive, symmetric, and transitive, it is an equivalence relation on the integers.
This means integers can be partitioned into groups whose members are all congruent to one another modulo \(n\).
The next lesson will formalize these groups as residue classes.
Parity as Modular Arithmetic
Even and odd integers can be described modulo \(2\).
Every even integer satisfies
\[ \boxed{n\equiv0\pmod2}, \]while every odd integer satisfies
\[ \boxed{n\equiv1\pmod2}. \]Thus parity is the simplest nontrivial modular classification.
Example: Odd Plus Odd
Suppose
\[ a\equiv1\pmod2 \]and
\[ b\equiv1\pmod2. \]Then
\[ a+b\equiv1+1=2\equiv0\pmod2. \]Therefore the sum of two odd integers is even.
Divisibility as Congruence to Zero
The statement
\[ n\mid a \]is equivalent to
\[ \boxed{a\equiv0\pmod n}. \]For example,
\[ 7\mid42 \]can be written
\[ 42\equiv0\pmod7. \]Divisibility Tests in Modular Language
Many familiar divisibility tests can be interpreted using congruence.
For example, a number is divisible by \(3\) exactly when
\[ \boxed{n\equiv0\pmod3}. \]The digit-sum test works because powers of \(10\) satisfy
\[ 10\equiv1\pmod3. \]This lets place-value expressions collapse into their digit sums modulo \(3\).
Example: Why the Digit-Sum Test Works Modulo \(3\)
Consider a three-digit number
\[ 100a+10b+c. \]Since
\[ 100\equiv1\pmod3 \qquad\text{and}\qquad 10\equiv1\pmod3, \]we have
\[ 100a+10b+c \equiv a+b+c \pmod3. \]Therefore the original number and its digit sum have the same remainder modulo \(3\).
Modular Arithmetic and Repeating Cycles
Modular arithmetic is useful whenever a process repeats after a fixed number of steps.
Examples include:
- hours on a clock;
- days of the week;
- rotational positions;
- cyclic schedules;
- repeating digital states.
Example: Days of the Week
A week repeats every \(7\) days.
To determine the day position \(100\) days later, reduce \(100\) modulo \(7\):
\[ 100=7(14)+2. \]Therefore,
\[ \boxed{100\equiv2\pmod7}. \]So the weekday shifts forward by \(2\) positions.
Solving a Simple Modular Equation
Consider
\[ x+3\equiv1\pmod5. \]Subtract \(3\) from both sides:
\[ x\equiv-2\pmod5. \]Reduce:
\[ -2\equiv3\pmod5. \]Therefore,
\[ \boxed{x\equiv3\pmod5}. \]Adding or Subtracting the Same Quantity
From
\[ a\equiv b\pmod n, \]we may add or subtract the same integer \(c\) on both sides:
\[ \boxed{a+c\equiv b+c\pmod n} \]and
\[ \boxed{a-c\equiv b-c\pmod n}. \]These rules resemble ordinary equality because addition and subtraction interact cleanly with divisibility.
Multiplying Both Sides
If
\[ a\equiv b\pmod n, \]then for any integer \(c\),
\[ \boxed{ac\equiv bc\pmod n}. \]For example, from
\[ 8\equiv3\pmod5, \]multiplying by \(4\) gives
\[ 32\equiv12\pmod5. \]Both sides reduce to \(2\) modulo \(5\).
Cancellation Requires Care
Multiplication preserves congruence, but cancellation is more delicate.
For example,
\[ 2\cdot1\equiv2\cdot4\pmod6 \]because
\[ 2\equiv8\pmod6. \]But cancelling the factor \(2\) would incorrectly suggest
\[ 1\equiv4\pmod6. \]This is false.
Why Cancellation Can Fail
From
\[ ac\equiv bc\pmod n, \]we know
\[ n\mid c(a-b). \]This does not always imply
\[ n\mid(a-b). \]Cancellation becomes valid under additional conditions involving the common divisors of \(c\) and \(n\). Later lessons on linear congruences will develop those conditions systematically.
Division Is Not Automatically Available
Ordinary arithmetic allows division by every nonzero real number. Modular arithmetic does not.
To “divide” by a number modulo \(n\), that number must have a suitable multiplicative inverse modulo \(n\).
This is one reason modular inverses and the Euclidean Algorithm become important in later number theory.
Common Error: Using \(=\) Instead of \(\equiv\)
The statement
\[ 17\equiv5\pmod{12} \]is correct.
Writing
\[ 17=5 \]is not.
Congruence records equality of remainder behavior, not ordinary numerical equality.
Common Error: Forgetting the Modulus
A congruence statement is incomplete without specifying the modulus.
The expression
\[ 17\equiv5 \]does not identify the arithmetic system being used.
The meaningful statement is
\[ \boxed{17\equiv5\pmod{12}}. \]Common Error: Keeping a Nonstandard Remainder
Modulo \(7\), the standard remainder should lie in
\[ 0,1,2,3,4,5,6. \]Although
\[ 20\equiv13\pmod7 \]is true, both numbers can be reduced further:
\[ 20\equiv13\equiv6\pmod7. \]Using the canonical remainder \(6\) usually makes calculations clearer.
Common Error: Mishandling Negative Remainders
A negative representative can be valid, but it may not be the standard nonnegative remainder.
For example,
\[ -1\equiv4\pmod5. \]Both represent the same modular position, but \(4\) is the canonical remainder.
Common Error: Cancelling Without Checking
From
\[ 2x\equiv2\pmod6, \]it is not valid to conclude immediately that
\[ x\equiv1\pmod6. \]The factor \(2\) shares a nontrivial common divisor with the modulus \(6\). Modular cancellation requires additional justification.
A Reliable Procedure for Reducing Modulo \(n\)
- Identify the positive modulus \(n\).
- Divide the integer by \(n\).
- Find the remainder \(r\) satisfying \(0\le r
- Write the result as \(a\equiv r\pmod n\).
- For negative integers, add or subtract multiples of \(n\) until the representative lies between \(0\) and \(n-1\).
A Reliable Procedure for Modular Arithmetic
- Reduce large inputs modulo \(n\) when convenient.
- Perform the required addition, subtraction, or multiplication.
- Reduce intermediate results again if they become large.
- For powers, reduce the base first and look for repeating patterns.
- Express the final answer using a standard remainder when appropriate.
- Do not cancel or divide unless the required modular conditions have been established.
Example: Full Modular Workflow
Compute
\[ 47\cdot38+29\pmod7. \]Reduce each input:
\[ 47\equiv5\pmod7, \qquad 38\equiv3\pmod7, \qquad 29\equiv1\pmod7. \]Substitute:
\[ 47\cdot38+29 \equiv 5\cdot3+1 = 16 \pmod7. \]Finally,
\[ 16\equiv2\pmod7. \]Therefore,
\[ \boxed{47\cdot38+29\equiv2\pmod7}. \]Example: A Power Pattern
Find the remainder when
\[ 2^{10} \]is divided by \(5\).
Compute small powers modulo \(5\):
\[ 2^1\equiv2, \] \[ 2^2\equiv4, \] \[ 2^3\equiv3, \] \[ 2^4\equiv1 \pmod5. \]The pattern repeats every four powers. Since
\[ 10\equiv2\pmod4, \]we obtain
\[ 2^{10}\equiv2^2\equiv4\pmod5. \]Therefore the remainder is
\[ \boxed{4}. \]Practice 1: Reduce an Integer
Reduce
\[ 58 \]modulo \(9\).
Practice 2: Negative Representative
Find the standard nonnegative remainder congruent to
\[ -17 \]modulo \(6\).
Practice 3: Test Congruence
Determine whether
\[ 43\equiv8\pmod7. \]Practice 4: Modular Addition
Compute
\[ 73+58\pmod9. \]Practice 5: Modular Multiplication
Compute
\[ 41\cdot27\pmod8. \]Practice 6: Modular Power
Compute
\[ 12^4\pmod7. \]Practice 7: Parity
Suppose
\[ a\equiv1\pmod2 \]and
\[ b\equiv0\pmod2. \]Determine the parity of \(ab\).
Practice 8: Simple Congruence Equation
Solve
\[ x+4\equiv2\pmod7. \]Practice 9: Repeating Cycle
A machine has \(10\) states numbered \(0\) through \(9\). Starting in state \(6\), it advances \(17\) states. Which state does it reach?
Practice 10: Identify the Error
A student writes
\[ 2x\equiv2\pmod6 \]and cancels \(2\) to conclude
\[ x\equiv1\pmod6. \]Explain why this cancellation is not automatically valid.
Practice Answers
Practice 1
\[ 58=9(6)+4. \]Therefore,
\[ \boxed{58\equiv4\pmod9}. \]Practice 2
Add multiples of \(6\):
\[ -17+18=1. \]Therefore,
\[ \boxed{-17\equiv1\pmod6}. \]Practice 3
Subtract:
\[ 43-8=35. \]Since
\[ 7\mid35, \]we have
\[ \boxed{43\equiv8\pmod7}. \]Practice 4
\[ 73\equiv1\pmod9 \]and
\[ 58\equiv4\pmod9. \]Therefore,
\[ 73+58\equiv1+4\equiv5\pmod9. \]Thus
\[ \boxed{5}. \]Practice 5
\[ 41\equiv1\pmod8 \]and
\[ 27\equiv3\pmod8. \]Therefore,
\[ 41\cdot27\equiv1\cdot3\equiv3\pmod8. \]Thus
\[ \boxed{3}. \]Practice 6
\[ 12\equiv5\pmod7. \]Then
\[ 5^2=25\equiv4\pmod7, \]so
\[ 5^4\equiv4^2=16\equiv2\pmod7. \]Therefore,
\[ \boxed{12^4\equiv2\pmod7}. \]Practice 7
Since
\[ a\equiv1\pmod2 \]and
\[ b\equiv0\pmod2, \]multiplication gives
\[ ab\equiv1\cdot0\equiv0\pmod2. \]Therefore,
\[ \boxed{ab\text{ is even}}. \]Practice 8
\[ x+4\equiv2\pmod7. \]Subtract \(4\):
\[ x\equiv-2\pmod7. \]Since
\[ -2\equiv5\pmod7, \]we obtain
\[ \boxed{x\equiv5\pmod7}. \]Practice 9
\[ 6+17=23. \]Modulo \(10\),
\[ 23\equiv3\pmod{10}. \]Therefore the machine reaches
\[ \boxed{\text{state }3}. \]Practice 10
From
\[ 2x\equiv2\pmod6 \]we know
\[ 6\mid2(x-1). \]Because \(2\) and \(6\) share a common factor, this does not imply \(6\mid(x-1)\). Modular cancellation requires additional conditions.
For example, \(x=4\) satisfies
\[ 2(4)=8\equiv2\pmod6, \]but
\[ 4\not\equiv1\pmod6. \]What to Remember
- \(a\equiv b\pmod n\) means \(a\) and \(b\) have the same remainder modulo \(n\).
- Equivalently, \(a\equiv b\pmod n\) exactly when \(n\mid(a-b)\).
- Every integer is congruent to exactly one standard remainder \(0,1,\ldots,n-1\).
- Congruence is reflexive, symmetric, and transitive.
- Addition, subtraction, multiplication, and positive integer powers preserve congruence.
- Divisibility by \(n\) is the same as congruence to \(0\) modulo \(n\).
- Reducing values early can simplify large calculations dramatically.
- Cancellation and division require extra care in modular arithmetic.
The central habit is: replace integers by simpler representatives with the same remainder, while always keeping track of the modulus.
Where We Go Next
Congruence groups integers according to shared remainder behavior. The next lesson, Residue Classes, formalizes those groups as mathematical objects and shows how the integers split into distinct congruence classes modulo a fixed positive integer.