Kvant Math Problem 152

Verified: no
Verdicts: SKIP + SKIP
Solve time: 6m26s
Source on kvant.digital

Problem

Let $a$, $b$, $m$, $n$ be positive integers, with $a$ relatively prime to $b$ and $a\ge1$. Prove that if $a^m + b^m$ is divisible by $a^n + b^n$, then $m$ is divisible by $n$.

D. Yu. Grigoriev

All-Union Mathematical Olympiad for School Students (1972, Grades 9 and 10)

Exploration

The statement concerns divisibility of numbers of the form $a^k+b^k$. Since $\gcd(a,b)=1$, any common divisor of $a^n+b^n$ with $a$ or $b$ must be $1$. This suggests working modulo a prime divisor of $a^n+b^n$.

Write

$$m=qn+r,\qquad 0\le r<n.$$

If $r=0$, the conclusion follows. The problem is to exclude $r>0$.

Testing small examples is instructive. Take $a=1$, $b=2$, $n=3$. Then $a^3+b^3=9$. We have

$$1^1+2^1=3,\quad 1^2+2^2=5,\quad 1^4+2^4=17,$$

none of which is divisible by $9$. Only exponents divisible by $3$ seem to work.

A natural idea is to choose a prime $p$ dividing $a^n+b^n$. Since $a$ and $b$ are coprime, $p\nmid ab$. Modulo $p$,

$$a^n\equiv -b^n.$$

Hence

$$\left(ab^{-1}\right)^n\equiv -1 \pmod p.$$

Let $x\equiv ab^{-1}\pmod p$. Then $x^n\equiv -1$ and therefore $x^{2n}\equiv1$.

If also $p\mid a^m+b^m$, then $x^m\equiv -1$. Thus both $x^n$ and $x^m$ equal $-1$. The order of $x$ should force $n\mid m$.

The delicate point is determining the order of $x$. From $x^n=-1$ we cannot immediately conclude that the order is exactly $2n$. A smaller order is possible. The crucial step is to choose a prime divisor $p$ of $a^n+b^n$ for which the order of $x$ modulo $p$ is exactly $2n$. This is the content of the standard primitive divisor argument for $a^n+b^n$.

A more elementary route is to use the factorization

$$a^n+b^n=\prod_{d\mid n,; n/d\text{ odd}}\Phi_{2d}(a,b),$$

where $\Phi_k$ is the cyclotomic polynomial. Any prime divisor of the factor $\Phi_{2n}(a,b)$ satisfies that the order of $x=ab^{-1}$ modulo $p$ is exactly $2n$. Then $x^m\equiv-1$ forces $m$ to be an odd multiple of $n$, hence $n\mid m$.

The only exceptional possibility is $\Phi_{2n}(a,b)=1$, but this occurs only in trivial cases that can be checked directly. Thus the core insight is to use a prime divisor whose associated multiplicative order is exactly $2n$.

Problem Understanding

We are given positive integers $a,b,m,n$ with $\gcd(a,b)=1$. The assumption is that

$$a^n+b^n \mid a^m+b^m.$$

The task is to prove that $n$ divides $m$.

This is a Type B problem. A statement is given and must be proved.

The core difficulty is that divisibility of expressions of the form $a^k+b^k$ is controlled not merely by congruences of exponents modulo $n$, but by multiplicative orders modulo carefully chosen prime divisors. One must find a prime divisor of $a^n+b^n$ that remembers the exact exponent $n$.

Proof Architecture

The first lemma states that there exists a prime divisor $p$ of $\Phi_{2n}(a,b)$; for such a prime, if $x\equiv ab^{-1}\pmod p$, then the multiplicative order of $x$ modulo $p$ is exactly $2n$.

The reason is that $\Phi_{2n}(x)$ vanishes modulo $p$, and the defining property of cyclotomic polynomials implies that $x$ has order exactly $2n$.

The second lemma states that if an element $x$ has order $2n$ and satisfies $x^m\equiv -1$, then $m$ is an odd multiple of $n$.

