Modular Arithmetic: Remainders, Congruences, and Competition Methods

Remainders and the Modulo Operation

Modular arithmetic focuses on what remains after division rather than on the full size of a number.

For positive integers $a$ and $n$, write

The value $r$ is the remainder, and the notation $a\bmod n$ asks for that remainder. For example,

The divisor $n$ is the modulus. When dividing by $5$, the only possible standard remainders are $0,1,2,3,4$. A remainder cannot be at least the modulus, because another copy of the modulus could still be removed.

A useful calculation routine is:

1. Find the largest multiple of the modulus that does not exceed the number.

2. Subtract that multiple.

3. Check that the result lies between $0$ and one less than the modulus.

For instance,

Special cases are worth recognizing. If $0<a<n$, then $a\bmod n=a$. If $n\mid a$, then $a\bmod n=0$.

Congruence and Remainder Classes

Congruence compares remainder behavior. The statement

means that $a$ and $b$ have the same remainder when divided by $n$. Equivalently,

For example,

because $17-5=12$, which is divisible by $6$. The same fact can be checked through remainders: both numbers leave remainder $5$ modulo $6$.

Do not confuse a modulo result with a congruence. The statement

identifies the actual standard remainder, whereas

places $17$ and $5$ in the same remainder class modulo $6$. The numbers $2,7,12,17,\ldots$ are all congruent modulo $5$, because each leaves remainder $2$.

A reliable way to verify a congruence is to subtract the two sides and test divisibility by the modulus. Remember that congruence is not ordinary equality: $17$ and $5$ are different integers even though they are congruent modulo $6$.

Arithmetic with Congruences

Congruences can be added, subtracted, and multiplied. If

then

Reduce the final result to a standard remainder when a numerical answer is requested.

For example, to find $37\cdot24\pmod5$, reduce first:

Thus,

Subtraction may produce a negative intermediate value. For example,

The standard remainder is $8$, obtained by adding $11$ to $-3$. More generally, add or subtract the modulus until the result lies in the range from $0$ through $m-1$.

These rules make large expressions manageable. For

replace the numbers by $8$, $6$, and $9$:

A key caution is division. Addition, subtraction, and multiplication preserve congruence directly, but cancellation requires a modular inverse and therefore a relatively prime factor.

Choosing Moduli for Divisibility and Parity

Choose a modulus that matches the information being asked for.

• Use modulo $2$ for parity: even numbers satisfy $n\equiv0\pmod2$, and odd numbers satisfy $n\equiv1\pmod2$.

• Use modulo $3$ or modulo $9$ for digit-sum tests.

• Use modulo $4$ for the last two digits.

• Use modulo $8$ for the last three digits.

• Use modulo $10$ for the last digit.

• Use modulo $11$ for alternating digit sums.

For a decimal number, powers of $10$ simplify under these moduli. Since $10\equiv1\pmod9$, a number and its digit sum have the same remainder modulo $9$. For example,

Parity often gives a fast contradiction. Three odd integers have sum congruent to

so their sum cannot be even.

For several remainder conditions, translate each sentence into a congruence. For example, “leaves remainder $2$ when divided by $3$” becomes $x\equiv2\pmod3$, while “is divisible by $5$” becomes $x\equiv0\pmod5$. Then list candidates, substitute, or combine the conditions systematically.

Always check compatibility first when moduli share a factor. A number satisfying $x\equiv2\pmod4$ is even, while a number satisfying $x\equiv3\pmod6$ is odd; therefore, those two conditions cannot hold simultaneously.

Powers, Cycles, and Digit Problems

Powers often have repeating remainder patterns. To find the last digit of a power, work modulo $10$. The powers of $7$ have last-digit cycle

Because the cycle length is $4$,

so

A remainder of $0$ when reducing an exponent by a cycle length means use the last entry of the cycle, not the first. For example, the exponent $100$ is congruent to $0$ modulo $4$, so $7^{100}$ corresponds to the fourth cycle entry, namely $1$.

