Number Systems: Divisibility, Factors, Remainders & Bases

Number systems supply two to four of the twenty-two QA questions in a typical CAT paper, and a high share of them are TITA — type-in questions with no negative marking, because "find the remainder" has a single integer answer that needs no options. That is exactly why this topic rewards preparation out of proportion to its size: a remainder question that looks fearsome (7^100 divided by 11) is a thirty-second job once Fermat's theorem is in your hands, and a wrong attempt costs nothing. What CAT tests is never the rule itself but the two- or three-step combination — factorise, then count; reduce the base, then reduce the exponent; convert the base, then apply a divisibility test. This chapter builds that toolkit in order: classification and divisibility, the factor formulas from prime factorisation, HCF and LCM, the remainder theorems (Fermat, Euler, Wilson, Chinese remainder by inspection), cyclicity of last digits, Legendre's formula for factorials, and finally bases and digit sums.

Classification and Divisibility — Including 7, 11 and 13

The number line CAT works on is: natural numbers N = {1, 2, 3, …} ⊂ whole numbers W = {0, 1, 2, …} ⊂ integers Z ⊂ rationals Q (every p/q, whose decimals terminate or recur) ⊂ reals R, with the irrationals (√2, π) filling the gap between Q and R. Inside N, a prime has exactly two factors; 1 is neither prime nor composite, 2 is the only even prime, and there are exactly 25 primes below 100. Every prime greater than 3 has the form 6k ± 1 (the converse is false: 25 = 6·4 + 1). To test whether n is prime, trial-divide only by primes up to √n: for 221, √221 ≈ 14.9, so test 2, 3, 5, 7, 11, 13 — and 221 = 13 × 17 is composite. For 199 the same six tests all fail, so 199 is prime.

Divisibility rules CAT expects you to run in your head
DivisorTestExample
2, 5, 10Last digit7,340 → divisible by 2, 5 and 10
4, 25Last two digits3,716 → 16 ÷ 4 ✓; 8,175 → 75 ÷ 25 ✓
8, 125Last three digits45,104 → 104 = 8 × 13 ✓
3, 9Sum of digits divisible by 3 / by 95,283 → 18 → divisible by 9
11(Sum of digits in odd places) − (sum in even places) is 0 or a multiple of 119,163,845 → (9+6+8+5) − (1+3+4) = 28 − 8 = 20 ✗; 1,331 → (1+3) − (3+1) = 0 ✓
7Drop the last digit, subtract twice it from what remains; repeat3,157 → 315 − 14 = 301 → 30 − 2 = 28 ✓
13Drop the last digit, add four times it to what remains; repeat2,704 → 270 + 16 = 286 → 28 + 24 = 52 ✓
7, 11, 13 together1001 = 7 × 11 × 13. Group digits in threes from the right and take the alternating sum; test that against 7, 11 or 131,234,567 → 567 − 234 + 1 = 334 → remainders 5, 4, 9 by 7, 11, 13
Composite (6, 12, 15, 72, …)Split into co-prime parts and test each: 72 = 8 × 9, 12 = 3 × 4, 15 = 3 × 57,344 → 344 = 8 × 43 ✓ and 7+3+4+4 = 18 ✓ → divisible by 72
  • Any three-digit block repeated is divisible by 7, 11 and 13. abcabc = abc × 1001, and 1001 = 7 × 11 × 13. So 481,481 ÷ 13 leaves remainder 0 without a single division; likewise abab = ab × 101 and abcdabcd = abcd × 10001 = abcd × 73 × 137.
  • Reversing digits. For a two-digit number 10a + b, the reverse is 10b + a. Their sum is 11(a + b) and their difference is 9(a − b). So "a two-digit number exceeds its reverse by 27" means a − b = 3 in one line, and the sum of the two numbers is always a multiple of 11. The same holds for any length: a number minus its digit-reversal is always divisible by 9.
  • Worked example with unknown digits. If 4a3 + 984 = 13b7 and 13b7 is divisible by 11, find a and b. Units: 3 + 4 = 7 ✓. Hundreds: 4 + 9 = 13 exactly, which means the tens column produced no carry, so a + 8 = b with a + 8 ≤ 9, giving (a, b) = (0, 8) or (1, 9). Now the 11-test on 13b7: (1 + b) − (3 + 7) = b − 9 must be 0 or ±11, so b = 9, a = 1. Check: 413 + 984 = 1,397 = 11 × 127 ✓.
