Number Theory

1.Divisibility and digit sums

We write $b \mid a$ when $a = bk$ for some integer $k$. Divisibility is preserved by sums and differences. If $a = dx$ and $b = dy$, then $a + b = d(x+y)$ and $a - b = d(x-y)$, so $d \mid a$ and $d \mid b$ force $d \mid (a+b)$ and $d \mid (a-b)$. This closure is what makes divisibility tests work: you only need the remainders of the pieces of a number, not the number itself.

The test for $9$ comes from one observation, $10 = 9 + 1$, so $10 \equiv 1 \pmod 9$. Writing $N = \sum_i d_i 10^i$ and reducing each power of $10$ gives $N \equiv \sum_i d_i \pmod 9$. So $N$ and its digit sum leave the same remainder on division by $9$. For example $385 = 9 \cdot 42 + 7$, and $3 + 8 + 5 = 16 \equiv 7 \pmod 9$. The same argument with $10 \equiv 1 \pmod 3$ gives the test for $3$.

The test for $11$ uses $10 \equiv -1 \pmod{11}$. Each digit in an odd position gets weight $+1$ and each digit in an even position gets weight $-1$, so $N$ and its alternating digit sum agree mod $11$. For $385 = 11 \cdot 35$, the alternating sum is $5 - 8 + 3 = 0$, as it must be.

Tests for $4$ and $8$ depend only on the last few digits, because $100 = 4 \cdot 25$ and $1000 = 8 \cdot 125$. More generally, $10^k$ is a multiple of $2^k$ and $5^k$, so the last $k$ digits decide divisibility by $2^k$ and $5^k$ alone.

Digit problems are counting problems about strings of digits. Write the number as $d_1 d_2 \cdots d_k$, translate each condition into a statement about neighbouring digits, and count with the multiplication principle. A condition such as “the digits are strictly increasing” is really a choice of a set: a strictly increasing string is determined by the set of digits it uses, so $k$-digit strings from $\{0, \ldots, 9\}$ with this property correspond to $\binom{10}{k}$ subsets. Leading zeros must be handled separately, since a string starting with $0$ is not a $k$-digit number.

• $b \mid a$ means $a = bk$ for some integer $k$; if $d \mid a$ and $d \mid b$ then $d \mid (a \pm b)$
• $N \equiv (\text{digit sum of } N) \pmod 9$, so $9 \mid N$ exactly when $9$ divides the digit sum
• $N \equiv (\text{alternating digit sum of } N) \pmod{11}$
• Divisibility by $2^k$ or $5^k$ depends only on the last $k$ digits

• Treating the digit sum as the remainder itself; it is only congruent to $N$ modulo $9$, and can be much larger than $9$
• Checking only the last digit for divisibility by $4$ or $8$, which needs the last two or three digits
• Counting a digit string with a leading zero as if it were a number with that many digits

2.Primes and factorisation

A prime is an integer greater than $1$ whose only positive divisors are $1$ and itself. The first primes are $2, 3, 5, 7, 11, 13, \ldots$. The number $1$ is neither prime nor composite. The Fundamental Theorem of Arithmetic says every integer $n > 1$ can be written as a product of primes, $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$, and this representation is unique apart from the order of the factors. The exponents form a fingerprint for $n$: they determine every divisor, every square factor and every gcd.

Why does the representation exist? If $n > 1$ is not prime, it has a divisor $d$ with $1 < d < n$, and we can split $n = d \cdot (n/d)$ and repeat with both pieces. Since each step makes the pieces smaller, the process stops, and it stops only at primes. Uniqueness is slightly harder, but it follows from Euclid's lemma: if a prime $p$ divides $ab$, then $p \mid a$ or $p \mid b$.

