Number Theory Fundamentals Every Competitor Should Know

Byyaniadmin

Category: Problem Solving
Reading Time: 9 minutes

Number theory appears in nearly every major math competition—from AMC 8 to MATHCOUNTS to Math Olympiad. Yet many students avoid these problems, viewing them as mysterious or overly complex.

The truth? Number theory is one of the most pattern-based, predictable areas of competition math. Master these fundamentals, and you’ll gain easy points that other students skip.

Why Number Theory Matters

Competition Frequency:

  • AMC 8: 4-6 problems (16-24% of test)
  • MATHCOUNTS: 5-8 problems (20-30% of test)
  • Math Olympiad: 2-3 problems per contest

The Advantage: While geometry requires visualization and algebra requires manipulation, number theory often rewards pattern recognition and systematic thinking—skills you can train.

Foundation 1: Divisibility Rules

The Essential Rules

Divisible by 2: Last digit is even (0, 2, 4, 6, 8)

  • Example: 1,234 is divisible by 2 (ends in 4)

Divisible by 3: Sum of digits is divisible by 3

  • Example: 147 → 1+4+7 = 12 → 12÷3 = 4 ✓
  • Example: 158 → 1+5+8 = 14 → 14÷3 ≠ integer ✗

Divisible by 4: Last two digits divisible by 4

  • Example: 3,416 → 16÷4 = 4 ✓
  • Example: 2,518 → 18÷4 ≠ integer ✗

Divisible by 5: Last digit is 0 or 5

  • Example: 1,275 ✓ (ends in 5)

Divisible by 6: Divisible by both 2 AND 3

  • Example: 144 → even ✓ and 1+4+4=9 (divisible by 3) ✓

Divisible by 8: Last three digits divisible by 8

  • Example: 12,816 → 816÷8 = 102 ✓

Divisible by 9: Sum of digits divisible by 9

  • Example: 729 → 7+2+9 = 18 → 18÷9 = 2 ✓

Divisible by 10: Last digit is 0

  • Example: 1,290 ✓

Divisible by 11: Alternating sum of digits is divisible by 11

  • Example: 2,728 → 2-7+2-8 = -11 → divisible by 11 ✓
  • Example: 1,331 → 1-3+3-1 = 0 → divisible by 11 ✓

Competition Application

Problem Type: “Find the smallest four-digit number divisible by 9”

Solution:

  • Smallest four-digit: 1,000
  • Sum of digits: 1+0+0+0 = 1
  • Need sum divisible by 9, so add 8
  • Answer: 1,008

Time Saved: 30 seconds vs. division

Foundation 2: Prime Numbers

What You Must Know

Definition: A number greater than 1 with exactly two factors: 1 and itself

First 25 Primes (Memorize These): 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97

Key Facts:

  • 2 is the only even prime
  • 1 is NOT prime
  • All primes > 2 are odd (but not all odd numbers are prime)

Testing for Primality

For numbers < 100:

To test if n is prime, check if it’s divisible by primes up to √n

Example: Is 89 prime?

  • √89 ≈ 9.4
  • Test primes up to 9: 2, 3, 5, 7
  • 89 is odd (not divisible by 2)
  • 8+9=17, not divisible by 3
  • Doesn’t end in 0 or 5 (not divisible by 5)
  • 89÷7 = 12.7… (not divisible by 7)
  • 89 is prime ✓

Prime Factorization

Every number can be expressed as a product of primes

Example: 360

360 = 2 × 180
    = 2 × 2 × 90
    = 2 × 2 × 2 × 45
    = 2 × 2 × 2 × 3 × 15
    = 2 × 2 × 2 × 3 × 3 × 5
    = 2³ × 3² × 5

Factor Tree Method:

        360
       /   \
      2    180
          /   \
         2    90
             /  \
            2   45
               /  \
              3   15
                 /  \
                3    5

Competition Shortcut: Divide by smallest prime repeatedly