⚠️ Composite rules need co-prime pieces
"Divisible by 4 and by 6, therefore by 24" is false — 12 is divisible by both and not by 24. The pieces must share no factor: 24 = 8 × 3 (co-prime), not 4 × 6. Likewise test 72 as 8 × 9, never as 6 × 12, and 36 as 4 × 9, never as 6 × 6.

Factors from the Prime Factorisation; HCF and LCM

Write N = p^a · q^b · r^c (distinct primes). Then the number of factors is (a + 1)(b + 1)(c + 1), the sum of factors is (1 + p + … + p^a)(1 + q + … + q^b)(1 + r + … + r^c), and the product of all factors is N^(d/2) where d is the number of factors — because the factors pair up as (f, N/f) with product N. Worked fully on 360 = 2³ × 3² × 5: number of factors = 4 × 3 × 2 = 24; sum = (1 + 2 + 4 + 8)(1 + 3 + 9)(1 + 5) = 15 × 13 × 6 = 1,170; product = 360¹². The odd factors ignore the power of 2: 3 × 2 = 6, so the even factors are 24 − 6 = 18. Factors that are perfect squares take only even exponents: 2⁰ or 2², 3⁰ or 3², 5⁰ → 2 × 2 × 1 = 4 (namely 1, 4, 9, 36).

Everything CAT can ask about 360 = 2³ × 3² × 5
QuantityFormulaValue for 360
Number of factors(a+1)(b+1)(c+1)4 × 3 × 2 = 24
Sum of factorsΠ (1 + p + … + p^a)15 × 13 × 6 = 1,170
Product of factorsN^(d/2)360¹²
Ways to write N as a product of two factorsd/2 if N is not a perfect square; (d + 1)/2 if it is24/2 = 12
Ways to write N as a product of two co-prime factors2^(k−1), k = number of distinct primes2² = 4: (1, 360), (8, 45), (9, 40), (5, 72)
Odd factors / even factorsDrop the 2-power / subtract from total6 / 18
Factors that are perfect squaresCount even exponents only2 × 2 × 1 = 4
  • HCF and LCM from the factorisation. HCF takes the lowest power of each common prime; LCM takes the highest power of every prime present. For 360 = 2³·3²·5 and 84 = 2²·3·7: HCF = 2²·3 = 12, LCM = 2³·3²·5·7 = 2,520. For two numbers HCF × LCM = product: 12 × 2,520 = 30,240 = 360 × 84 ✓. This identity fails for three or more numbers — a frequent trap.
  • Fractions. HCF of fractions = HCF of numerators ÷ LCM of denominators; LCM of fractions = LCM of numerators ÷ HCF of denominators. For 2/3, 4/9, 8/15: HCF = HCF(2, 4, 8)/LCM(3, 9, 15) = 2/45; LCM = LCM(2, 4, 8)/HCF(3, 9, 15) = 8/3.
  • Bells (LCM). Three bells toll every 6, 8 and 12 seconds and start together. They toll together every LCM(6, 8, 12) = 24 s. In 30 minutes = 1,800 s that is 1,800/24 = 75 further times, so 76 times including the start — the "+1 for the start" is where marks are lost.
  • Tiles (HCF). The largest square tile that exactly paves a 4.5 m × 3.6 m floor has side HCF(450, 360) = 90 cm, and the number of tiles is (450/90) × (360/90) = 5 × 4 = 20.
  • Same remainder (HCF of differences). The greatest number that divides 62, 132 and 237 leaving the same remainder each time divides their differences 70, 105 and 175, so it is HCF(70, 105, 175) = 35 (the common remainder is 27). If instead the remainders are the divisors' deficits — N leaves 1, 2, 3 on division by 3, 4, 5 — then N + 2 is a multiple of LCM = 60, so the smallest N is 58.
🧠 Perfect squares have an odd number of factors
Only a perfect square has an odd factor count, because only there does one factor (√N) pair with itself. This answers "how many numbers below 100 have exactly 3 factors" instantly — a number with exactly 3 factors is p², so 4, 9, 25, 49: four. And it fixes the pair count: 3,600 = 2⁴·3²·5² has 5 × 3 × 3 = 45 factors, so it can be written as a product of two factors in (45 + 1)/2 = 23 ways, the extra one being 60 × 60.

Remainders — Fermat, Euler, Wilson and the Chinese Remainder Idea