To factor a number by hand, divide by $2$ as often as possible, then by $3$, $5$, $7$ and so on. You can stop once the square of the current prime exceeds what remains, because a composite number always has a prime factor no larger than its square root; the leftover is then prime or $1$. For example $360 = 2 \cdot 180 = 2^2 \cdot 90 = 2^3 \cdot 45 = 2^3 \cdot 3^2 \cdot 5$.

Primes are also the building blocks of divisibility questions. A number $m$ divides $n$ exactly when every prime in $m$ appears in $n$ with at least the same exponent. Problems that ask “how many divisors”, “what is the largest square dividing $N$” or “what is the least common multiple” are all answered by reading exponents off the factorisation.

A useful habit is to factor large expressions such as $3^8 - 1$ using difference-of-squares and sum-of-powers identities. For instance $3^8 - 1 = (3^4 - 1)(3^4 + 1)$, and each factor splits again, which exposes the prime divisors without a calculator.

• Fundamental Theorem: $n = p_1^{a_1}\cdots p_k^{a_k}$ is unique up to the order of the factors
• $1$ is neither prime nor composite
• A composite $n$ always has a prime factor $p \le \sqrt{n}$
• $a^2 - b^2 = (a-b)(a+b)$ and $a^n - 1$ factors through $a^d - 1$ for each divisor $d$ of $n$

• Stopping trial division at the number itself rather than at its square root
• Forgetting that $1$ is not prime, which changes sums of primes and counts of prime divisors
• Assuming a number is prime because it has no small prime factor up to $\sqrt[3]{n}$ rather than $\sqrt{n}$

3.GCD, LCM and the Euclidean algorithm

The greatest common divisor $\gcd(a,b)$ is the largest integer dividing both $a$ and $b$. The least common multiple $\operatorname{lcm}(a,b)$ is the smallest positive integer that both $a$ and $b$ divide. With prime factorisations both are read off prime by prime: the gcd takes the smaller exponent and the lcm takes the larger. For $12 = 2^2 \cdot 3$ and $18 = 2 \cdot 3^2$ we get $\gcd = 2 \cdot 3 = 6$ and $\operatorname{lcm} = 2^2 \cdot 3^2 = 36$.

Factoring large numbers is slow, but the Euclidean algorithm finds the gcd quickly, and it rests on one lemma: $\gcd(a,b) = \gcd(b, a \bmod b)$. To see why, write $a = qb + r$ with $r = a \bmod b$. Any common divisor of $a$ and $b$ divides $r = a - qb$, and any common divisor of $b$ and $r$ divides $a = qb + r$. So the two pairs $(a,b)$ and $(b,r)$ have exactly the same common divisors, and therefore the same greatest one.

Iterating the lemma gives the algorithm: replace $(a,b)$ by $(b, a \bmod b)$ until the remainder is $0$; the last nonzero number is the gcd. For $252$ and $105$: $252 = 2 \cdot 105 + 42$, $105 = 2 \cdot 42 + 21$, $42 = 2 \cdot 21$, so $\gcd(252,105) = 21$. The same chain of equations can be run backwards to write the gcd as an integer combination $21 = 105 - 2 \cdot 42 = \ldots$, which is the extended Euclidean algorithm and is the source of modular inverses.

The two functions are linked by $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab$. For each prime, the smaller and the larger exponent add up to the sum of the two original exponents, so the identity holds prime by prime.

On the contest, gcd and lcm arise whenever two things repeat with different periods, when a rectangle is tiled by the largest possible squares, or when a condition holds for two different reasons at once. In each case, reduce the problem to a gcd or lcm and then compute it by factoring or by Euclid.

• $\gcd(a,b) \cdot \operatorname{lcm}(a,b) = ab$ for positive integers $a$ and $b$
• $\gcd(a,b) = \gcd(b, a \bmod b)$, and $\gcd(a,0) = a$
• If $\gcd(a,b) = 1$ then $a$ and $b$ are relatively prime and $\gcd(a, bc) = \gcd(a,c)$ for every $c$
• Two repeating cycles of lengths $a$ and $b$ coincide again after $\operatorname{lcm}(a,b)$ steps

