Intuition and motivation for congruence relations modulo $n$?

Question

I'm trying to learn a bit of Number Theory. And while I understand the definition of congruence relations modulo $n$ and that they are an equivalence relations, I fail to see the motivation for it. So what is congruence relation $\bmod n$ intuitively? (The "bold lines" below are my questions that I'm seeking answer to.)

Definition: For $a,b \in \mathbb{Z}$ and $n \in \mathbb{N}$, $a\equiv b \bmod n \Leftrightarrow n|(a-b)$

---

Okay, so let's start with the definition, what is really the point of "$n | (a-b)$?" That $a=nq + b$, for some $q \in \mathbb{Z}$? So what do I do with this and why is it so important?

Secondly, if $a$ and $b$ leave the same residue or remainder upon division by $n$ then $a \equiv b \bmod n$, again I don't see why are we so interested in remainders?

And lastly, I keep seeing examples of clocks, days of the week and months. That's good but is that all there's to it?

I have a strong feeling, I'm grossly underestimating congruence relations modulo $n$, perhaps that's because I don't have the intuition for it and where should I should use it. So any intuitive explanations of it and where should one use them would be really really really nice. I'm desperately trying to figure this out. Thanks in advance.

Answer 1

Modulo weakens equality, helps divisibility, and allows dealing with huge numbers. It's relevant to Cryptography, and therefore cybersecurity. It can even help with divisor form:

Assume a number is of form $2^p-1$ , it's clear that any time $2^p\equiv 1\pmod q$ that $q\mid 2^p-1$ . Assume they are both primes, then we get $p\mid q-1$ any time $p>2$ ( Fermat's little theorem, and a bit more theory) but that means $q=jp+1$ with $j$ even ( $j=2k$ for some integer $k$ ) because $q$ must be odd.

It can also be looked at as linear polynomials with all integer variable, coefficients and constants as $y\equiv b\pmod m\implies y=mx+b$

Expanding more upon this $$y\not\equiv b\pmod m\implies y\ne b$$ you can set up $b$ with properties and prove $y$ doesn't have a property. This is used in diophantine equations to show or disprove an example could exist with a property.

An example is checking the conjecture that all natural numbers can be expressed as the sum of $3$ cubes of integers. You can show modulo $9$ that there are only $7$ possible sums of remainders , so there are at least $2$ remainders that will never be possible.

Answer 2

The short answer is that there are many problems in number theory whose solutions depend on looking at the remainders of numbers when they are divided by a specific number m. I can think of no simpler example to illustrate this than the problem of deciding when a given natural number is divisible by 3 or by 9 or by 11. In this case, one needs to look at the remainders of the powers of 10 when they are divided by 3 or by 9 or by 11. For high powers, the theory of congruences makes the job significantly easier. A more sophisticated example is given by certain investigations of Pierre de Fermat, menioned in the previous answer. Fermat was interested, for example, in deciding, for a given prime number p, which natural n makes 2^n - 1 a multiple of p. This line of inquiry led him to his famous Little Theorem: a prime p divides n^(p-1) - 1 whatever natural n one plugs in the expression.The easiest way to prove this is by using congruences, and observing that, for any n not divisible by p, the numbers n, 2n, 3n, ... (p-1)n leave p-1 distinct non-zero remainders when divided by p. These remainders can only be 1, 2, 3, ..., p-1, so that we can say that n*(2n)(3n)...(p-1)n == 123...*(p-1) mod p. Then, dividing both sides by (p-1)! (which is allowed since (p-1)! and p are coprime), we obtain the theorem.