The basic remainder theorem: the remainder of a product is the product of the remainders (reduced again), and the remainder of a sum is the sum of the remainders. So 17 × 23 × 31 on division by 7 becomes 3 × 2 × 3 = 18 → 4 (check: 12,121 = 7 × 1,731 + 4 ✓). A remainder may also be written negatively: 15 ≡ −1 (mod 16), so 15^20 ≡ (−1)^20 = 1 (mod 16). And 2⁴ = 16 ≡ −1 (mod 17), so 2^32 = (2⁴)⁸ ≡ (−1)⁸ = 1 (mod 17). Whenever a power of the base sits one below or one above the divisor, the negative-remainder route is the fastest.

The three named theorems and when each applies
TheoremStatementCondition
Fermat's little theorema^(p−1) ≡ 1 (mod p)p prime, p does not divide a
Euler's theorema^φ(n) ≡ 1 (mod n), where φ(n) = n(1 − 1/p)(1 − 1/q)… over the distinct primes of nHCF(a, n) = 1 — not required to be prime
Wilson's theorem(p − 1)! ≡ −1 (mod p), i.e. leaves remainder p − 1p prime. So 10! ÷ 11 leaves 10 and 28! ÷ 29 leaves 28
  • Fermat, worked. Remainder of 7^100 on division by 11: 11 is prime and does not divide 7, so 7^10 ≡ 1 (mod 11). Then 7^100 = (7^10)^10 ≡ 1^10 = 1. Again: 2^100 ÷ 13. Here 2^12 ≡ 1, and 100 = 12 × 8 + 4, so 2^100 ≡ 2⁴ = 16 ≡ 3 (mod 13). The whole method is "reduce the exponent modulo p − 1".
  • Euler, worked. Remainder of 2^100 on division by 9: HCF(2, 9) = 1 and φ(9) = 9(1 − 1/3) = 6, so 2⁶ ≡ 1 (mod 9). 100 = 6 × 16 + 4, so 2^100 ≡ 2⁴ = 16 ≡ 7 (mod 9). Cross-check by the negative route: 2³ = 8 ≡ −1, so 2^100 = (2³)^33 × 2 ≡ (−1)^33 × 2 = −2 ≡ 7 ✓. Useful values: φ(100) = 100 × ½ × ⅘ = 40, φ(20) = 8, φ(36) = 12, φ(p) = p − 1.
  • Chinese remainder by inspection. Find the smallest N with N ≡ 2 (mod 3), N ≡ 3 (mod 5), N ≡ 2 (mod 7). Start from the largest modulus: candidates 2, 9, 16, 23, 30, …; the first that leaves 3 on division by 5 is 23; and 23 ÷ 3 leaves 2 ✓. So N = 23, and the general solution is 23 + 105k. When all remainders are equal, N = LCM·k + r directly: leaves 3 on division by 4, 5, 6 → N = 60k + 3.
  • Divisor is a multiple of the new divisor. A number leaves 63 on division by 899 = 29 × 31. On division by 29 it leaves 63 mod 29 = 5, because N = 899q + 63 and 899q is already a multiple of 29. This works only when the new divisor divides the old one; otherwise the remainder cannot be determined.
  • Factorial sums. Remainder of 1! + 2! + 3! + … + 100! on division by 24: every term from 4! = 24 onward is a multiple of 24, so only 1 + 2 + 6 = 9 survives. The same idea gives 1! + 2! + … + 50! mod 5 → 1 + 2 + 6 + 24 = 33 → 3.
⚠️ Euler needs HCF(a, n) = 1
Asked for 6^100 mod 9, a candidate who writes φ(9) = 6 and "6^6 ≡ 1" is wrong from the first line — 6 and 9 share the factor 3, so the theorem does not apply. Here 6² = 36 ≡ 0 (mod 9), so the remainder is 0. Always check the HCF before reaching for φ(n); when the base shares a factor with the divisor, look for a power of the base that the divisor divides.

Cyclicity of Last Digits; Powers of a Prime in n!

The last digit of a^n depends only on the last digit of a and on n modulo the cycle length. Digits 0, 1, 5, 6 are fixed points; 4 and 9 alternate with period 2; and 2, 3, 7, 8 run a period-4 cycle. So the units digit of 3^47 is found from 47 ≡ 3 (mod 4): the third entry of 3, 9, 7, 1 is 7. For 2^50: 50 ≡ 2 (mod 4), second entry of 2, 4, 8, 6 is 4. When n is a multiple of 4, take the fourth entry, not the "zeroth" — 3^100 ends in 1, not 3.