• Taking the gcd of the numbers' sum or difference instead of the numbers themselves
• Multiplying the lcm of three numbers pairwise without checking that the common factors are not double-counted
• Confusing $\gcd(a,b)=1$ with $a$ and $b$ being prime

4.Divisor counting and divisor sums

Suppose $n = p_1^{a_1} p_2^{a_2} \cdots p_k^{a_k}$. Every divisor of $n$ has the form $p_1^{e_1} \cdots p_k^{e_k}$ with $0 \le e_i \le a_i$, and distinct exponent tuples give distinct divisors because the factorisation is unique. For each prime there are $a_i + 1$ choices, and the choices for different primes are independent, so the number of divisors is $$d(n) = (a_1+1)(a_2+1)\cdots(a_k+1).$$ For example $360 = 2^3 \cdot 3^2 \cdot 5$ has $4 \cdot 3 \cdot 2 = 24$ divisors.

The sum of divisors works the same way, with the choices weighted by their values. For a single prime power, $1 + p + \cdots + p^a = \frac{p^{a+1}-1}{p-1}$. Because the choices for different primes multiply, the divisor sum factors too: $$\sigma(n) = \prod_{i=1}^{k} \left(1 + p_i + p_i^2 + \cdots + p_i^{a_i}\right).$$ So $\sigma(360) = (1+2+4+8)(1+3+9)(1+5) = 15 \cdot 13 \cdot 6 = 1170$. The reason multiplication works is that the map $(e_1,\ldots,e_k) \mapsto p_1^{e_1}\cdots p_k^{e_k}$ is a bijection between tuples and divisors, and the weight of a product is the product of the weights.

Restricted counts follow the same pattern. A divisor is a perfect square exactly when every exponent is even, so you count even choices for each prime. The sum of odd divisors of $360$ uses only the odd part $45 = 3^2 \cdot 5$, giving $\sigma(45) = 13 \cdot 6 = 78$. A number has an odd number of divisors exactly when it is a perfect square, because the divisors pair off as $d$ and $n/d$ unless $d = n/d$.

Counting divisors of a factorial uses the exponent formula of Legendre. The exponent of $p$ in $m!$ is $\lfloor m/p \rfloor + \lfloor m/p^2 \rfloor + \cdots$, since each multiple of $p^j$ contributes one more factor of $p$. Once these exponents are known, the divisor count of $m!$ is a product as above.

• $d(n) = (a_1+1)\cdots(a_k+1)$ when $n = p_1^{a_1}\cdots p_k^{a_k}$
• $\sigma(n) = \prod_i (1 + p_i + \cdots + p_i^{a_i})$, a product over the prime powers
• $n$ has an odd number of divisors exactly when $n$ is a perfect square
• The exponent of $p$ in $m!$ is $\sum_{j \ge 1} \lfloor m/p^j \rfloor$

• Adding exponents instead of adding $1$ to each exponent before multiplying
• Counting pairs $(d, n/d)$ and forgetting that a square root of $n$ is counted once
• Using $\sigma(n)$ for a sum over prime divisors only, which ignores the higher powers

5.Modular arithmetic and inverses

We write $a \equiv b \pmod m$ when $m \mid (a - b)$, equivalently when $a$ and $b$ leave the same remainder on division by $m$. For example $29 \equiv 5 \pmod{12}$ because $29 - 5 = 24$. Congruence is an equivalence relation, and it respects arithmetic: if $a \equiv b$ and $c \equiv d \pmod m$, then $a + c \equiv b + d$, $a - c \equiv b - d$ and $ac \equiv bd \pmod m$. The proof is one line: $(a+c) - (b+d) = (a-b) + (c-d)$ is a sum of multiples of $m$.

