Olympiad Number Theory

Divide $n$ by $d$: $n=qd+r$ with $0\le r<d$. Then $a^n=(a^d)^qa^r\equiv a^r$, so $a^n\equiv1$ forces $a^r\equiv1$, and the minimality of $d$ forces $r=0$. Fermat's little theorem gives $a^{p-1}\equiv1$, hence $d\mid p-1$. For the second item, $a^n\equiv-1$ gives $a^{2n}\equiv1$, so $d\mid2n$, while $a^n\equiv-1\not\equiv1$ (as $p$ is odd) gives $d\nmid n$. A divisor of $2n$ that does not divide $n$ must carry the full power of $2$ in $2n$. The third item is just $n=d\mid p-1$. Every problem in this section is these three lines applied to a well-chosen prime.

Step 1 — let $p\mid2^{32}+1$; then $p$ is odd and $2^{32}\equiv-1$, so $2^{64}\equiv1$. The order $d$ of $2$ divides $64$ but not $32$; the divisors of $64$ are powers of $2$, and the only one not dividing $32$ is $64$ itself. So $d=64$.

Step 2 — $d\mid p-1$ gives $p\equiv1\pmod{64}$.

Step 3 — search that one residue class: $64k+1$ for $k=1,\dots,10$ is $65,129,193,257,321,385,449,513,577,641$, and the primes among them are $193,257,449,577,641$. Trial division rejects the first four, and $2^{32}+1=641\cdot6700417$, where $6700417=64\cdot104694+1$ is prime — as Step 2 requires. This is how Euler refuted Fermat's guess that every $2^{2^k}+1$ is prime. (With quadratic residues one gets more: $p\equiv1\pmod8$ makes $2$ a square mod $p$, so $2^{(p-1)/2}\equiv1$, $64\mid\tfrac{p-1}2$ and $p\equiv1\pmod{128}$; indeed $641=5\cdot128+1$.)

How to find it. "Prime factors of $a^m+1$" is a question about the order of $a$. When $m$ is a power of $2$ the order is forced completely, turning a factoring problem into a short search along one residue class.

Step 1 — both factors are odd, so $p$ and $q$ are odd. By Fermat, $5^p-2^p\equiv5-2=3\pmod p$, so $p\mid5^p-2^p$ only when $p=3$.

Step 2 — suppose $p\ne3$. Then $p\mid5^q-2^q$; this rules out $p=5$ (it would divide $2^q$), so $2$ and $5$ are invertible mod $p$. Put $u\equiv5\cdot2^{-1}\pmod p$: then $u^q\equiv1$ and $u\not\equiv1$ (as $p\ne3$). The order of $u$ divides the prime $q$ and is not $1$, so it is $q$, and $q\mid p-1$; in particular $q<p$.

Step 3 — by symmetry, $q\ne3$ would give $p<q$. Both cannot hold, so $p=3$ or $q=3$; say $p=3$.

Step 4 — $5^3-2^3=117=3^2\cdot13$. If $q=3$, then $9\mid117^2$ and the pair works. If $q\ne3$, Step 1 says $q\nmid5^q-2^q$, so $q\mid117$ and $q=13$; and $39\mid117$, so $(3,13)$ works. The answer is $(3,3)$, $(3,13)$, $(13,3)$.

How to find it. The same prime in the exponent and in the modulus calls for Fermat; a prime modulus with a different prime exponent calls for the order. Two primes each dividing something indexed by the other give $q\mid p-1$ and $p\mid q-1$, which cannot both happen.

Step 1 — the left side is $\Phi(x)=x^6+x^5+\cdots+x+1$. It is positive for every integer $x\ne1$ ($x^7-1$ and $x-1$ have the same sign), so $y^5>1$, $y\ge2$, and both factors of $y^5-1=(y-1)(y^4+y^3+y^2+y+1)$ are positive divisors of $\Phi(x)$.

Step 2 — every prime $p\mid\Phi(x)$ is $7$ or $\equiv1\pmod7$. Indeed $p\mid x^7-1$, so $\operatorname{ord}_p(x)$ is $1$ or $7$. Order $7$ gives $7\mid p-1$. Order $1$ means $x\equiv1$, and then $\Phi(x)\equiv7\pmod p$, so $p=7$.

Step 3 — a positive divisor of $\Phi(x)$ is a product of such primes, hence $\equiv0$ or $1\pmod7$. Apply this to $y-1$: $y\equiv1$ or $2\pmod7$.

