8.6.b Number System -- Tips, Tricks, and Shortcuts

---

Trick 1: Quick Divisibility Checks (Combined Rules)

When you need to check divisibility by a composite number, break it into co-prime factors.

Divisible by 6   --> check 2 AND 3
Divisible by 12  --> check 4 AND 3   (not 2 and 6, since 2 and 6 are not co-prime)
Divisible by 15  --> check 3 AND 5
Divisible by 18  --> check 2 AND 9
Divisible by 24  --> check 8 AND 3
Divisible by 36  --> check 4 AND 9
Divisible by 72  --> check 8 AND 9

Why co-prime? The factors you pick must be co-prime (HCF = 1) so that checking them independently is sufficient. Checking divisibility by 2 and 6 for 12 would not work because 6 already contains 2.

---

Trick 2: Counting Factors Fast (Without Full Expansion)

You do not need to list all factors. Just find the prime factorization and apply the formula.

Quick mental process for 720:

720 / 2 = 360
360 / 2 = 180
180 / 2 = 90
90  / 2 = 45
45  / 3 = 15
15  / 3 = 5
5   / 5 = 1

720 = 2^4 x 3^2 x 5^1

Number of factors = (4+1)(2+1)(1+1) = 5 x 3 x 2 = 30

Shortcut for small numbers: For numbers up to 100, memorize the factorizations or spot them instantly.

Commonly tested:
48  = 2^4 x 3      --> (4+1)(1+1) = 10 factors
72  = 2^3 x 3^2    --> (3+1)(2+1) = 12 factors
96  = 2^5 x 3      --> (5+1)(1+1) = 12 factors
120 = 2^3 x 3 x 5  --> (3+1)(1+1)(1+1) = 16 factors
180 = 2^2 x 3^2 x 5 --> (2+1)(2+1)(1+1) = 18 factors

---

Trick 3: Unit Digit Cycle -- The 4-Step Shortcut

For any number, you only need to look at its unit digit and divide the power by 4.

Step 1: Note the unit digit of the base.
Step 2: Divide the exponent by 4 and note the remainder (call it r).
Step 3: If r = 0, the unit digit = (unit digit)^4.
        Otherwise, unit digit = (unit digit)^r.

Memorize the cycles (only 4 digits have cycle length 4):
  2: {2, 4, 8, 6}
  3: {3, 9, 7, 1}
  7: {7, 9, 3, 1}
  8: {8, 4, 2, 6}

Two digits have cycle length 2:
  4: {4, 6}
  9: {9, 1}

Four digits always give the same unit digit:
  0: always 0
  1: always 1
  5: always 5
  6: always 6

Ultra-fast example: Unit digit of 2347^893

Unit digit of base = 7
893 / 4 = 223 remainder 1
Cycle of 7: {7, 9, 3, 1}
Position 1 --> unit digit = 7

---

Trick 4: Unit Digit of Sums and Products

Unit digit of (A + B) = unit digit of (unit digit of A + unit digit of B)
Unit digit of (A x B) = unit digit of (unit digit of A x unit digit of B)

Example: Unit digit of 234^17 + 456^23

Unit digit of 234^17:
  Base unit = 4, cycle of 4: {4, 6}, 17 mod 2 = 1 --> unit digit = 4

Unit digit of 456^23:
  Base unit = 6, always 6 --> unit digit = 6

Sum's unit digit = unit digit of (4 + 6) = 0

---

Trick 5: Quick Prime Checking

To check if a number N is prime, you only need to test divisibility by primes up to sqrt(N).

To check if 97 is prime:
  sqrt(97) ≈ 9.8 --> test primes up to 9: {2, 3, 5, 7}

  97 / 2 = not even       ✓
  97 / 3 = 9+7=16, not divisible by 3  ✓
  97 / 5 = does not end in 0 or 5      ✓
  97 / 7 = 97/7 ≈ 13.8, not exact      ✓

  97 is prime.

6k +/- 1 filter: Every prime > 3 is of the form 6k+1 or 6k-1. So first check if the number is of this form.

Is 91 prime?
91 = 6 x 15 + 1  --> passes the 6k+1 test, so it COULD be prime
But: 91 = 7 x 13  --> NOT prime

The 6k +/- 1 test is necessary but not sufficient.

