Number Theory Toolkit

Every rule works the same way: most of the number is a multiple of the divisor, so only a few digits can affect the remainder. $100$ is a multiple of $4$, so $4$ sees only the last two digits; $1000$ is a multiple of $8$, so $8$ sees the last three; every power of $10$ is one more than a multiple of $9$, so $9$ sees the digit sum. To test a composite divisor, split it into factors that share nothing — $12 = 3\cdot4$, $36 = 4\cdot9$ — and test each.

Step 1 — the rule: the digit sum must be a multiple of $9$.

Step 2 — the known digits give $4 + 2 + 8 = 14$.

Step 3 — a single digit $d$ makes the sum $14 + d$, which is between $14$ and $23$; the only multiple of $9$ there is $18$, so $d = 4$. Check: $4248 = 9\cdot472$.

Step 1 — split $12 = 3\cdot4$; the factors share nothing, so the number must pass both tests.

Step 2 — the test for $4$ looks at the last two digits, $d4$: $04, 24, 44, 64, 84$ are multiples of $4$ and $14, 34, 54, 74, 94$ are not, so $d$ is even.

Step 3 — the test for $3$: $5 + 7 + d + 4 = 16 + d$ must be a multiple of $3$, so $d$ is $2$, $5$ or $8$.

Step 4 — both: $d = 2$ or $8$, and the largest is $8$. Check: $5784 = 12\cdot482$.

Step 1 — the alternating sum from the units digit: $2 - A + 5 - A + 7 = 14 - 2A$.

Step 2 — it must be a multiple of $11$. Since $A$ is a digit, $14 - 2A$ lies between $-4$ and $14$, so it is $0$ or $11$.

Step 3 — $14 - 2A = 11$ has no whole-number solution, and $14 - 2A = 0$ gives $A = 7$. Check: $77572 = 11\cdot7052$. The rule works because $10$ is one less than $11$, so the powers of $10$ alternate between one more and one less than multiples of $11$.

Why the divisor formula works: a divisor of $2^3\cdot3^2$ must be built from the same primes with exponents no larger, so it is $2^a3^b$ with $a$ chosen from $0, 1, 2, 3$ and $b$ from $0, 1, 2$ — four choices times three choices. Every question about divisors, perfect squares, and common factors becomes a question about exponents, which is why factoring comes first.

Step 1 — split into any two factors, $504 = 8\cdot63$, and keep splitting until every end is prime: $8 = 2\cdot2\cdot2$ and $63 = 7\cdot9 = 7\cdot3\cdot3$.

Step 2 — collect: $504 = 2^3\cdot3^2\cdot7$.

Step 3 — the divisor count is $(3 + 1)(2 + 1)(1 + 1) = 24$. Starting with $504 = 4\cdot126$ or $504 = 12\cdot42$ gives a different tree with the same primes at the ends — that is the uniqueness of prime factorization.

Step 1 — work backwards from the formula: $10$ divisors means the product of (exponent $+ 1$) is $10$, so the exponents are $9$ (one prime) or $4$ and $1$ (two primes).

Step 2 — smallest of each shape: $2^9 = 512$; and $2^4\cdot3 = 48$, putting the bigger exponent on the smaller prime ($3^4\cdot2 = 162$ is larger).

Step 3 — the answer is $48$. Its divisors: $1, 2, 3, 4, 6, 8, 12, 16, 24, 48$.

Step 1 — factor: $180 = 2^2\cdot3^2\cdot5$.

Step 2 — a perfect cube has every exponent a multiple of $3$, so raise each exponent to the next multiple of $3$: $2^2 \to 2^3$ needs one $2$, $3^2 \to 3^3$ needs one $3$, $5^1 \to 5^3$ needs two $5$s.

Step 3 — $k = 2\cdot3\cdot5^2 = 150$, and $180\cdot150 = 27000 = 30^3$.