Last-digit cycles
Last digit of baseCycle of last digits (n = 1, 2, 3, 4)Period
0, 1, 5, 6Same digit always1
44, 62 (odd power → 4, even → 6)
99, 12 (odd power → 9, even → 1)
22, 4, 8, 64
33, 9, 7, 14
77, 9, 3, 14
88, 4, 2, 64
  • Last two digits, base ending in 1. For (…a1)^n the units digit is 1 and the tens digit is the units digit of a × n. So 21^37 → tens = units of 2 × 37 = 74 → 4, giving 41. And 31^40 → units of 3 × 40 = 120 → 0, giving 01.
  • Last two digits, base ending in 3, 7 or 9. Raise to a power that ends in 1 first: 3⁴ = 81, 7⁴ = 2,401, 9² = 81. So 3^80 = (3⁴)^20 = 81^20 → tens = units of 8 × 20 = 160 → 0, giving 01. For 13^25: 13⁴ = 28,561 → treat as 61; 13^25 = (13⁴)⁶ × 13 → 61⁶ ends in (6 × 6 = 36 → 6)1 = 61, and 61 × 13 = 793 → 93.
  • Last two digits, even base. Use 2^10 = 1,024 → 24, and 24^odd → 24, 24^even → 76. So 2^100 = (2^10)^10 → 24^10 → 76. Any number ending in 25 keeps ending in 25; 76 keeps ending in 76; those two are the "fixed" endings.
  • Legendre's formula. The highest power of a prime p in n! is ⌊n/p⌋ + ⌊n/p²⌋ + ⌊n/p³⌋ + … In 100!: power of 5 = 20 + 4 = 24; power of 2 = 50 + 25 + 12 + 6 + 3 + 1 = 97; power of 3 = 33 + 11 + 3 + 1 = 48. Trailing zeros of n! = power of 5 (there are always more 2s), so 100! ends in 24 zeros and 125! in 25 + 5 + 1 = 31. For a composite like 6 = 2 × 3 take the minimum over the primes: 100! contains 6 to the power min(97, 48) = 48. For 12 = 2² × 3: min(⌊97/2⌋, 48) = min(48, 48) = 48.
  • Trailing zeros skip values. 24! has 4 trailing zeros and 25! jumps to 6, so no factorial ends in exactly 5 zeros — likewise none ends in exactly 11, 17, 23, 29 or 30. "Find n such that n! has exactly 30 zeros" has answer none; the 124! → 28, 125! → 31 jump skips 29 and 30. Zeros in another base follow the same idea: 10! in base 12 = 2² × 3 has min(⌊8/2⌋, 4) = 4 trailing zeros, since 10! carries 2⁸ and 3⁴.

Other Bases, and Digit Sums

In base b the digits run 0 to b − 1 and place values are 1, b, b², b³, … To convert to base b, divide repeatedly and read the remainders upward. 2,021 to base 8: 2,021 ÷ 8 = 252 remainder 5; 252 ÷ 8 = 31 remainder 4; 31 ÷ 8 = 3 remainder 7; 3 ÷ 8 = 0 remainder 3. Reading up: (3745)₈. Check by expanding: 3 × 512 + 7 × 64 + 4 × 8 + 5 = 1,536 + 448 + 32 + 5 = 2,021 ✓. To convert from base b, expand the place values: (1011)₂ = 8 + 0 + 2 + 1 = 11, and (2A5)₁₆ = 2 × 256 + 10 × 16 + 5 = 677.

  • Arithmetic in base b: carry at b, not at 10. (27)₈ + (15)₈: units 7 + 5 = 12 = 1 × 8 + 4, write 4 carry 1; then 2 + 1 + 1 = 4. Answer (44)₈. Check in decimal: 23 + 13 = 36 = 4 × 8 + 4 ✓. Subtraction borrows b: (52)₈ − (27)₈ → units 2 − 7 needs a borrow of 8: 10 − 7 = 3; then 4 − 2 = 2 → (23)₈ (42 − 23 = 19 = 2 × 8 + 3 ✓).
  • Find the base. "In some base, 34 = 2 × 15" → 3b + 4 = 2(b + 5) = 2b + 10 → b = 6. Check: (34)₆ = 22, (15)₆ = 11 ✓. A base must exceed every digit used, so an answer b = 4 with a digit 5 present is invalid — CAT uses this to kill one option.
  • Divisibility tests travel to any base. In base b, a number is divisible by b − 1 exactly when its digit sum is (the base-10 "rule of 9"), and by b + 1 when its alternating digit sum is (the "rule of 11"). So in base 8, (3745)₈ has digit sum 19 → 19 mod 7 = 5, and indeed 2,021 = 7 × 288 + 5 ✓. The number of digits of N in base b is ⌊log_b N⌋ + 1: 2,021 lies between 8³ = 512 and 8⁴ = 4,096, so it has 4 octal digits.

