Number Theory and Arithmetic
Core concepts
Candidates must handle divisibility rules, prime factorization, greatest common divisor and least common multiple, remainders and modular arithmetic, and the distinction between rational and irrational numbers. Be fluent with the Euclidean algorithm and with converting repeating decimals to fractions.
Traps
- "Divisible by" vs "divides": keep the direction of the relation straight.
- LCM/GCD of more than two numbers: compute pairwise or via prime factorization; do not average.
- Remainders with negatives: the remainder is conventionally in [0, m).
- Counting multiples in a range: use floor division and check endpoints.
- Coprime does not mean prime.
Rule of thumb
For divisibility by 3 or 9, sum the digits; for 4, inspect the last two digits; for 8, the last three; for 11, alternate digit sums.
Worked example
Find the least positive integer leaving remainder 3 when divided by 5 and remainder 4 when divided by 7. Write n = 5a + 3. Testing a = 0,1,2,...: candidates 3, 8, 13, 18, 23, 28, 33. Check mod 7: 3→3, 8→1, 13→6, 18→4. So n = 18 works, and solutions repeat every 35. The answer is 18.