This means you may replace any number in a computation by its remainder at any step. To compute $7^4 \bmod 10$, note $7^2 = 49 \equiv 9$, so $7^4 \equiv 9^2 = 81 \equiv 1 \pmod{10}$. Reducing early keeps the numbers small and is the main technique behind almost every modular problem.

Division is different. Cancelling a common factor is allowed only when that factor is coprime to the modulus: if $ac \equiv bc \pmod m$ and $\gcd(c,m) = 1$, then $a \equiv b \pmod m$. The reason is that $m \mid c(a-b)$ and $\gcd(c,m) = 1$ force $m \mid (a-b)$.

An inverse of $a$ modulo $m$ is a number $x$ with $ax \equiv 1 \pmod m$. It exists exactly when $\gcd(a,m) = 1$. The Euclidean algorithm produces it: running the algorithm on $a$ and $m$ gives $1 = ax + my$ for integers $x, y$, and reducing mod $m$ shows $x$ is the inverse. For example $3 \cdot 5 = 15 \equiv 1 \pmod 7$, so $3^{-1} \equiv 5 \pmod 7$. Inverses let you solve linear congruences $ax \equiv b \pmod m$ by multiplying both sides by $a^{-1}$.

Beware of the nonexistent: $2x \equiv 4 \pmod 6$ has solutions $x \equiv 2 \pmod 3$ rather than a single residue, because $\gcd(2,6) = 2$ does not divide into the modulus. Always check the gcd before cancelling.

• $a \equiv b \pmod m$ means $m \mid (a-b)$, and congruences can be added and multiplied
• $ac \equiv bc \pmod m$ with $\gcd(c,m)=1$ implies $a \equiv b \pmod m$
• $a$ has an inverse modulo $m$ exactly when $\gcd(a,m) = 1$
• $ax \equiv b \pmod m$ has $\gcd(a,m)$ solutions modulo $m$ when $\gcd(a,m)$ divides $b$

• Cancelling a common factor $c$ from $ac \equiv bc$ when $\gcd(c,m) \ne 1$
• Reducing a subtraction to a negative remainder and forgetting to add the modulus back
• Assuming a linear congruence has a unique solution when the gcd of the coefficient and the modulus is larger than $1$

6.Fermat, Euler and multiplicative orders

Fermat's Little Theorem says that if $p$ is prime and $p \nmid a$, then $a^{p-1} \equiv 1 \pmod p$. A short proof: the numbers $a, 2a, \ldots, (p-1)a$ are all nonzero mod $p$ and pairwise distinct, because $ia \equiv ja$ would force $i \equiv j$ after cancelling $a$. So they are a rearrangement of $1, 2, \ldots, p-1$. Multiplying both sets together gives $(p-1)! \cdot a^{p-1} \equiv (p-1)!$, and cancelling $(p-1)!$ (which is coprime to $p$) yields the theorem.

Euler's theorem generalises this. Let $\varphi(m)$ count the integers in $\{1, \ldots, m\}$ that are coprime to $m$. If $\gcd(a,m) = 1$ then $a^{\varphi(m)} \equiv 1 \pmod m$. The same permutation argument works, since multiplication by $a$ permutes the reduced residues. For $m = p^k$ we have $\varphi(m) = p^{k-1}(p-1)$, and for $m = p_1^{a_1}\cdots p_r^{a_r}$ the function is multiplicative: $\varphi(m) = \prod p_i^{a_i - 1}(p_i - 1)$.

The practical use is exponent reduction. If $\gcd(a,m)=1$, then $a^N \bmod m$ depends only on $N \bmod \varphi(m)$. For example $3^{100} \bmod 11$: since $\varphi(11) = 10$ and $100 \equiv 0 \pmod{10}$, we get $3^{100} \equiv 1$. Fermat is the case $m = p$.

The multiplicative order of $a$ modulo $m$ is the least $t > 0$ with $a^t \equiv 1 \pmod m$. The order always divides $\varphi(m)$, and $a^N \equiv 1$ holds exactly when the order divides $N$. Finding the order by testing divisors of $\varphi(m)$ is often faster than running through all powers.