Digit sums and the digital root. Because 10 ≡ 1 (mod 9), every number is congruent to its digit sum modulo 9 — and modulo 3. Repeating the digit sum until one digit remains gives the digital root, which equals N mod 9 (with 9 standing for 0). Three consequences CAT uses:
(i) a number minus its digit sum is always divisible by 9;
(ii) the digital root of a perfect square is always 1, 4, 7 or 9, so a number with digital root 2, 3, 5, 6 or 8 (such as 4,325 → 14 → 5) cannot be a square;
(iii) the digital root of 2^100 is its remainder mod 9, which we computed above as 7. Counting digits: writing 1 to 999, each of the three places carries every digit 0–9 exactly 100 times, so the sum of all digits is 3 × 100 × 45 = 13,500; and writing 1 to 100 uses 9 + 90 × 2 + 3 = 192 digits.

🎯 Why this topic is TITA territory
A remainder, a count of trailing zeros, a base — each is a single integer, so CAT can set the question without options, and a wrong typed answer costs nothing. Two habits pay: always finish a number-system TITA with some integer rather than leaving it blank, and verify by a second route (negative remainder against Fermat, decimal expansion against a base conversion) because there is no option list to catch a slip.

Key takeaways

  • From N = p^a·q^b·r^c: factors (a+1)(b+1)(c+1), sum Π(1 + p + … + p^a), product N^(d/2); factor-pairs d/2, or (d+1)/2 for a perfect square; co-prime pairs 2^(k−1).
  • Test composite divisors through co-prime pieces (72 = 8 × 9, never 6 × 12), and remember 1001 = 7 × 11 × 13 makes any repeated three-digit block divisible by all three.
  • Fermat: a^(p−1) ≡ 1 (mod p) for prime p not dividing a; Euler: a^φ(n) ≡ 1 (mod n) only when HCF(a, n) = 1; Wilson: (p−1)! leaves p − 1. Reduce the exponent, then the base.
  • Trailing zeros of n! = ⌊n/5⌋ + ⌊n/25⌋ + ⌊n/125⌋ + …, and the count jumps at multiples of 25, so some values (5, 11, 30) are never attained.
  • In base b, carry at b, digits must be below b, the digit-sum test is for b − 1 and the alternating-sum test for b + 1; in base 10 every number is congruent to its digit sum modulo 9.

Practice questions (8)

