Number Theory Problem Solving Guide

Number Theory · Axiom Academy

SUMMARY Number Theory Problem Solving Guide Essential strategies and techniques for tackling number theory problems with confidence. Direct Approach: Express numbers using divisor (e.g., if a|b , then b = ka for some integer k ) Factorization: Break down expressions into prime factors to reveal divisibility relationships Algebraic Manipulation: Rewrite expressions to isolate the divisor as a common factor Cases: Consider different cases based on remainders or properties of the numbers involved Use Induction When: The statement involves all natural numbers n , or when there's a recursive relationship Use Direct Proof When: You can manipulate algebraic expressions directly or when the statement doesn't involve a sequence Strong Induction: Apply when you need to assume the statement holds for all values up to k , not just k Hybrid Approach: Sometimes combine both—prove base cases directly, then use induction for the general pattern Euclidean Algorithm: Always the fastest method for computing gcd(a, b)—repeatedly apply gcd(a, b) = gcd(b, a mod b) Prime Factorization: For gcd, take minimum exponents; for lcm, take maximum exponents of each prime Key Identity: Remember that gcd(a, b) × lcm(a, b) = a × b Linear Combinations: Use Bezout's identity— gcd(a, b) = ax + by for some integers x, y Simplify Early: Reduce modulo n at each step to keep numbers manageable Use Properties: (a + b) mod n = ((a mod n) + (b mod n)) mod n , similarly for multiplication

This is the written version of the interactive lesson above. See the full Number Theory course.