Skip to content
Tutorials Center
My learning

Topics

Lesson 6 of 86 Ā· Number System

Remainders and Cyclicity

Learn remainder rules, unit-digit cycles, Fermat's and Euler's theorems and find remainders of huge powers by hand, then check each one with code.

What is the last digit of 7¹²³? What is the remainder when 2¹⁰⁰ is divided by 7? These numbers are far too big to compute, yet aptitude tests ask for these answers in under a minute. The secret is that remainders behave very predictably. They repeat in cycles, and once you know the cycle length, a huge exponent shrinks to a tiny one.

This lesson teaches how remainders combine, how the last digits of powers cycle, and how two classic theorems (Fermat's and Euler's) shorten the work further. Every method is checked with a short script that does the exact calculation, so you can see that the shortcuts are exact and not approximations.

Remainder rules

When you divide a by m, the remainder is a mod m, a number from 0 to m āˆ’ 1. Writing a ≔ r (mod m) means a leaves remainder r when divided by m. Three rules do almost all the work:

  • Sum: the remainder of a + b equals the remainder of (r_a + r_b).
  • Product: the remainder of a Ɨ b equals the remainder of (r_a Ɨ r_b).
  • Power: the remainder of a^n equals the remainder of (r_a)^n.

Example: What is the remainder of 23 Ɨ 37 when divided by 8? 23 leaves 7 and 37 leaves 5. The product 7 Ɨ 5 = 35 leaves 3 when divided by 8. So the answer is 3 (indeed 23 Ɨ 37 = 851 = 106 Ɨ 8 + 3).

Using negative remainders

A remainder can be written as a negative number whenever it is shorter that way. 17 ≔ āˆ’1 (mod 18), so 17²⁰⁰ ≔ (āˆ’1)²⁰⁰ = 1 (mod 18). The remainder is 1. Because (āˆ’1) raised to an even power is 1 and to an odd power is āˆ’1, the remainder of 17²⁰¹ is āˆ’1, which is 17 once you add the modulus.

Another favorite: when the base is just above or below a multiple of the modulus, use it. 5² = 25 ≔ 1 (mod 24), so 5⁵⁰ = (5²)²⁵ ≔ 1²⁵ = 1 (mod 24).

Remainders of divisibility-rule moduli

You already know remainders by 9 and 3: a number leaves the same remainder as its digit sum. For 11 use the alternating sum. For 2, 4 and 8, only the last one, two or three digits matter, since 10, 100 and 1,000 are multiples of 2, 4 and 8.

The division algorithm

Every remainder question rests on one equation. For whole numbers N and d (with d > 0) there is exactly one quotient q and one remainder r with

N = d Ɨ q + r, where 0 ≤ r < d.

So 63 Ć· 4 gives q = 15 and r = 3, because 4 Ɨ 15 + 3 = 63. The condition r < d is what makes the answer unique: a "remainder" of 7 when dividing by 4 is not a remainder yet.

Negative numbers fit the same equation. For āˆ’17 Ć· 5 we need r between 0 and 4, so q = āˆ’4 and r = 3, since 5 Ɨ (āˆ’4) + 3 = āˆ’17.

Changing the divisor

If you know the remainder on dividing by a large number, you also know it for any factor of that number.

Example 1. A number leaves remainder 29 when divided by 56. Since 56 = 8 Ɨ 7, write N = 56q + 29. The first part is a multiple of 8, so the remainder by 8 is 29 mod 8 = 5. The remainder by 7 is 29 mod 7 = 1.

Example 2. A number leaves remainder 39 when divided by 357. Because 357 = 17 Ɨ 21, the remainder by 17 is 39 mod 17 = 5. This trick works only when the new divisor divides the old one.

Divide the quotient again

Example 3. A number N leaves remainder 3 when divided by 4. The quotient q leaves remainder 2 when divided by 5. Write q = 5k + 2, so N = 4(5k + 2) + 3 = 20k + 11. The remainder when N is divided by 20 is 11.

Adding remainders