For a large exponent, use one of three approaches:

1. Calculate successive powers until a cycle appears.

2. Use repeated squaring and reduce after each multiplication.

3. Apply a theorem such as Fermat's Little Theorem or Euler's theorem when its conditions hold.

Repeated squaring is efficient because an exponent can be written as a sum of powers of $2$. For example, $100=64+32+4$, so compute $a^{64}$, $a^{32}$, and $a^4$ by successive squaring, then multiply their reduced residues.

Fermat's Little Theorem says that for a prime $p$ with $p\nmid a$,

Thus, for $2^{100}\pmod{13}$, reduce the exponent modulo $12$:

The condition $p\nmid a$ is essential. Do not reduce exponents automatically without checking the relevant cycle or theorem.

Combining Remainder Conditions

A system of congruences can often be solved by listing candidates or by substitution. Consider

Numbers congruent to $2$ modulo $3$ are $2,5,8,11,14,\ldots$. The first one that is congruent to $4$ modulo $5$ is $14$, so

The period is $15$ because $3$ and $5$ are relatively prime.

Substitution gives another method. To solve

write $x=1+4k$. Then

Since $4\equiv-1\pmod5$, we obtain $k\equiv3\pmod5$, and therefore $x=13$ is the least positive solution. The complete solution is

This is an instance of the Chinese Remainder Theorem: compatible conditions with relatively prime moduli determine one residue modulo the product of the moduli. If moduli share factors, the corresponding remainders must agree modulo the common factors.

For a linear congruence

let $d=\gcd(a,m)$. If $d\nmid b$, there are no solutions. If $d\mid b$, divide the entire congruence by $d$, solve the reduced congruence, and then account for the resulting solution classes modulo $m$.

Modular Inverses and Safe Division

Division in modular arithmetic means multiplication by a modular inverse. An inverse of $a$ modulo $m$ is a number $a^{-1}$ satisfying

Such an inverse exists exactly when $\gcd(a,m)=1$. For example, $3^{-1}\equiv5\pmod7$ because $3\cdot5=15\equiv1\pmod7$. Therefore, solving

gives

If the coefficient and modulus are not relatively prime, cancellation may be invalid. From $2x\equiv2 otag a\pmod6$, it does not follow that $x\equiv1 otag a\pmod6$. The original congruence has more than one solution class.

The Euclidean algorithm can find inverses. For instance,

Working backward gives

so $-5$ and $38$ are inverses of $17$ modulo $43$. This allows the equation

to be solved as

For a prime modulus $p$, Fermat's Little Theorem also gives

when $p\nmid a$. Use the Euclidean algorithm for small direct computations, and use exponentiation when powers are already part of the problem.

Advanced Competition Methods

Factorials and products often simplify through divisibility. If a factorial contains enough factors to include every prime factor of the modulus with sufficient multiplicity, its remainder is $0$. For example,

contains both $3$ and $17$, so it contains a factor of $51=3\cdot17$. Hence

For a prime $p$, Wilson's theorem states

For example,

A nearby factorial can be related to $(p-1)!$. Since

and $100!\equiv-1\pmod{101}$, we get

Thus, $2\cdot98!\equiv-1\pmod{101}$, and multiplying by the inverse of $2$ yields $98!\equiv50 otag a\pmod{101}$.

For factorial quotients, simplify the quotient as an ordinary integer before reducing whenever possible. Do not cancel factors inside a congruence unless the canceled factor has a modular inverse.

A dependable competition workflow is:

1. Identify the target modulus and factor it if useful.

2. Inspect factorials and products for immediate divisibility.

3. Reduce large bases to small congruent values.

4. Find a cycle or use repeated squaring for powers.

5. Apply Fermat's Little Theorem only when its conditions hold.

6. Replace division with multiplication by a modular inverse.

7. Convert negative answers to standard remainders and verify the result.