Why the identity holds: in the prime factorizations, the gcd takes the SMALLER exponent of each prime and the lcm the LARGER. For $12 = 2^2\cdot3$ and $18 = 2\cdot3^2$ the gcd is $2\cdot3 = 6$ and the lcm is $2^2\cdot3^2 = 36$. For each prime, smaller exponent plus larger exponent equals the two exponents added, so $\gcd\cdot\text{lcm}$ has exactly the primes of $ab$.

Step 1 — the first bell rings at multiples of $12$ minutes after noon, the second at multiples of $18$.

Step 2 — they coincide at common multiples, first at $\text{lcm}(12, 18) = 36$.

Step 3 — $12{:}36$. (Using the gcd here is the classic slip: $6$ minutes after noon neither bell rings.)

Step 1 — the identity: $\gcd\cdot\text{lcm} = ab$, so $6\cdot180 = 36b$.

Step 2 — $b = 1080/36 = 30$.

Step 3 — check, because the identity can give a number that fails: $\gcd(36, 30) = 6$ and $\text{lcm}(36, 30) = 180$. Both hold.

Step 1 — the tile's side must divide both $84$ and $60$, and the largest such side is $\gcd(84, 60) = 12$ ($84 = 2^2\cdot3\cdot7$, $60 = 2^2\cdot3\cdot5$).

Step 2 — the floor holds $84/12 = 7$ tiles along one side and $60/12 = 5$ along the other.

Step 3 — $7\cdot5 = 35$ tiles.

The count comes straight from the factorization: each divisor chooses an exponent for each prime independently, from $0$ to $a_i$. So $72 = 2^3\cdot3^2$ has $(3+1)(2+1) = 12$ divisors, and their sum is $\dfrac{2^4-1}{1}\cdot\dfrac{3^3-1}{2} = 15\cdot13 = 195$. A perfect square is exactly a number with an ODD divisor count, because only then is some $a_i+1$ product odd — that fact alone answers a whole family of contest questions about lockers and lightbulbs.

To find the units digit of $7^{2026}$, divide the exponent by the cycle length: $2026 = 4\cdot506 + 2$, so it matches $7^2$, units digit $9$. Two traps: an exponent that is a multiple of the cycle length lands on the LAST entry of the cycle, not the first ($7^{4}$ ends in $1$, not $7$); and the cycle is about the units digit only — for the last TWO digits you need to work modulo $100$.

Step 1 — factor: $600 = 2^3\cdot3\cdot5^2$, so $d(600) = 4\cdot2\cdot3 = 24$ divisors.

Step 2 — the units digit of $3^k$ cycles $3,9,7,1$ with period $4$, and $600 = 4\cdot150$ exactly, so $3^{600}$ matches the last entry of the cycle: units digit $1$. Both halves are the same idea — read the answer off the structure instead of computing the number.

Step 1 — divisors pair up as $d$ and $n/d$, so the count is odd exactly when one divisor is paired with itself, $d = n/d$, which means $n = d^2$ is a perfect square.

Step 2 — the squares up to $60$ are $1, 4, 9, 16, 25, 36, 49$.

Step 3 — the answer is $7$. No divisor counting was needed; the pairing did the work.

Step 1 — translate with the formula: the product of (exponent $+ 1$) is $3$, and $3$ is prime, so there is one prime with exponent $2$: the number is $p^2$.

Step 2 — its divisors are $1, p, p^2$, exactly three.

Step 3 — $p^2 < 100$ means $p < 10$: $p = 2, 3, 5, 7$, giving $4, 9, 25, 49$. The answer is $4$.

Step 1 — write it as a product: $abcabc = abc\cdot1000 + abc = abc\cdot1001$.

Step 2 — factor $1001 = 7\cdot11\cdot13$.

Step 3 — so $abcabc = abc\cdot7\cdot11\cdot13$ is divisible by all three, whatever the digits. For example $358358 = 358\cdot1001$. Seeing the structure — "repeat" means "multiply by $1001$" — replaces three long divisions.