Example 4. Two numbers leave remainders 7 and 11 when divided by 15. Their sum leaves (7 + 11) mod 15 = 18 mod 15 = 3.

Same remainder, find the divisor

Example 5. Find the largest number that divides 245 and 1,029 leaving remainder 5 each time. Subtract the remainder: 240 and 1,024 must both be multiples of the divisor, so it is HCF(240, 1,024). Since 240 = 2⁓ Ɨ 15 and 1,024 = 2¹⁰, the HCF is 16. (A divisor of 16 must also exceed the remainder 5, and 16 does.) See HCF and LCM for the method.

JS Check the division algorithm

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Unit digits and cyclicity

The last digit of a power depends only on the last digit of the base, and the sequence of last digits repeats.

Last digit of base Cycle of last digits (for exponents 1, 2, 3, …) Cycle length
0 0 1
1 1 1
2 2, 4, 8, 6 4
3 3, 9, 7, 1 4
4 4, 6 2
5 5 1
6 6 1
7 7, 9, 3, 1 4
8 8, 4, 2, 6 4
9 9, 1 2

Every cycle length is 1, 2 or 4, and all of these divide 4. So there is one rule for every digit: divide the exponent by 4; if the remainder is 0, use the last item of the cycle (position 4).

Example 1: Unit digit of 7¹²³. 123 ÷ 4 leaves 3, so take the third item of the 7-cycle: 7, 9, 3, 1. The answer is 3.

Example 2: Unit digit of 2¹⁰⁰ + 3¹⁰⁰. 100 leaves 0, so use the fourth item. For 2 that is 6, for 3 it is 1. The sum 6 + 1 = 7. The answer is 7.

Example 3 (a tower): Unit digit of 2^(3⁓). First compute the exponent's remainder by 4: 3⁓ = 81 and 81 mod 4 = 1. So the unit digit is the first item of the 2-cycle, 2.

flowchart TB
    A["Find unit digit of d^n"] --> B["Take the last digit of d"]
    B --> C["Divide n by 4 and keep the remainder r"]
    C --> D{"r = 0?"}
    D -- "Yes" --> E["Use position 4 of the cycle"]
    D -- "No" --> F["Use position r of the cycle"]

The cycle position comes from the exponent modulo 4.

The last two digits

For the last two digits, work modulo 100. Powers of many numbers return to 1 quickly: 7⁓ = 2,401 ≔ 1 (mod 100), so 7 has a cycle of 4 for the last two digits. For 7¹²³: 123 mod 4 = 3, so the last two digits equal those of 7³ = 343, which are 43. Any number ending in 5 has a square ending in 25.

The cycle of last digits is visible below. The script finds each cycle automatically by multiplying until the digit repeats.

JS Unit-digit cycles

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The cycles match the table. The last line computes 7¹²³ exactly with big integers and confirms that the unit digit is 3.

Fermat's little theorem

If p is prime and a is not a multiple of p, then

a^(p āˆ’ 1) ≔ 1 (mod p)

The exponent p āˆ’ 1 is a period: after that many multiplications you are back at 1. So an exponent only matters modulo p āˆ’ 1.

Example: The remainder of 3¹⁰⁰ divided by 7. Here p = 7, so 3⁶ ≔ 1. Since 100 = 6 Ɨ 16 + 4, 3¹⁰⁰ ≔ 3⁓ = 81 ≔ 4 (mod 7) because 81 = 11 Ɨ 7 + 4.

Example: The remainder of 2¹⁰⁰ divided by 7. The cycle is even shorter here: 2³ = 8 ≔ 1 (mod 7). With 100 = 3 Ɨ 33 + 1, 2¹⁰⁰ ≔ 2¹ = 2. The theorem guarantees that the cycle length divides p āˆ’ 1 = 6, and you should always look for a shorter cycle when one is obvious.

Euler's theorem