Foundation 3: GCD and LCM

Greatest Common Divisor (GCD)

Definition: Largest number that divides both numbers

Method 1: List Factors

Find GCD(24, 36):

  • Factors of 24: 1, 2, 3, 4, 6, 8, 12, 24
  • Factors of 36: 1, 2, 3, 4, 6, 9, 12, 18, 36
  • Common factors: 1, 2, 3, 4, 6, 12
  • GCD = 12

Method 2: Prime Factorization (Faster!)

Find GCD(24, 36):

  • 24 = 2³ × 3
  • 36 = 2² × 3²
  • GCD = 2² × 3 = 12 (use lowest power of each common prime)

Method 3: Euclidean Algorithm (Fastest for large numbers!)

Find GCD(24, 36):

  • 36 = 24 × 1 + 12
  • 24 = 12 × 2 + 0
  • GCD = 12 (last non-zero remainder)

Least Common Multiple (LCM)

Definition: Smallest number that both numbers divide into

Method 1: List Multiples

Find LCM(6, 8):

  • Multiples of 6: 6, 12, 18, 24, 30…
  • Multiples of 8: 8, 16, 24, 32…
  • LCM = 24

Method 2: Prime Factorization (Better!)

Find LCM(6, 8):

  • 6 = 2 × 3
  • 8 = 2³
  • LCM = 2³ × 3 = 24 (use highest power of each prime)

Method 3: Formula (Fastest!)

LCM(a,b) = (a × b) / GCD(a,b)

Find LCM(6, 8):

  • GCD(6, 8) = 2
  • LCM = (6 × 8) / 2 = 48 / 2 = 24

Competition Applications

Problem: “What is the smallest positive integer divisible by 6, 8, and 12?”

Solution: Find LCM(6, 8, 12)

  • 6 = 2 × 3
  • 8 = 2³
  • 12 = 2² × 3
  • LCM = 2³ × 3 = 24

Problem: “Two bells ring every 6 and 8 minutes. If they ring together at noon, when do they next ring together?”

Solution: Find LCM(6, 8) = 24 Answer: 12:24 PM

Foundation 4: Modular Arithmetic (Remainders)

Understanding Remainders

Notation: a ≡ b (mod m) means “a and b have the same remainder when divided by m”

Examples:

  • 17 ≡ 2 (mod 5) because 17 = 3×5 + 2 and 2 = 0×5 + 2
  • 23 ≡ 3 (mod 10) because both have remainder 3 when divided by 10

Modular Arithmetic Rules

Addition: (a + b) mod m = [(a mod m) + (b mod m)] mod m

Example: What is the remainder when 47 + 38 is divided by 5?

  • 47 mod 5 = 2
  • 38 mod 5 = 3
  • (2 + 3) mod 5 = 0

Multiplication: (a × b) mod m = [(a mod m) × (b mod m)] mod m

Example: What is the remainder when 23 × 17 is divided by 7?

  • 23 mod 7 = 2
  • 17 mod 7 = 3
  • (2 × 3) mod 7 = 6

Pattern Recognition with Remainders

Problem: “What is the units digit of 3²⁰?”

Solution: Find the pattern of units digits

  • 3¹ = 3
  • 3² = 9
  • 3³ = 27 (units digit 7)
  • 3⁴ = 81 (units digit 1)
  • 3⁵ = 243 (units digit 3) → Pattern repeats!

Pattern: 3, 9, 7, 1, 3, 9, 7, 1… (cycle of 4)

  • 20 ÷ 4 = 5 remainder 0
  • Remainder 0 means we’re at the end of a cycle
  • Answer: 1 (the 4th element)

Divisibility Using Modular Arithmetic

Problem: “Is 7²⁰ + 3 divisible by 4?”