Step 4 — then $y^4+y^3+y^2+y+1\equiv5$ (for $y\equiv1$) or $\equiv31\equiv3$ (for $y\equiv2$) modulo $7$, which is neither $0$ nor $1$. Contradiction: there are no solutions.

How to find it. $\tfrac{x^7-1}{x-1}$ is a cyclotomic value, and the prime divisors of $\Phi_n(x)$ are pinned by orders: $n$'s own prime or $1\bmod n$. The right side factors, so both factors inherit the restriction — and the table shows that no residue of $y$ lets both factors have it.

The failing step is "the order is $n$": $p\mid a^n-1$ gives only $\operatorname{ord}_p(a)\mid n$. Here $\operatorname{ord}_3(2)=2$ and $\operatorname{ord}_7(2)=3$ — both primes already divide the smaller numbers $2^2-1$ and $2^3-1$. A prime of order exactly $n$ is primitive, and $63$ has none: this is the exceptional case $(2,6)$ of Zsigmondy's theorem. A correct argument names the order $d$, proves $d=n$ (or disposes of each smaller $d$), and only then concludes $p\equiv1\pmod n$.

The descent is well-ordering: a nonempty set of positive integers has a least element, so there is no infinite chain of solutions with $a+b$ strictly decreasing. Vieta's formulas make each jump free. From one root $a$ of $t^2-St+P$ the other root is $S-a$, visibly an integer, and also $P/a$, visibly small when $P$ is small compared with $a^2$. Two expressions for one number supply integrality and size at once, and the jump keeps the equation because it only swaps the two roots of the same quadratic. Geometrically the solutions are lattice points on a conic, and the jumps are horizontal and vertical chords between them, walking toward the axes.

Step 1 — fix such a $k$ and take a solution with $x+y$ minimal and $x\ge y$. If $x=y$, the equation reads $2x^2+1=kx^2$, so $x^2\mid1$: $x=y=1$ and $k=3$.

Step 2 — if $x>y$, fix $y$: $x$ is a root of $t^2-ky\,t+(y^2+1)=0$, whose other root is $x'=ky-x$ (an integer) and also $x'=\tfrac{y^2+1}{x}$ (positive).

Step 3 — size: since $x\ge y+1$, $x'=\tfrac{y^2+1}{x}\le\tfrac{y^2+1}{y+1}\le y<x$. So $(x',y)$ is a solution in positive integers with $x'+y<x+y$, contradicting minimality.

Step 4 — so the minimal solution is $(1,1)$ and $k=3$; conversely $k=3$ has the solution $(1,1)$. The only value is $k=3$.

How to find it. A symmetric equation, quadratic in each variable, with a free parameter $k$: jump from a minimal solution. The boundary case $x=y$ is where the parameter gets pinned.

Step 1 — let $k=\tfrac{a^2+b^2}{ab+1}$ and suppose $k$ is not a perfect square. Among all pairs of positive integers with $a^2+b^2=k(ab+1)$, take one with $a+b$ minimal and $a\ge b$.

Step 2 — as a quadratic in $a$ it reads $a^2-kb\,a+(b^2-k)=0$, so the other root is $a'=kb-a=\tfrac{b^2-k}{a}$, an integer by the first formula.

Step 3 — $a'\ne0$, since otherwise $k=b^2$ is a square.