---

Trick 6: Remainder Shortcuts

Negative Remainder Trick

If remainder is negative, add the divisor.

Example: Remainder of 23 / 7
23 = 7 x 3 + 2  --> remainder = 2

But sometimes it is faster to compute:
23 = 7 x 4 - 5  --> remainder = 7 - 5 = 2  (same answer)

This is extremely useful in practice:

Remainder of 99 / 7:
99 = 7 x 14 + 1  --> remainder = 1

Faster: 99 = 100 - 1
Rem(100/7) = 2
Rem(99/7) = 2 - 1 = 1  ✓

Remainder of (a^n) / d -- Use Simplification

Remainder of 2^10 / 7:
2^10 = 1024
1024 / 7 = 146 remainder 2

Faster approach:
2^3 = 8 --> Rem(8/7) = 1
So 2^3 mod 7 = 1
2^10 = (2^3)^3 x 2^1 = (1)^3 x 2 = 2  ✓

Pattern: Remainder of (n-1) when divided by n

Rem(a/n) = some value r
Then Rem((n-1)/n) = n - 1   (always)

More useful:
Rem(a^even power / (a+1)) tends to be 1
Rem(a^odd power / (a+1)) tends to be a  (i.e., n-1 which equals -1)

Example: Rem(7^100 / 8)
7 = 8 - 1, so 7 mod 8 = -1
(-1)^100 = 1
Remainder = 1

---

Trick 7: Trailing Zeros -- The Quick Formula

Trailing zeros in n! = floor(n/5) + floor(n/25) + floor(n/125) + ...

For mental math, just keep dividing by 5 and add:

Example: Trailing zeros in 250!
250/5   = 50
250/25  = 10
250/125 = 2
250/625 = 0 (stop)
Total   = 50 + 10 + 2 = 62 trailing zeros

---

Trick 8: Finding the Last Two Digits

For the last two digits of a^n, compute a^n mod 100.

Special case for odd numbers ending in 1:

For numbers ending in 1:
(....1)^n --> last two digits depend on tens digit and n.

Example: 31^52
Tens digit = 3, power = 52
Last two digits = (unit digit is always 1)
Tens digit = (3 x 52) mod 10 = 156 mod 10 = 6
So last two digits = 61