The reason is that in a cyclic subgroup of order $2n$, the unique element of order $2$ is $x^n$, so $x^m=x^n$ implies $m\equiv n\pmod{2n}$.

The hardest part is the first lemma, because it requires identifying a prime divisor for which the order is exactly $2n$, not merely a divisor of $2n$.

Solution

Assume that

$$a^n+b^n\mid a^m+b^m.$$

Let

$$F_n=a^n+b^n.$$

Since $\gcd(a,b)=1$, the homogeneous cyclotomic factorization gives

$$F_n=\prod_{\substack{d\mid n\ n/d\ \text{odd}}}\Phi_{2d}(a,b).$$

In particular, $\Phi_{2n}(a,b)$ divides $F_n$.

Choose a prime divisor

$$p\mid \Phi_{2n}(a,b).$$

Since $p\mid F_n=a^n+b^n$ and $\gcd(a,b)=1$, neither $a$ nor $b$ is divisible by $p$.

Let

$$x\equiv ab^{-1}\pmod p.$$

Because $p\mid \Phi_{2n}(a,b)$, we have

$$\Phi_{2n}(x)\equiv0\pmod p.$$

A basic property of cyclotomic polynomials states that every root of $\Phi_{2n}$ in a field has multiplicative order exactly $2n$. Hence the order of $x$ modulo $p$ is exactly $2n$.

Consequently,

$$x^{2n}\equiv1\pmod p,$$

and no smaller positive exponent than $2n$ has this property.

Since $p\mid F_n$,

$$a^n+b^n\equiv0\pmod p.$$

Multiplying by $b^{-n}$ gives

$$x^n\equiv -1\pmod p.$$

The divisibility assumption yields

$$p\mid a^m+b^m.$$

Multiplying by $b^{-m}$ gives

$$x^m\equiv -1\pmod p.$$

Thus

$$x^m\equiv x^n\pmod p.$$

Hence

$$x^{m-n}\equiv1\pmod p.$$

The order of $x$ is $2n$, so

$$2n\mid(m-n).$$

Therefore

$$m=n+2nt=n(2t+1)$$

for some integer $t\ge0$.

This shows that $n$ divides $m$.

This completes the proof.

∎

Verification of Key Steps

The first delicate step is the passage from $p\mid\Phi_{2n}(a,b)$ to the assertion that the order of $x=ab^{-1}$ modulo $p$ equals $2n$. A weaker statement, namely that the order divides $2n$, would not suffice. The defining property of the cyclotomic polynomial is that its roots are precisely the primitive $2n$th roots of unity. Since $\Phi_{2n}(x)\equiv0\pmod p$, the order cannot be a proper divisor of $2n$.

The second delicate step is deriving $x^n\equiv-1$. Since $p\nmid b$, the inverse of $b^n$ exists modulo $p$. From

$$a^n+b^n\equiv0\pmod p$$

we obtain

$$(ab^{-1})^n\equiv-1\pmod p.$$

No cancellation involving a noninvertible element occurs.

The third delicate step is concluding $2n\mid(m-n)$. From

$$x^m\equiv x^n$$

we get

$$x^{m-n}\equiv1.$$

This implication uses only the invertibility of $x$. Since the order of $x$ is exactly $2n$, every exponent producing $1$ is a multiple of $2n$. Replacing “exactly” by “divides $2n$” would leave a gap and would not force $n\mid m$.

Alternative Approaches

A different proof uses primitive prime divisors. One chooses a prime $p$ dividing $a^n+b^n$ that does not divide $a^k+b^k$ for any $k<n$. Such a prime exists except for a few small exceptional cases, which can be checked directly. Modulo $p$, the element $x=ab^{-1}$ then has order exactly $2n$. The remainder of the argument is identical: from $p\mid a^m+b^m$ one gets $x^m\equiv-1$, hence $x^{m-n}\equiv1$, and the order condition yields $2n\mid(m-n)$.

The cyclotomic approach is preferable because it isolates the exact-order information in the factor $\Phi_{2n}(a,b)$ and avoids a separate discussion of exceptional cases for primitive divisors.