Step 4 — $a'>0$: if $a'\le-1$, then $a'b+1\le1-b\le0$, yet $a'^2+b^2=k(a'b+1)$ has a positive left side.

Step 5 — $a'<a$: $a'=\tfrac{b^2-k}{a}<\tfrac{b^2}{a}\le b\le a$. So $(a',b)$ is a positive solution with a smaller sum, a contradiction; hence $k$ is a perfect square.

Step 6 — the same jumps describe all solutions: descent from any solution ends at a pair with a zero coordinate, and there $k=b^2$. For $k=4$ the chain $(30,8)\to(2,8)\to(2,0)$ is drawn on the curve $a^2+b^2=4(ab+1)$.

How to find it. "$ab+1$ divides $a^2+b^2$" is symmetric and quadratic in each variable, so jump. The descent can only stop at $a'=0$, and that exit is exactly the statement "$k=b^2$".

And there are solutions: $(a,b)=(8,2)$ gives $\tfrac{64+4}{17}=4$. The jump from $(8,2)$ is $a'=4\cdot2-8=0$, which is not positive, so it leaves the set of positive solutions and the descent stops there. The case $a'=0$ is exactly where the conclusion lives ($b^2=k$), and a proof must treat $a'<0$, $a'=0$ and $a'>0$ separately. A descent proof that never uses the negation of the conclusion is wrong somewhere.

The first is just the finiteness of the set of divisors. The second is unique factorization: each prime $p\mid C$ appears in $C^k$ with an exponent that is a multiple of $k$, and coprimality sends all of those copies of $p$ to the same factor, so every prime exponent of $A$ (and of $B$) is a multiple of $k$. Without coprimality this fails ($2\cdot8=4^2$), so compute the gcd first — it usually divides a small number, and each possible gcd is a separate case. Most "find all integer solutions" equations of olympiad size are driven into one of these two forms, often after a size argument has bounded one factor.

Step 1 — complete the product: $xy-3x+2y-6=(x+2)(y-3)$, so the equation is $(x+2)(y-3)=11$.

Step 2 — $11$ is prime, so $(x+2,\,y-3)$ is one of $(1,11)$, $(11,1)$, $(-1,-11)$, $(-11,-1)$.

Step 3 — the solutions are $(x,y)=(-1,14),(9,4),(-3,-8),(-13,2)$. Check one: $9\cdot4-27+8=17$.

How to find it. One $xy$ term plus linear terms is always Simon's trick; the constant to add is the product of the two shifts. Over the integers the negative divisor pairs are half of the answer, and forgetting them is the usual loss.

Step 1 — factor: $(x-y)(x^2+xy+y^2)=602=2\cdot7\cdot43$. Put $d=x-y$, a positive divisor of $602$.

Step 2 — size: $x^2+xy+y^2=d^2+3xy>d^2$, so $d^3<602$ and $d\le8$; the divisors of $602$ in that range are $1,2,7$.

Step 3 — in each case $3xy=\tfrac{602}{d}-d^2$. For $d=1$: $xy=200$ and $x=y+1$, so $y^2+y-200=0$, whose discriminant $801$ is not a square. For $d=2$: $xy=99$ and $x=y+2$, so $y^2+2y-99=0$, giving $y=9$, $x=11$. For $d=7$: $3xy=86-49=37$, not a multiple of $3$.

Step 4 — the only solution is $(11,9)$, and $1331-729=602$.

How to find it. A difference of cubes always factors, and the second factor dwarfs the first. That imbalance bounds the small factor and leaves a handful of divisors to test.

Step 1 — suppose there are solutions and take one with $z$ minimal. Then $\gcd(x,y)=1$: a common prime $p$ would give $p^4\mid z^2$, so $p^2\mid z$, and $\left(\tfrac xp,\tfrac yp,\tfrac z{p^2}\right)$ would be a smaller solution.

Step 2 — $(x^2)^2+(y^2)^2=z^2$ is a primitive Pythagorean triple, so (swapping $x$ and $y$ if necessary) $x$ is odd, $y$ is even, and there are coprime $m>n>0$ of opposite parity with $x^2=m^2-n^2$, $y^2=2mn$, $z=m^2+n^2$.

Step 3 — $x^2+n^2=m^2$ is again primitive with $x$ odd, so $n$ is even and $n=2rs$, $m=r^2+s^2$ with $\gcd(r,s)=1$.

Step 4 — coprime pieces: $\left(\tfrac y2\right)^2=\tfrac{mn}{2}=rs(r^2+s^2)$, and $r$, $s$, $r^2+s^2$ are pairwise coprime, so each is a square: $r=u^2$, $s=v^2$, $r^2+s^2=w^2$.

Step 5 — then $u^4+v^4=w^2$ is a positive solution with $w\le w^2=m\le m^2<m^2+n^2=z$, contradicting the minimality of $z$.

How to find it. A sum of two squares equal to a square is a Pythagorean triple; its parametrization produces a product equal to a square; coprime pieces make each piece a square; and the same equation reappears in smaller numbers — infinite descent. As a corollary $x^4+y^4=z^4$ has no solutions, the case $n=4$ of Fermat's Last Theorem.

This misses $x=3$: $3\cdot12=36$. The factors $3$ and $12$ are not squares because $\gcd(x,x+9)$ can be $3$ or $9$, and coprime pieces needs gcd $1$. Either split into cases by the gcd, or avoid it: $4x(x+9)=(2x+9)^2-81$, so $x(x+9)=y^2$ becomes $(2x+9-2y)(2x+9+2y)=81$. The divisor pairs $(1,81)$ and $(3,27)$ give exactly $x=16$ and $x=3$; the pair $(9,9)$ gives $y=0$.