General shortcut (Euler's theorem):

phi(100) = phi(4) x phi(25) = 2 x 20 = 40

For any number co-prime to 100:
a^40 mod 100 = 1

So to find last two digits of a^n:
Reduce n mod 40, then compute a^(n mod 40) mod 100.

---

Trick 9: Common Exam Patterns

Pattern 1: "Find the largest n-digit number divisible by k"

Largest n-digit number = 10^n - 1  (e.g., 999 for 3 digits)
Divide by k, take the floor, multiply back.

Answer = k x floor((10^n - 1) / k)

Example: Largest 3-digit number divisible by 7
999 / 7 = 142.71...
floor = 142
Answer = 7 x 142 = 994

Pattern 2: "Find the smallest n-digit number divisible by k"

Smallest n-digit number = 10^(n-1)  (e.g., 100 for 3 digits)
Divide by k, take the ceiling, multiply back.

Answer = k x ceil(10^(n-1) / k)

Example: Smallest 3-digit number divisible by 7
100 / 7 = 14.28...
ceil = 15
Answer = 7 x 15 = 105

Pattern 3: "How many factors of N are perfect squares?"

N = p1^a1 x p2^a2 x ... x pk^ak

A factor is a perfect square if all its prime exponents are even.
Even choices for exponent of pi: 0, 2, 4, ..., up to ai
Number of even values from 0 to ai = floor(ai/2) + 1

Number of perfect square factors = product of (floor(ai/2) + 1)

Example: N = 2^6 x 3^4 x 5^3
Perfect square factors = (6/2 + 1)(4/2 + 1)(3/2 + 1) = 4 x 3 x 2 = 24
         (since floor(3/2)=1, so 1+1=2 for the 5 part)

Pattern 4: "If N! ends in k zeros, find N"

Work backwards from the trailing zeros formula.
Multiply the zero count by 5 for a rough estimate, then verify.

Example: n! has 7 trailing zeros. Find n.
Estimate: 7 x 5 = 35
Check 35!: floor(35/5) + floor(35/25) = 7 + 1 = 8 (too many)
Check 30!: floor(30/5) + floor(30/25) = 6 + 1 = 7  ✓
Answer: n = 30 (and also 31, 32, 33, 34 give 7 zeros)

---

Trick 10: Digit Sum Casting (Casting Out Nines)

A number and its digit sum have the same remainder when divided by 9.

Example: Is 7 x 8 x 9 x 11 = 5,544?

Digit sum of 5544: 5+5+4+4 = 18 --> 1+8 = 9 --> remainder 0 when divided by 9

Product check: 7 x 8 x 9 x 11
Remainders mod 9: 7 x 8 x 0 x 2 = 0

Both give remainder 0 mod 9, consistent (not a proof, but a quick check).

---

Trick 11: Number of Co-primes Less Than N (Euler's Totient)

phi(N) = N x (1 - 1/p1) x (1 - 1/p2) x ...

Shortcut: 
phi(p) = p - 1                    (for prime p)
phi(p^k) = p^k - p^(k-1)         (for prime power)
phi(m x n) = phi(m) x phi(n)     (if m, n are co-prime)

Quick computation:

phi(36) = phi(4) x phi(9) = 2 x 6 = 12

Or: 36 = 2^2 x 3^2
phi(36) = 36 x (1 - 1/2) x (1 - 1/3) = 36 x 1/2 x 2/3 = 12

---

Trick 12: Sum of Digits Divisibility Shortcut

If a question asks "which of these is divisible by 9?", quickly sum the digits mentally. Use cascading sums for big numbers.

Is 987,654,321 divisible by 9?
9+8+7+6+5+4+3+2+1 = 45 --> 4+5 = 9 --> Yes!

Is 123,456,789 divisible by 9?
1+2+3+4+5+6+7+8+9 = 45 --> Yes!

---

Trick 13: Factorials and Divisibility

n! is always divisible by all integers from 1 to n.

Key results:
- Product of any k consecutive integers is divisible by k!
- n! is never a perfect square for n >= 2 (by Bertrand's postulate, there is always
  a prime between n/2 and n that appears exactly once in the factorization).

---

Trick 14: Quick GCD/LCM Without Prime Factorization

For GCD: Use successive subtraction or the Euclidean algorithm mentally.

GCD(48, 18):
48 - 18 = 30
30 - 18 = 12
18 - 12 = 6
12 - 6  = 6
GCD = 6

Faster (Euclidean):

GCD(48, 18):
48 = 18 x 2 + 12
18 = 12 x 1 + 6
12 = 6 x 2 + 0
GCD = 6

---

Trick 15: Identifying Perfect Squares Quickly

A perfect square can only end in: 0, 1, 4, 5, 6, or 9.
A perfect square NEVER ends in: 2, 3, 7, or 8.

Also:
- If it ends in 0, the number of trailing zeros must be even.
- If it ends in 5, the tens digit must be 2 (i.e., ends in 25).
- A perfect square, when divided by 4, gives remainder 0 or 1 (never 2 or 3).
- A perfect square, when divided by 3, gives remainder 0 or 1 (never 2).

---

Trick 16: The "Plus-Minus 1" Pattern

Many exam questions use the pattern:

a^n - 1 is divisible by (a - 1) for all positive integers n.
a^n + 1 is divisible by (a + 1) for all ODD positive integers n.

Example: 7^100 - 1 is divisible by 6 (since 7-1 = 6).
Example: 7^99 + 1 is divisible by 8 (since 7+1 = 8).

---

Summary of Key Shortcuts

Situation	Shortcut
Unit digit of a^n	Cyclicity (divide power by 4)
Divisibility by composite	Break into co-prime factors
Number of factors	Prime factorize, multiply (exponent+1) values
Perfect square factors	Multiply (floor(exp/2)+1) values
Trailing zeros in n!	Sum of floor(n/5^k)
Remainder of a^n / d	Reduce using Fermat/Euler, or use (d +/- 1) pattern
Is N prime?	Test primes up to sqrt(N)
Last two digits	Euler: reduce power mod 40, compute mod 100
Largest/smallest n-digit multiple of k	Floor/ceil division then multiply back
Quick verification	Casting out nines (digit sum mod 9)