Number Theory - IOQM Study Guide
Number Theory on IOQM tests exact integer reasoning: divisibility, residues, primes, gcd and lcm, and Diophantine constraints. The paper asks for a single integer answer in the range 00–99, so a residue or a small count is usually enough; a formal proof is not required, but every shortcut must be justified.
Core rules and concepts
- Write divisibility through prime factorisation. If a|c and b|c with gcd(a,b)=1, then ab|c.
- Congruences respect +, −, ×. Divide only by a unit modulo m; do not divide by a non-coprime factor.
- Reduce exponents using the cycle length of the base modulo m, or Euler/Fermat when gcd(base,m)=1.
- Use gcd(a,b)·lcm(a,b)=ab, and factor out gcds before counting.
- Eliminate cases with mod 3, 4, 8, 9, 10, 11. Perfect squares are 0,1,4,5,6,9 mod 10.
Worked example
Find the remainder when 7^{2024} is divided by 100. Compute 7^2=49, 7^4=2401≡1 (mod 100). Hence powers repeat with period dividing 4. Since 2024=4·506, 7^{2024}≡(7^4)^{506}≡1 (mod 100). The two-digit answer is 01. The shortcut works because gcd(7,100)=1; the period is 4, not φ(100)=40.
Traps that cost marks
- Reducing the exponent modulo 100 without checking coprimality.
- Replacing lcm(a,b) by ab when a and b are not coprime.
- Counting 0 or negative values after the problem says “positive”.
- Entering 0 as “0” instead of “00”.
- Declaring a number prime after testing only 2, 3, 5; test primes up to √n. Remember that 1 is not prime.