"Prove k Divides expression(n)" Is a Mod k Problem in Disguise

A classic Indian board-exam problem: prove that 7 divides 11^n - 4^n for every positive integer n. The standard textbook response is to reach for mathematical induction — base case, inductive hypothesis, messy algebraic manipulation to get the (n+1) case out of the n case. That proof works. It is also three times longer than it needs to be.

The better instinct: any sentence of the form "k divides expression(n)" is a modular arithmetic claim in disguise. Rewrite k \mid f(n) as f(n) \equiv 0 \pmod{k}, simplify each piece of f(n) modulo k, and the divisibility fact usually falls out immediately — often in a single line.

The trigger phrase to recognise

Scan the problem statement. If you see any of these, a mod-k rewrite is almost certainly the fastest route.

"Show that k divides …"
"Prove k \mid \text{(something)}"
"(something) is always a multiple of k"
"(something) leaves remainder r when divided by k"

These are all the same sentence wearing different clothes. They are asking you to prove a congruence mod k. The moment you recognise this, the problem type changes from "messy induction" to "one-line residue computation."

Any divisibility claim $k \mid f(n)$ becomes $f(n) \equiv 0 \pmod k$. Once you are working mod $k$, every piece of $f(n)$ can be replaced by its residue — which is usually a much smaller number.

The worked example: 7 \mid 11^n - 4^n

Problem. Prove that for every positive integer n, 7 divides 11^n - 4^n.

Approach 1: the induction slog (for contrast)

Base case n = 1. 11^1 - 4^1 = 7, and 7 \mid 7. ✓

Inductive step. Assume 7 \mid 11^k - 4^k, i.e. 11^k - 4^k = 7m for some integer m. Show 7 \mid 11^{k+1} - 4^{k+1}.

11^{k+1} - 4^{k+1} = 11 \cdot 11^k - 4 \cdot 4^k.

Add and subtract 4 \cdot 11^k to introduce the inductive hypothesis:

= 11 \cdot 11^k - 4 \cdot 11^k + 4 \cdot 11^k - 4 \cdot 4^k = 7 \cdot 11^k + 4(11^k - 4^k) = 7 \cdot 11^k + 4 \cdot 7m = 7(11^k + 4m).

Both terms are multiples of 7, so 7 \mid 11^{k+1} - 4^{k+1}. By induction, the claim holds for all n \geq 1. \square

That is a full page of algebra. It works. Now watch the mod rewrite.

Approach 2: the mod-7 rewrite (one line)

Rewrite the claim: 7 \mid 11^n - 4^n iff 11^n \equiv 4^n \pmod 7.

Now reduce 11 modulo 7: 11 = 7 + 4, so 11 \equiv 4 \pmod 7. Raise both sides to the nth power — a legal operation in congruences — to get

11^n \equiv 4^n \pmod 7.

Done. \square

Why: if a \equiv b \pmod k, then a^n \equiv b^n \pmod k for every positive integer n. This is one of the defining properties of congruence, proved once and reused. So the entire proof shrinks to "11 \equiv 4 \pmod 7, therefore 11^n \equiv 4^n \pmod 7, therefore 7 \mid 11^n - 4^n."

Two lines instead of a page. Both are valid proofs. The second one exposes why the claim is true: 11 and 4 are literally the same thing modulo 7, so their n-th powers are the same thing modulo 7, so their difference is zero modulo 7.

Induction hid that structure. The mod rewrite revealed it.

Second example: 6 \mid n^3 - n

Problem. Show that 6 divides n^3 - n for every integer n.

Rewrite. 6 \mid n^3 - n iff n^3 \equiv n \pmod 6.

Check each residue. Every integer n is congruent mod 6 to exactly one of \{0, 1, 2, 3, 4, 5\}. Check n^3 \bmod 6 in each case.

n \bmod 6	0	1	2	3	4	5
n^3 \bmod 6	0	1	8 \equiv 2	27 \equiv 3	64 \equiv 4	125 \equiv 5

In every column, n^3 \equiv n \pmod 6. Since every integer falls into one of these six classes, the congruence holds universally. Therefore 6 \mid n^3 - n. \square

Why this tactic works: modular arithmetic has only finitely many cases (six cases, for mod 6). Checking them all is a proof by exhaustion over residue classes, and it beats induction whenever the expression simplifies cleanly inside each class.

You could also factor: n^3 - n = n(n-1)(n+1), the product of three consecutive integers, which is always divisible by 2 and by 3, hence by 6. That is even slicker, but it requires spotting the factorisation. The residue-class table works even when no factorisation is obvious.

When induction is still the right tool

The mod rewrite is not a universal replacement for induction. It wins when the expression collapses cleanly into residues. It loses when the expression has pieces whose modular behaviour depends on the structure of n rather than n \bmod k.

Cases where induction usually beats the mod rewrite:

Summation claims like "prove 1 + 2 + \cdots + n = n(n+1)/2." There is no fixed modulus; the claim is about a growing sum, not a divisibility.
Inequality claims like "prove 2^n > n^2 for n \geq 5." Congruences preserve equality, not order.
Recursive definitions like the Fibonacci relation F_{n+2} = F_{n+1} + F_n — the induction machinery matches the recursion directly.
Mixed-degree polynomials where reducing modulo k does not simplify the exponents. For example, "show n! > 2^n for n \geq 4" — factorials do not play nicely with modular reduction.

The heuristic: if the claim has the shape "k divides expression in n" and the expression's pieces have a clean residue pattern mod k, go modular. Otherwise fall back to induction.

The pattern to internalise

Whenever a problem says "k divides …":

Rewrite the divisibility claim as a congruence: k \mid f(n) becomes f(n) \equiv 0 \pmod k.
Reduce each piece of f(n) modulo k. Bases reduce; use a \equiv b \pmod k \Rightarrow a^n \equiv b^n \pmod k to tame exponents.
Check that the reduced expression is \equiv 0. If the expression depends on n \bmod k, tabulate the finitely many cases.

The shift you are making is from an infinite family of integer claims ("for every n \geq 1") to a finite check inside a small residue system. That is the whole reason modular arithmetic exists: to shrink infinite problems into finite ones.