Attempt each one before opening the answer. Every explanation names the tempting wrong option as well as the right one, because that is where marks are lost.

  1. The number of positive factors of 360 is:

    1. 12
    2. 24
    3. 18
    4. 6
    Show answer

    Answer: B — 24

    360 = 2³ × 3² × 5¹, so the number of factors is (3 + 1)(2 + 1)(1 + 1) = 4 × 3 × 2 = 24. The value 12 is the number of ways to write 360 as a product of two factors (24 ÷ 2) — a different question. The value 18 = 3 × 3 × 2 comes from forgetting to add 1 to the exponent of 2, and 6 = 3 × 2 × 1 is the bare product of the exponents with no +1 at all.

  2. If 4a3 + 984 = 13b7, where a and b are digits, and 13b7 is divisible by 11, then a + b equals:

    1. 9
    2. 1
    3. 8
    4. 10
    Show answer

    Answer: D — 10

    In the hundreds column 4 + 9 = 13 exactly matches the "13" of the result, so the tens column produced no carry: a + 8 = b, forcing (a, b) = (0, 8) or (1, 9). Apply the 11-test to 13b7: (1 + b) − (3 + 7) = b − 9 must be 0 or ±11, so b = 9 and a = 1, giving a + b = 10. Check: 413 + 984 = 1,397 = 11 × 127. The value 9 is b alone and 1 is a alone; the value 8 comes from stopping at the pair (0, 8) without running the divisibility test, which is exactly the step the question is built around.

  3. In how many ways can 3,600 be written as a product of two positive integers (order not mattering)?

    1. 23
    2. 22
    3. 45
    4. 46
    Show answer

    Answer: A — 23

    3,600 = 36 × 100 = 2⁴ × 3² × 5², so it has (4 + 1)(2 + 1)(2 + 1) = 45 factors. Because 45 is odd, 3,600 is a perfect square (60²), and the number of unordered factor pairs is (45 + 1)/2 = 23 — the pair 60 × 60 pairs with itself. The value 22 is 45/2 rounded down, which drops exactly that 60 × 60 pair. The value 45 is the factor count itself, and 46 is 45 + 1 without the halving.

  4. The number of trailing zeros at the end of 125! is:

    1. 25
    2. 30
    3. 31
    4. 62
    Show answer

    Answer: C — 31

    Each trailing zero needs one factor 2 and one factor 5, and 5s are scarcer, so count the power of 5 by Legendre's formula: ⌊125/5⌋ + ⌊125/25⌋ + ⌊125/125⌋ = 25 + 5 + 1 = 31. The value 25 stops after the first division and misses the extra 5s carried by 25, 50, 75, 100 and 125. The value 30 counts 25 + 5 but forgets that 125 = 5³ contributes a third 5. The value 62 doubles 31, as if each of the pairing 2s also had to be counted.

  5. The units digit of 7^83 is:

    1. 1
    2. 3
    3. 7
    4. 9
    Show answer

    Answer: B — 3

    Powers of 7 end in the cycle 7, 9, 3, 1 with period 4. Since 83 = 4 × 20 + 3, the units digit of 7^83 equals that of 7³ = 343, namely 3. The value 7 comes from misreading the remainder of 83 ÷ 4 as 1, the value 9 from taking it as 2, and the value 1 from treating 83 as a multiple of 4 — which would be right for 7^84, not 7^83.

  6. The remainder when 3^100 is divided by 7 is:

    1. 1
    2. 2
    3. 3
    4. 4
    Show answer

    Answer: D — 4

    By Fermat's little theorem 3⁶ ≡ 1 (mod 7), so the exponent may be reduced modulo 6: 100 = 6 × 16 + 4, and 3^100 ≡ 3⁴ = 81 = 7 × 11 + 4 → remainder 4. Direct check of the cycle 3, 2, 6, 4, 5, 1 confirms the fourth entry is 4. The value 1 assumes 100 is a multiple of 6. The value 2 comes from reducing the exponent modulo 7 instead of modulo 6 (100 ≡ 2 mod 7, then 3² = 9 → 2), which is the most common Fermat slip. The value 3 is 3¹, from reducing the exponent modulo 3.

  7. A number leaves a remainder of 63 when divided by 899. The remainder when the same number is divided by 29 is:

    1. 34
    2. 63
    3. 5
    4. 1
    Show answer

    Answer: C — 5

    Write N = 899q + 63. Since 899 = 29 × 31, the term 899q is a multiple of 29, so the remainder on division by 29 is that of 63 alone: 63 = 2 × 29 + 5, giving 5. The value 63 forgets that a remainder must be smaller than the divisor. The value 34 subtracts 29 only once (63 − 29) and stops. The value 1 is the remainder of 63 on division by 31, the other factor of 899 — the right method applied to the wrong divisor.

  8. The remainder when 7^100 is divided by 100 is:

    1. 1
    2. 7
    3. 49
    4. 43
    Show answer

    Answer: A — 1

    Compute 7⁴ = 2,401, which is 1 more than a multiple of 100, so 7⁴ ≡ 1 (mod 100) and 7^100 = (7⁴)^25 ≡ 1^25 = 1. The remainder is 1 — equivalently, 7^100 ends in the digits 01. Euler's theorem gives the same answer more slowly: φ(100) = 40, so 7^40 ≡ 1 and 7^100 = (7^40)² × 7^20 = 7^20 = (7⁴)⁵ ≡ 1. The value 7 is 7¹, from treating the exponent as if it reduced to 1; the value 49 is 7², from confusing the period 4 with a period 2; the value 43 is the last two digits of 7³ = 343, from taking 100 ≡ 3 in the period-4 cycle instead of 0.