Solution:

  • 7 ≡ 3 (mod 4) → 7 leaves remainder 3 when divided by 4
  • 7² ≡ 3² ≡ 9 ≡ 1 (mod 4)
  • 7²⁰ = (7²)¹⁰ ≡ 1¹⁰ ≡ 1 (mod 4)
  • 7²⁰ + 3 ≡ 1 + 3 ≡ 4 ≡ 0 (mod 4)
  • Yes, it’s divisible by 4 ✓

Foundation 5: Perfect Squares and Cubes

Perfect Squares (Memorize 1-20)

1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289, 324, 361, 400

Key Patterns:

  • All perfect squares end in: 0, 1, 4, 5, 6, 9 (never 2, 3, 7, 8)
  • Between n² and (n+1)²: 2n+1 integers
  • Difference of consecutive squares: (n+1)² – n² = 2n+1

Perfect Square Testing

Is 784 a perfect square?

Method 1: Check last digit (4 ✓) Method 2: Estimate √784

  • 20² = 400
  • 30² = 900
  • Try 28: 28² = 784 ✓

Quick Check: Perfect squares modulo 4 are always 0 or 1

  • 784 mod 4 = 0 ✓ (could be a perfect square)
  • 785 mod 4 = 1 ✓ (could be a perfect square)
  • 786 mod 4 = 2 ✗ (definitely NOT a perfect square)

Perfect Cubes (Memorize 1-10)

1, 8, 27, 64, 125, 216, 343, 512, 729, 1,000

Key Pattern: Sum of first n odd numbers = n² Sum of first n cubes = [n(n+1)/2]²

Example: 1³ + 2³ + 3³ + 4³ = ?

  • [4(4+1)/2]² = [10]² = 100

Foundation 6: Special Numbers

Fibonacci Numbers

Sequence: 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144… Rule: Each term is sum of previous two

Competition Tip: Know first 12 terms by heart

Triangular Numbers

Sequence: 1, 3, 6, 10, 15, 21, 28, 36, 45, 55… Formula: T_n = n(n+1)/2

Visual: Arranging dots in triangular pattern

•              •            •
             • •          • •
                        • •  •

Application: Counting handshakes, pairs, combinations

Factorial

Definition: n! = n × (n-1) × (n-2) × … × 2 × 1

Examples:

  • 5! = 5 × 4 × 3 × 2 × 1 = 120
  • 10! = 3,628,800

Special: 0! = 1 (by definition)

Divisibility Fact: n! is divisible by all numbers from 1 to n

Foundation 7: Diophantine Equations

Linear Diophantine Equations

Form: ax + by = c (find integer solutions)

Key Theorem: Solutions exist if and only if GCD(a, b) divides c

Example: 6x + 9y = 21

Solution exists? GCD(6, 9) = 3, and 3 divides 21 ✓

Finding Solutions:

  • Simplify: Divide by GCD: 2x + 3y = 7
  • Guess and check or systematic trial:
    • If y = 1: 2x + 3 = 7 → 2x = 4 → x = 2 ✓
  • One solution: (2, 1)
  • General solution: x = 2 + 3t, y = 1 – 2t (for integer t)

The Chicken McNugget Theorem (Frobenius Coin Problem)

For two coprime numbers a and b: Largest number that CANNOT be made using combinations of a and b is: ab – a – b

Example: McNuggets come in boxes of 6 and 9

  • GCD(6, 9) = 3 (not coprime!)
  • Simplify to 2 and 3 (divide by GCD)
  • Largest unmakeable with 2 and 3: (2)(3) – 2 – 3 = 1
  • Scale back up: 1 × 3 = 3
  • Largest unmakeable: 3 McNuggets (but any multiple of 3 ≥ 6 is makeable)

For coprime a and b: Largest = ab – a – b

  • Example: 6 and 7 (coprime)
  • Largest unmakeable: (6)(7) – 6 – 7 = 35

Competition Problem Types

Type 1: Digital Root Problems

Problem: “Find all two-digit numbers where the product of digits equals 24”