Be careful with composite moduli: the relevant exponent is $\varphi(m)$, not $m-1$, and Fermat's theorem does not apply unless the modulus is prime. A common trap is using $p-1$ for $p^2$ instead of $p(p-1)$.

• Fermat: $a^{p-1} \equiv 1 \pmod p$ when $p$ is prime and $p \nmid a$
• Euler: $a^{\varphi(m)} \equiv 1 \pmod m$ when $\gcd(a,m) = 1$
• $\varphi(p^k) = p^{k-1}(p-1)$, and $\varphi$ is multiplicative
• The multiplicative order of $a$ modulo $m$ divides $\varphi(m)$

• Applying Fermat's theorem to a composite modulus, where the exponent should be $\varphi(m)$
• Reducing the exponent modulo $p$ rather than modulo $p-1$
• Forgetting the hypothesis $\gcd(a,m) = 1$, which fails when $a$ shares a factor with $m$

7.The Chinese Remainder Theorem

Suppose $m$ and $k$ are coprime and we want an integer $n$ with $n \equiv a \pmod m$ and $n \equiv b \pmod k$. The Chinese Remainder Theorem says such an $n$ exists, and is unique modulo $mk$. The existence proof is a clean counting argument. Consider the $mk$ integers $0, 1, \ldots, mk - 1$. If two of them, $x$ and $y$, had the same residues modulo $m$ and modulo $k$, then $m \mid (x - y)$ and $k \mid (x - y)$. Since $\gcd(m,k) = 1$, this forces $mk \mid (x - y)$, which is impossible for distinct numbers in the range. So the pairs of residues are all attained, and each pair occurs exactly once.

To solve a specific system, write $n = a + m t$ and substitute into the second congruence: $a + mt \equiv b \pmod k$, which is a linear congruence in $t$. Because $\gcd(m,k) = 1$, $m$ has an inverse mod $k$, and $t$ is found by multiplying by $m^{-1}$. This is the practical method and is fast for small moduli.

As an example, solve $n \equiv 1 \pmod 4$ and $n \equiv 2 \pmod 5$. Write $n = 1 + 4t$. Then $1 + 4t \equiv 2 \pmod 5$, so $4t \equiv 1$. Since $4 \cdot 4 = 16 \equiv 1 \pmod 5$, the inverse of $4$ is $4$, giving $t \equiv 4$ and $n = 17$. The solutions are $n \equiv 17 \pmod{20}$.

The theorem extends to any number of pairwise coprime moduli, and it is the reason modular problems with a composite modulus can be split into prime-power pieces. For example $n \equiv 2^{100} \pmod{45}$ can be handled by finding the value mod $9$ and mod $5$ separately and combining. The same trick handles moduli like $1000 = 8 \cdot 125$.

Watch the coprimality hypothesis: $n \equiv 1 \pmod 4$ and $n \equiv 2 \pmod 6$ are incompatible, because the two conditions disagree mod $2$, so the theorem's conclusion is not automatic when the moduli share a factor.

• If $\gcd(m,k) = 1$, the system $n \equiv a \pmod m$, $n \equiv b \pmod k$ has a unique solution mod $mk$
• The solution is found by writing $n = a + mt$ and solving $mt \equiv b - a \pmod k$
• CRT splits a modulus into prime powers, which are then handled one at a time

• Applying the method to moduli that share a factor, where the system can have no solution
• Solving one congruence and forgetting to check the others
• Quoting the solution as one residue when it is only unique modulo the product of the moduli

8.Last digits and cycles

The last digit of $N$ is $N \bmod 10$, and the last two digits are $N \bmod 100$. Both are modular questions, and the strategy is to reduce every factor and every exponent as you go. Since $10 = 2 \cdot 5$, the last digit is determined by the residues mod $2$ and mod $5$, and the last two digits by the residues mod $4$ and mod $25$, which is the Chinese Remainder Theorem in action.

