Hard Number Theory

Study Sheet

Hard Number Theory

Contest-level problems that combine everything

Strategy

Concept
The toolkit in one place

Hard number theory problems combine a few moves: reduce mod a well-chosen modulus to rule out solutions; factor (SFFT, difference of squares, sums of cubes); bound a variable by size or by the growth of a power; use orders to control exponents; and apply Fermat, Euler, Wilson or CRT to compute residues. Look for the invariant a modulus exposes.

Choose the modulus by what the equation contains: squares suggest mod 44 or mod 88 (squares are 0,10, 1 mod 44; 0,1,40, 1, 4 mod 88); cubes suggest mod 77 or 99 (cubes are 0,±10, \pm1); powers of 22 suggest mod 33; fourth powers mod 1616. If a modulus leaves too many residues, try a product of small primes and reason with CRT. And know that some innocent equations resist every tool: whether n!+1=m2n! + 1 = m^2 has solutions beyond n=4,5,7n = 4, 5, 7 (Brocard's problem) is still open.

Example
Bounding with growth

Find all n≥2n \ge 2 with n!=n3−nn! = n^3 - n. Factor the right side: n3−n=(n−1)n(n+1)n^3 - n = (n - 1)n(n + 1), and n!=(n−2)! (n−1)nn! = (n - 2)!\,(n - 1)n, so the equation becomes (n−2)!=n+1(n - 2)! = n + 1. The factorial grows much faster than n+1n + 1: n=2,3,4n = 2, 3, 4 give 1,1,21, 1, 2 against 3,4,53, 4, 5; n=5n = 5 gives 3!=6=5+13! = 6 = 5 + 1; and from n=6n = 6 on, (n−2)!≥24>n+1(n - 2)! \ge 24 > n + 1 and the gap only widens. So n=5n = 5: 120=125−5120 = 125 - 5.

Example
Combining orders and Fermat

Show 2n+12^n + 1 is never divisible by 77. The order of 22 mod 77 is 33 (23=8≡12^3 = 8 \equiv 1), so 2n2^n cycles through 2,4,12, 4, 1 and 2n+12^n + 1 through 3,5,23, 5, 2 — never 00. Compare mod 55, where 22 has order 44 and 22≡−12^2 \equiv -1: there 5∣2n+15 \mid 2^n + 1 exactly when n≡2(mod4)n \equiv 2 \pmod 4.

Side note
Where it goes wrong

Trusting a modulus that says nothing. For x2+y2+z2=2023x^2 + y^2 + z^2 = 2023, reducing mod 33 (squares 0,10, 1) allows 2023≡12023 \equiv 1 as 1+0+01 + 0 + 0, and mod 44 allows 2023≡32023 \equiv 3 as 1+1+11 + 1 + 1. Silence is not evidence; move to mod 88, where the equation dies (next section).

Try it
Try it: a classic

Find all primes pp such that p2+2p^2 + 2 is also prime.

Show the answer

For p≠3p \ne 3, p2≡1(mod3)p^2 \equiv 1 \pmod 3, so 3∣p2+23 \mid p^2 + 2, and p2+2>3p^2 + 2 > 3 is composite. Only p=3p = \mathbf{3} remains, and 9+2=119 + 2 = 11 is prime.

Choosing a Modulus

Concept
Let the equation pick the modulus

A modulus is useful when the terms of the equation take few values in it. Match the modulus to the exponent: n2n^2 lives in {0,1,4}\{0, 1, 4\} mod 88; n3n^3 in {0,±1}\{0, \pm1\} mod 99 and mod 77; 2n2^n cycles with period 22 mod 33 and period 33 mod 77. Several moduli, used in turn, can pin down exponents and parities one fact at a time.

The reason these particular moduli work is orders: mod 88 every odd square is 11 because the group of units mod 88 has exponent 22; mod 99 every cube of a unit is ±1\pm1 because the units form a cycle of length 6=φ(9)6 = \varphi(9) and cubing collapses it to the two elements of order dividing 22. When one modulus yields a parity fact ("mm is even"), feed it back into the equation: an even exponent often means a difference of squares.

Example
Three squares, mod 88
0011223344556677nn²n² mod 8 lands only on 0, 1, 4
Every square is 0, 1 or 4 mod 8, and no three of these add to 7.

Show that x2+y2+z2=2023x^2 + y^2 + z^2 = 2023 has no integer solutions. Squares mod 88: 02=00^2 = 0, (±1)2=1(\pm1)^2 = 1, (±2)2=4(\pm2)^2 = 4, (±3)2=9≡1(\pm3)^2 = 9 \equiv 1, 42=16≡04^2 = 16 \equiv 0 — only 0,1,40, 1, 4. Sums of three of these: 0,1,2,3,4,5,60, 1, 2, 3, 4, 5, 6 are all reachable, but 77 is not. And 2023=8⋅252+72023 = 8\cdot252 + 7. Impossible.

Example
Powers of 33 and 22

Solve 3m=2n+13^m = 2^n + 1 in positive integers. If n=1n = 1: 3m=33^m = 3, so m=1m = 1. If n≥2n \ge 2: mod 44, 3m≡13^m \equiv 1, and since 3≡−13 \equiv -1 this forces mm even, m=2km = 2k. Now factor: 2n=32k−1=(3k−1)(3k+1)2^n = 3^{2k} - 1 = (3^k - 1)(3^k + 1), two powers of 22 that differ by 22, so they are 22 and 44: k=1k = 1, m=2m = 2, n=3n = 3. Solutions: (m,n)=(1,1),(2,3)(m, n) = (1, 1), (2, 3).

Example
A prime by elimination

Find all primes pp with 2p+p22^p + p^2 prime. p=2p = 2 gives 88, not prime; p=3p = 3 gives 8+9=178 + 9 = 17, prime. For a prime p>3p > 3: pp is odd, so 2p≡(−1)p=−1(mod3)2^p \equiv (-1)^p = -1 \pmod 3, and p2≡1(mod3)p^2 \equiv 1 \pmod 3. The sum is ≡0(mod3)\equiv 0 \pmod 3 and larger than 33: composite. Only p=3p = 3.

Side note
Where it goes wrong

Stopping at the first modulus that gives a partial answer. In 3m=2n+13^m = 2^n + 1, mod 44 alone only shows mm is even; it rules nothing out. The finish needed a second tool — factoring the difference of squares — which the parity fact made available.

Try it
Try it: two moduli

Find all n≥1n \ge 1 for which 2n+3n2^n + 3^n is a perfect square.

Show the answer

Mod 33: 2n+3n≡(−1)n2^n + 3^n \equiv (-1)^n, and squares are 0,1(mod3)0, 1 \pmod 3, so nn must be even, n=2kn = 2k. Mod 55: 22k+32k=4k+9k≡(−1)k+(−1)k=±22^{2k} + 3^{2k} = 4^k + 9^k \equiv (-1)^k + (-1)^k = \pm2, but squares mod 55 are 0,1,40, 1, 4 and ±2≡2,3\pm2 \equiv 2, 3. So no n≥1n \ge 1 works.

Floor Sums and Lattice Points

Concept
Count the dots two ways

A sum of floors counts lattice points: ⌊qk/p⌋\lfloor qk/p \rfloor is the number of points (k,j)(k, j) with 1≤j≤qk/p1 \le j \le qk/p, the points on or under the line y=qx/py = qx/p above x=kx = k. For coprime p,qp, q: ∑k=1p−1⌊qkp⌋=(p−1)(q−1)2\displaystyle\sum_{k=1}^{p-1}\left\lfloor \frac{qk}{p} \right\rfloor = \frac{(p - 1)(q - 1)}{2}. Similarly ∑k=1n⌊n/k⌋=∑k=1nτ(k)\sum_{k=1}^{n}\lfloor n/k \rfloor = \sum_{k=1}^{n}\tau(k): both count the points under the hyperbola xy=nxy = n.

The line from (0,0)(0, 0) to (p,q)(p, q) cuts the (p−1)×(q−1)(p - 1)\times(q - 1) box of interior lattice points into two halves. When gcd⁡(p,q)=1\gcd(p, q) = 1 no interior lattice point lies ON the line (that would need p∣qkp \mid qk with 0<k<p0 < k < p), and the half-turn symmetry about the centre of the box swaps the two halves, so each half holds exactly (p−1)(q−1)/2(p - 1)(q - 1)/2 points. For the hyperbola, counting column by column gives ⌊n/x⌋\lfloor n/x \rfloor points above xx, while counting the points with product exactly kk gives τ(k)\tau(k).

Example
∑k=16⌊5k/7⌋\sum_{k=1}^{6}\lfloor 5k/7 \rfloor
012234(7, 5)k:
Filled dots: under the line y = 5x/7, counted column by column 0, 1, 2, 2, 3, 4. Open dots: the other half.

Directly: ⌊5/7⌋,⌊10/7⌋,…,⌊30/7⌋=0,1,2,2,3,4\lfloor 5/7 \rfloor, \lfloor 10/7 \rfloor, \ldots, \lfloor 30/7 \rfloor = 0, 1, 2, 2, 3, 4, total 1212. As a count: these are the interior lattice points below the line from (0,0)(0, 0) to (7,5)(7, 5). The interior box has 6⋅4=246\cdot4 = 24 points, none on the line since gcd⁡(5,7)=1\gcd(5, 7) = 1, and symmetry splits them evenly: 24/2=1224/2 = 12.

Example
Points under a hyperbola
123456123456xy = 614 points
Lattice points with xy ≤ 6: columns give ⌊6/x⌋, curves xy = k give τ(k).

Evaluate ∑k=16⌊6/k⌋=6+3+2+1+1+1=14\sum_{k=1}^{6}\lfloor 6/k \rfloor = 6 + 3 + 2 + 1 + 1 + 1 = 14. The same points counted by their product xy=kxy = k: there are τ(k)\tau(k) points with product kk, so the total is τ(1)+⋯+τ(6)=1+2+2+3+2+4=14\tau(1) + \cdots + \tau(6) = 1 + 2 + 2 + 3 + 2 + 4 = 14. This is the start of the study of the average number of divisors, which grows like ln⁡n\ln n.

Side note
Where it goes wrong

Using the half-box formula when pp and qq share a factor. For ∑k=15⌊4k/6⌋=0+1+2+2+3=8\sum_{k=1}^{5}\lfloor 4k/6 \rfloor = 0 + 1 + 2 + 2 + 3 = 8, the "formula" gives 5⋅3/2=7.55\cdot3/2 = 7.5 — not even an integer. The line from (0,0)(0, 0) to (6,4)(6, 4) passes through the lattice point (3,2)(3, 2), which sits on the line and breaks the symmetric split.

Try it
Try it: a floor sum

Evaluate ∑k=110⌊3k11⌋\displaystyle\sum_{k=1}^{10}\left\lfloor \frac{3k}{11} \right\rfloor.

Show the answer

gcd⁡(3,11)=1\gcd(3, 11) = 1, so the sum is (11−1)(3−1)2=10\dfrac{(11 - 1)(3 - 1)}{2} = \mathbf{10}. Directly: k=1,2,3k = 1, 2, 3 give 00; k=4,…,7k = 4, \ldots, 7 give 11; k=8,9,10k = 8, 9, 10 give 22; total 4+6=104 + 6 = 10.

Why It Works

Pair kk with p−kp - k. For coprime p,qp, q and 0<k<p0 < k < p, qk/pqk/p is not an integer, so write qk/p=⌊qk/p⌋+fqk/p = \lfloor qk/p \rfloor + f with 0<f<10 < f < 1. Then q(p−k)/p=q−qk/p=(q−1−⌊qk/p⌋)+(1−f)q(p - k)/p = q - qk/p = (q - 1 - \lfloor qk/p \rfloor) + (1 - f), and 0<1−f<10 < 1 - f < 1, so ⌊q(p−k)/p⌋=q−1−⌊qk/p⌋\lfloor q(p - k)/p \rfloor = q - 1 - \lfloor qk/p \rfloor. Each pair of terms therefore sums to q−1q - 1. Adding all p−1p - 1 terms counts every pair twice: 2∑=(p−1)(q−1)2\sum = (p - 1)(q - 1). This identity is the engine of Eisenstein's proof of quadratic reciprocity.