Number Theory and Discrete Mathematics
Core ideas
Be comfortable with divisibility, primes and prime factorization, greatest common divisor and least common multiple, modular arithmetic, and base representation. Know the division algorithm, the Euclidean algorithm, and how gcd and lcm relate: gcd(a,b) * lcm(a,b) = a*b for positive integers. Understand parity arguments, the pigeonhole principle, and basic counting of integer solutions.
Traps to watch
- 1 is not prime; 2 is the only even prime.
- Confusing gcd with lcm when simplifying or combining cycles.
- Sign errors in modular arithmetic; reduce to the least nonnegative residue.
- Assuming a number is prime without checking divisors up to its square root.
- Forgetting that divisibility rules give necessary but sometimes insufficient conditions.
Worked example
Find the last two digits of 7^2024. Work mod 100. Powers of 7 cycle: 7, 49, 43, 1 (mod 100) with period 4. Since 2024 = 4*506, the exponent is a multiple of 4, so 7^2024 ≡ 1 (mod 100). Last two digits: 01. Spotting the cycle length is the key move.
Rule of thumb
For large-power or last-digit problems, compute small powers until the residues repeat; the cycle length then reduces the exponent modulo that length.