Solution: List factor pairs of 24:

  • 1 × 24 (no, 24 isn’t a digit)
  • 2 × 12 (no, 12 isn’t a digit)
  • 3 × 8 ✓ → 38, 83
  • 4 × 6 ✓ → 46, 64

Answer: 38, 46, 64, 83

Type 2: Remainder Problems

Problem: “When n is divided by 7, the remainder is 5. What is the remainder when 3n is divided by 7?”

Solution:

  • n ≡ 5 (mod 7)
  • 3n ≡ 3 × 5 ≡ 15 ≡ 1 (mod 7)

Answer: 1

Type 3: Counting Factors

Problem: “How many positive divisors does 72 have?”

Solution:

  • Prime factorization: 72 = 2³ × 3²
  • Formula: (3+1)(2+1) = 4 × 3 = 12

Why it works: Each divisor uses 0 to 3 factors of 2 (4 choices) and 0 to 2 factors of 3 (3 choices)

Type 4: Last Digit Problems

Problem: “What is the units digit of 7⁵⁰?”

Solution:

  • Pattern of 7’s units digits: 7, 9, 3, 1, 7, 9, 3, 1… (cycle of 4)
  • 50 ÷ 4 = 12 remainder 2
  • Answer: 9 (the 2nd in the cycle)

Your Number Theory Toolkit

Things to Memorize

Essential:

  • Divisibility rules (2, 3, 4, 5, 6, 8, 9, 10, 11)
  • First 25 prime numbers
  • Perfect squares 1-20
  • Perfect cubes 1-10
  • First 12 Fibonacci numbers

Formulas:

  • LCM(a,b) × GCD(a,b) = a × b
  • Number of divisors: (e₁+1)(e₂+1)… where n = p₁^e₁ × p₂^e₂ × …
  • Triangular number: n(n+1)/2
  • Sum of 1 to n: n(n+1)/2

Problem-Solving Strategy

Step 1: Identify the Type

  • Divisibility?
  • Primes?
  • Remainders/modular arithmetic?
  • GCD/LCM?
  • Counting factors?

Step 2: Choose Your Tool

  • Prime factorization (most versatile)
  • Divisibility rules (for quick checks)
  • Modular arithmetic (for patterns and remainders)
  • Systematic listing (when in doubt)

Step 3: Check Your Answer

  • Does it make sense?
  • Test with small examples
  • Verify divisibility claims

Practice Resources

Books:

  • Art of Problem Solving: Introduction to Number Theory
  • Beast Academy 5: Integers
  • MATHCOUNTS School Handbook (Number Theory sections)

Online:

  • Alcumus (AoPS) – Adaptive practice
  • Brilliant.org – Number Theory course
  • YaniPrep – Structured number theory lessons

Practice Problems:

  • AMC 8 past tests (problems 10-20 usually include number theory)
  • MATHCOUNTS Chapter/State/National Sprint problems
  • Math Olympiad problems (often have elegant number theory solutions)

Final Thoughts

Number theory is the “great equalizer” in competition math. Unlike geometry (which requires visualization) or algebra (which requires manipulation), number theory rewards systematic thinking and pattern recognition—skills anyone can develop.

Start with:

  1. Memorize divisibility rules and first 25 primes
  2. Practice prime factorization daily
  3. Master GCD and LCM
  4. Explore modular arithmetic patterns

Remember: Every expert struggled with “simple” concepts like why 1 isn’t prime or how modular arithmetic works. The difference? They kept practicing until the patterns became obvious.

Your advantage: Most students skip number theory problems. Master these fundamentals, and you’ll gain 4-6 easy points that others leave blank.

Related Articles

  • 10 Proven Strategies to Ace the AMC 8
  • Building Mental Math Speed for Competitions
  • Counting & Probability: From Basic to Advanced

Ready to practice? Download our Number Theory Problem Set with solutions and start building your skills today!

Leave a Reply

Your email address will not be published. Required fields are marked *