Maths Olympiad Prep

Library / /45 of 155

Number theory Difficulty 5.6 AIME, harder Prove it Saudi Arabia

Let uu and vv be positive rational numbers with uvu \neq v. Assume that there are infinitely many positive integers nn with the property that unvnu^{n}-v^{n} are integers. Prove that uu and vv are integers.

Solution

Let u=x/zu = x / z and v=y/zv = y / z with xx, yy, zz positive integers, and (x,y,z)=1(x, y, z) = 1. The statement is equivalent to saying that xnyn(modzn)x^{n} \equiv y^{n} \pmod{z^{n}}.

If z>1z > 1, assume that there is an odd prime divisor pzp \mid z. Let rr be the least positive integer such that xryr(modp)x^{r} \equiv y^{r} \pmod{p}, so rnn=rkr \mid n \Rightarrow n = r k. Let a=vp(n)a = v_{p}(n) and b=vp(xryr)b = v_{p}(x^{r} - y^{r}). By LTE, we have
vp(xnyn)=vp((xr)k(yr)k)=vp(xryr)+vp(k)b+vp(n)=a+b. v_{p}(x^{n} - y^{n}) = v_{p}((x^{r})^{k} - (y^{r})^{k}) = v_{p}(x^{r} - y^{r}) + v_{p}(k) \leq b + v_{p}(n) = a + b.
But vp(xnyn)vp(zn)nna+bpnpapb=npbv_{p}(x^{n} - y^{n}) \geq v_{p}(z^{n}) \leq n \Rightarrow n \leq a + b \Rightarrow p^{n} \leq p^{a} \cdots p^{b} = n p^{b}. This cannot be true for infinitely many positive integers nn.

If zz has no odd prime divisor, then zz is a power of 22. From this we have xx, yy are both odd.

If nn is odd then
2nxnyn=(xy)(xn1+xn2y++xyn2+yn1). 2^{n} \mid x^{n} - y^{n} = (x - y)(x^{n-1} + x^{n-2} y + \cdots + x y^{n-2} + y^{n-1}).
But the second factor is odd since nn is odd, we get 2nxy2^{n} \mid x - y for xyx \neq y. It is clear that there are only finitely many such nn.

If nn is even, let s=v2(x2y2)s = v_{2}(x^{2} - y^{2}) and c=v2(n)c = v_{2}(n). By LTE we have
v2(xnyn)=c+s1nc+s1nlog2n+s1. v_{2}(x^{n} - y^{n}) = c + s - 1 \Rightarrow n \leq c + s - 1 \Rightarrow n \leq \log_{2} n + s - 1.
Which does not hold for sufficiently large even values of nn.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.