Powers of a fixed base repeat. Take $a = 3$ mod $10$: the powers $3, 9, 7, 1$ repeat with period $4$, so the last digit of $3^N$ depends only on $N \bmod 4$. This period is the multiplicative order of $3$ modulo $10$. The same reasoning gives the period of $a^N$ modulo $m$ as the order of $a$ modulo $m$, and the order divides $\varphi(m)$ whenever $\gcd(a,m) = 1$.

For huge exponents, the procedure is always the same. Find the modulus $m$, compute the order $t$ of the base (or any multiple of it, such as $\varphi(m)$), reduce the exponent mod $t$, and evaluate. For example, the last two digits of $3^{2025}$: the order of $3$ mod $100$ divides $20$, and $2025 \equiv 5 \pmod{20}$. So $3^{2025} \equiv 3^5 = 243 \equiv 43 \pmod{100}$.

Sums of powers can be handled term by term, and cancellation in the cycle does a lot of work. If all terms beyond a certain index are divisible by the modulus, they vanish. For instance $1! + 2! + \cdots + 100!$ is congruent mod $10$ to $1 + 2 + 6 + 24 = 33$, since every factorial from $5!$ on is divisible by $10$. So the last digit is $3$.

A nested exponent such as $7^{7^7}$ needs the top exponent first. Compute the order of $7$ mod $100$, which is $4$, then reduce $7^7$ modulo $4$. Since $7 \equiv -1 \pmod 4$, we have $7^7 \equiv -1 \equiv 3 \pmod 4$, so $7^{7^7} \equiv 7^3 = 343 \equiv 43 \pmod{100}$.

• The last $k$ digits of $N$ are $N \bmod 10^k$
• The powers $a^N \bmod m$ are periodic in $N$, with period dividing $\varphi(m)$ when $\gcd(a,m)=1$
• $n! \equiv 0 \pmod{10}$ for every $n \ge 5$

• Reducing the base mod $10$ but reducing the exponent mod $10$ instead of the cycle length
• Stopping at the cycle of the last digit, when the question asks for the last two digits and the cycle is longer
• Forgetting that a factor divisible by the modulus kills all later terms of a sum

9.Number bases

In base $b$, a numeral $d_k d_{k-1} \cdots d_1 d_0$ with $0 \le d_i \le b-1$ stands for $\sum_{i} d_i b^i$. Each place is worth $b$ times the place to its right because a base-$b$ numeral groups items into bundles of $b$, bundles of bundles, and so on. The subscript tells you the base: $(1101)_2 = 8 + 4 + 0 + 1 = 13$, while the decimal numeral $1101$ is a different number entirely.

The conversion from decimal to base $b$ is an algorithm built on the division algorithm. Divide $N$ by $b$ to get a quotient $q$ and remainder $r_0$, so $N = bq + r_0$ with $0 \le r_0 \le b-1$. Then $r_0$ is the last digit, and the other digits are the base-$b$ expansion of $q$. Repeating and reading the remainders from the last to the first gives the answer. For $13$ in base $2$: $13 = 2 \cdot 6 + 1$, $6 = 2 \cdot 3 + 0$, $3 = 2 \cdot 1 + 1$, $1 = 2 \cdot 0 + 1$, so $13 = (1101)_2$.

The last digit of $N$ in base $b$ is $N \bmod b$, so base questions are modular arithmetic in disguise. A numeral with $n$ digits in base $b$ satisfies $b^{n-1} \le N \le b^n - 1$, which is the fastest way to estimate how many digits a number has.

Digit counts and digit sums also change with base. Each digit of $N$ in base $b$ is found by repeated division, so the sum of the digits of $N$ in base $b$ is congruent to $N$ modulo $b - 1$, exactly as the decimal digit sum is congruent mod $9$. This gives a quick divisibility test in any base.