For any modulus n (not necessarily prime), define φ(n) (Euler's totient) as the count of numbers from 1 to n that are co-prime to n. Compute it from the prime factors:

φ(n) = n Ɨ (1 āˆ’ 1/p) Ɨ (1 āˆ’ 1/q) Ɨ …, over each distinct prime p, q dividing n

So φ(10) = 10 Ɨ ½ Ɨ ⁓⁄₅ = 4, φ(12) = 12 Ɨ ½ Ɨ ā…” = 4, φ(20) = 20 Ɨ ½ Ɨ ⁓⁄₅ = 8, and for a prime p, φ(p) = p āˆ’ 1 (Fermat's theorem is a special case).

Euler's theorem: if a and n are co-prime, a^φ(n) ≔ 1 (mod n).

Example: The remainder of 7¹⁰⁰ divided by 10. φ(10) = 4 and 7 and 10 are co-prime, so 7⁓ ≔ 1 (mod 10). 100 is a multiple of 4, so 7¹⁰⁰ ≔ 1 (mod 10).

Example: Remainder of 2¹⁰⁰ divided by 15. 2 and 15 are co-prime, φ(15) = 15 Ɨ ā…” Ɨ ā…˜ = 8, so 2⁸ ≔ 1. In fact 2⁓ = 16 ≔ 1 (mod 15), so 2¹⁰⁰ = (2⁓)²⁵ ≔ 1.

Remember the condition: a and n must be co-prime. The theorem does not apply to 6¹⁰⁰ mod 9, for example, since 6 and 9 share the factor 3.

Checking with exact arithmetic

The next script uses repeated squaring, the fast way for a computer to calculate a^n mod m, with big integers. It checks the worked examples, and then tests Fermat's and Euler's theorems over many values.

JS Verify remainders with modular exponentiation

Press Run (or Ctrl + Enter) to see the console output here.

No output.

The last line prints 0, not 1, which shows why the co-prime condition matters.

Strategy

  1. Unit digit question: use the cycle table and the exponent modulo 4.
  2. Remainder by a small number: reduce the base first, look for ±1 or an early return to 1.
  3. Remainder by a prime: use Fermat and reduce the exponent modulo p āˆ’ 1, but check for a shorter cycle.
  4. Remainder by a composite number: use Euler if the base is co-prime to it, or split the modulus into co-prime parts.
  5. Always sanity-check small cases when you are unsure of a pattern.

Check your understanding

Quick check Ā· 5 questions

of 5 answered You scored / 5 Ā· perfect!

  1. 1. What is the unit digit of 3^2025?

    2025 leaves remainder 1 when divided by 4, so take the first item of the 3-cycle (3, 9, 7, 1), which is 3.
  2. 2. What is the remainder when 2^50 is divided by 7?

    2^3 = 8 leaves 1 modulo 7. 50 = 3 x 16 + 2, so 2^50 leaves the same remainder as 2^2 = 4.
  3. 3. What is the remainder when 17^23 is divided by 16?

    17 leaves 1 when divided by 16, so any power of 17 also leaves 1.
  4. 4. What is Euler's totient of 20?

    phi(20) = 20 x (1 - 1/2) x (1 - 1/5) = 20 x 1/2 x 4/5 = 8.
  5. 5. What is the unit digit of 2^100 + 3^100?

    100 is a multiple of 4, so 2^100 ends in 6 and 3^100 ends in 1. Then 6 + 1 = 7.

Summary

  • Remainders of sums, products and powers can be found from the remainders of the parts; negative remainders (like 17 ≔ āˆ’1 mod 18) often shorten the work.
  • Unit digits of powers cycle with length 1, 2 or 4, so divide the exponent by 4 and use position 4 when the remainder is 0.
  • For last two digits, work modulo 100 and look for a short cycle (7⁓ ≔ 1 mod 100).
  • Fermat: a^(pāˆ’1) ≔ 1 (mod p) for a prime p not dividing a. Euler: a^φ(n) ≔ 1 (mod n) when a and n are co-prime.
  • Always check the co-prime condition, and look for cycles shorter than the theorem promises.

Next: Surds, Indices and Simplification, where you will learn the laws of exponents and how to simplify roots and expressions quickly.