Maths Olympiad Prep

Library / /42 of 155

Number theory Difficulty 5.5 AIME, harder Prove it Saudi Arabia

Solve the following equation in positive integers xx, yy:
x20171=(x1)(y20151). x^{2017}-1=(x-1)(y^{2015}-1).

Solution

It is clear that x=1x=1 is a solution of the problem (with yy any positive integer).

We now show that for x>1x>1, the given equation has no solution. In fact, suppose that there are x>1x>1 and yy are positive integers satisfying the equation. Then, one has y>1y>1 and
x2016+x2015++x+1=y20151=(y1)(y2014+y2013++y+1). x^{2016}+x^{2015}+\cdots+x+1 = y^{2015}-1 = (y-1)(y^{2014}+y^{2013}+\cdots+y+1).
Put p=2017p=2017, and note that pp is a prime. Let qq be a prime factor of xp1++x+1x^{p-1}+\cdots+x+1. Then (x,q)=1(x, q)=1 and by Fermat's little theorem we get qxq11q \mid x^{q-1}-1. But qxp1q \mid x^{p}-1, it follows that the order of xx modulo qq is a divisor of (p,q1)(p, q-1) which is either 11 or pp. This shows that qx1q \mid x-1 or pq1p \mid q-1.

If qx1q \mid x-1 then xp1++x+1p(modq)x^{p-1}+\cdots+x+1 \equiv p \pmod{q}, i.e. qpq \mid p, this gives p=qp=q. This means that any prime divisor of xp1++x+1x^{p-1}+\cdots+x+1 is congruent either to 00 or to 1(modp)1 \pmod{p}, hence any positive divisor of xp1++x+1x^{p-1}+\cdots+x+1 is too. In particular, y1y-1 and y2014+y2013++y+1y^{2014}+y^{2013}+\cdots+y+1 (which are positive divisors of xp1++x+1x^{p-1}+\cdots+x+1) are congruent either to 00 or to 1(modp)1 \pmod{p}.

But, if py1p \mid y-1 then
y2014+y2013++y+12015≢0,1(modp), y^{2014}+y^{2013}+\cdots+y+1 \equiv 2015 \not\equiv 0,1 \pmod{p},
we get a contradiction.

Hence, y11(modp)y-1 \equiv 1 \pmod{p}, i.e. y2(modp)y \equiv 2 \pmod{p}, then
y2014+y2013++y+122014+22013++2+1220151(modp). y^{2014}+y^{2013}+\cdots+y+1 \equiv 2^{2014}+2^{2013}+\cdots+2+1 \equiv 2^{2015}-1 \pmod{p}.
This shows that 2201510(modp)2^{2015}-1 \equiv 0 \pmod{p} or 2201511(modp)2^{2015}-1 \equiv 1 \pmod{p}. That is, either p220151p \mid 2^{2015}-1 or p220141p \mid 2^{2014}-1. On the other hand, by Fermat's little theorem again, p2p11=220161p \mid 2^{p-1}-1 = 2^{2016}-1. From this, we easily get p1p \mid 1 or p3p \mid 3 which is impossible. The problem is therefore solved.

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.