Problems often ask how a numeral looks in several bases at once, or when a numeral in one base is a number in another. Translate both sides into polynomials in the bases and compare. For example, $(\overline{ab})_{7}$ and $(\overline{ba})_{9}$ are equal when $7a + b = 9b + a$, which simplifies to $6a = 8b$, a linear equation with only a few solutions.

• $(d_k \cdots d_1 d_0)_b = \sum_i d_i b^i$ with $0 \le d_i \le b-1$
• The last digit of $N$ in base $b$ is $N \bmod b$
• A numeral with $n$ digits in base $b$ lies between $b^{n-1}$ and $b^n - 1$
• The digit sum of $N$ in base $b$ is congruent to $N$ modulo $b-1$

• Reading a numeral in base $b$ with the decimal place values
• Using a digit equal to the base, which is never allowed in base $b$
• Forgetting that the subscript base itself must be larger than every digit that appears

10.Diophantine equations

A Diophantine equation asks for integer or positive-integer solutions. On the AMC these are almost always polynomial equations that factor after a small rearrangement, and the solution is a finite list that you count. The first move is to look for a factorisation. Expressions such as $xy - 3x - 3y$ become $(x-3)(y-3) - 9$ after adding $9$ to both sides, and $x^2 - y^2 = (x-y)(x+y)$ is a product that can be enumerated.

The method known as Simon's Favourite Factoring Trick applies to any equation of the form $xy + ax + by = c$. Add $ab$ to both sides to get $(x+b)(y+a) = c + ab$. Then the integer solutions correspond to factor pairs of $c + ab$, and you check each pair for the sign and size constraints. The same idea works for the reciprocal equation $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$, which becomes $(x-n)(y-n) = n^2$ after clearing denominators.

Sign and size constraints matter. If $x, y$ are positive, then $x - n$ and $y - n$ can both be negative only when $x$ and $y$ are both less than $n$, and this is often impossible because the product of two integers in a short range is too small. So you usually only need the positive factor pairs, and you count those.

A difference of squares forces parity. The equation $x^2 - y^2 = N$ requires $x - y$ and $x + y$ to have the same parity, so $N$ must be odd or a multiple of $4$. Once the parity works, each factor pair $(d,e)$ with $de = N$ and $d < e$ gives exactly one positive solution, since $x = (d+e)/2$ and $y = (e-d)/2$.

Modular arguments can rule out whole families. A sum of two squares is never congruent to $3 \pmod 4$, and in general one checks the equation modulo a small number to reduce the search. Combine this with the factorisation and bounding steps, and the solution count follows.

• $x^2 - y^2 = (x-y)(x+y)$, and the two factors must have the same parity
• $xy + ax + by = c$ becomes $(x+b)(y+a) = c + ab$ after adding $ab$ to both sides
• $\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$ becomes $(x-n)(y-n) = n^2$
• A sum of two squares is never congruent to $3 \pmod 4$

• Forgetting that a factor pair with both factors negative can give solutions with negative variables, which the problem may exclude
• Counting ordered pairs when the problem asks for unordered ones, or the reverse
• Missing the case where a factor pair has $d = e$, which gives a single solution rather than two

Example 1: Neither two nor five

How many of the integers $1, 2, \ldots, 100$ are divisible by neither $2$ nor $5$?

Example 2: Squares plus one

For how many integers $n$ with $1 \le n \le 100$ is $n^2 + 1$ divisible by $5$?

Example 3: Cubes among divisors

How many positive divisors of $6^6$ are perfect cubes?

Example 4: Thousand-fold remainder

What is the remainder when $2^{1000}$ is divided by $1000$?

Example 5: Difference of squares

How many ordered pairs of positive integers $(a, b)$ satisfy $a^2 - b^2 = 2025$?

Example 6: Divisor sum summed

Find $\displaystyle\sum_{k=1}^{100} \left\lfloor \frac{100}{k} \right\rfloor$.