Number theory problems that look like algebra, and how to tell

Most students can tell a geometry problem from a combinatorics problem at a glance. The confusion is between algebra and number theory, because the number theory problems that cause the most trouble look like algebra. There is an equation, or a fraction, or a polynomial, and the instinct is to rearrange, substitute and solve. Then the rearranging goes nowhere, because the problem was never asking you to solve anything.

The difference is one word. When the unknowns are integers, an equation stops being something you solve and becomes a constraint you squeeze. Algebra asks what is x. Number theory asks which whole numbers survive, and the tools for that are different: factoring into a product, dividing out a remainder, and reducing modulo something small.

So this is a recognition drill: how to see, in the first minute, that an algebra-looking problem is really a number theory problem.

Five signals

• "Integer" sitting next to an equation with more unknowns than equations. Algebra says $xy = 2x + 3y$ has infinitely many solutions. Integers say it has four positive ones. Too many unknowns plus the word integer means the answer is a finite list, and you will find it by factoring, not by solving.
• A fraction that has to be a whole number. "Find all $n$ such that $n+1$ divides $n^2+1$" is a fraction problem in disguise, and the method is to divide the polynomial out until the remainder stops depending on $n$.
• "Prime" or "composite" applied to a polynomial. The question looks like it is about primes. It is usually about an algebraic factorisation that someone hid.
• Digits. Any problem that moves, reverses or sums the digits of a number becomes an equation the moment you write the number in place value. After that it is a divisibility problem.
• A divisibility condition on two variables that are tangled together. A quotient like $\frac{a^2+b^2}{ab+1}$ is a quadratic in disguise, and a quadratic with integer roots hands you a second root for free.

The three moves that follow

Once you have recognised it, there are three moves, and almost every problem of this kind uses one of them.

1. Factor into a product equal to a constant. Integers that multiply to 6 can only be a few things. Move everything to one side and add whatever constant makes it factor: $xy - 2x - 3y = 0$ becomes $(x-3)(y-2) = 6$. Now $x - 3$ is a divisor of 6, and the positive solutions are $(4,8), (5,5), (6,4), (9,3)$. Check the negative divisors too; here they all give a non-positive $x$ or $y$.
2. Divide out and look at the remainder. For $n+1$ dividing $n^2+1$, write $n^2 + 1 = (n+1)(n-1) + 2$. Whatever divides $n+1$ and $n^2+1$ must divide 2, so $n + 1 = 2$ and $n = 1$ is the only positive answer. That is modular thinking in its plainest form: modulo $n+1$, $n$ is $-1$.
3. Bound, then check a short list. Once the factor is fixed or the remainder is small, the size of the unknowns is capped, and a finite search finishes it. Bounding is what turns "find all" into "check these".

Watching it work

The hidden factorisation. Prove that $n^4 + 4$ is composite for every integer $n > 1$. It looks like a question about primes, so people start testing small cases and looking for a prime that always divides it. None does. The problem is algebra wearing number theory's clothes, the reverse of everything above: $n^4 + 4 = (n^2 - 2n + 2)(n^2 + 2n + 2)$. Both factors are at least 2 once $n > 1$, and you are done. The restriction $n > 1$ matters, since $n = 1$ gives 5, which is prime.

The digits problem. Find the smallest number ending in 6 that becomes four times larger when the 6 moves to the front (IMO 1962). Write $n = 10m + 6$ with $m$ having $k$ digits. Moving the 6 gives $6 \cdot 10^k + m$, and setting that equal to $4n$ gives $13m = 2(10^k - 4)$. Now it is pure number theory: you need $10^k \equiv 4 \pmod{13}$. The powers of 10 modulo 13 run $10, 9, 12, 3, 4, 1$, so $k = 5$ is the first that works, $m = 15384$, and $n = 153846$. Check: $4 \times 153846 = 615384$.

The same move cracks the three-digit multiples of 11 equal to eleven times their digit-square sum (IMO 1960): place value, then the divisibility rule for 11 splits it into two cases, and each case is a small equation with a short list of candidates. The answers are 550 and 803.

The tangled divisibility. If $ab + 1$ divides $a^2 + b^2$, the quotient is a perfect square (IMO 1988). Call the quotient $k$ and read $a^2 - kb \cdot a + (b^2 - k) = 0$ as a quadratic in $a$. The other root is $kb - a$, an integer, so a solution with $a \ge b$ produces a smaller one until that root reaches zero. Follow the chain for $k = 4$: $(112, 30)$ jumps to $(30, 8)$, then to $(8, 2)$, then to $(2, 0)$, where $k = b^2 = 4$. That descent to the bottom is the whole proof, and it is the reason the method is filed under infinite descent and Vieta jumping.

When it really is algebra

The signals cut both ways. If the problem says real numbers, or asks for an exact value, or the unknowns can be fractions, the integer moves are worthless and you should solve, substitute and simplify. The $n^4 + 4$ problem is the useful reminder that some problems need both: an algebraic identity to produce the factors, and a number theory question to make the factors matter.

The quickest practice is to take ten number theory problems from the problem archive and, before solving any, write one line for each: which signal fired and which of the three moves it calls for. Recognition is the skill you are short of, and it trains faster than solving does. The daily problem is a cheap way to keep it warm.