Maths Olympiad Prep

Library / /407 of 520

Number theory Difficulty 6.0 AIME, harder Prove it

Given kk is a positive integer, mm is a positive odd number. Prove: there exists a positive integer nn, such that mn+nmm^{n}+n^{m} has at least kk distinct prime factors.
(65th Romanian National Team Selection Test)

Solution

mn+nm0(modpi). \equiv m^{n}+n^{m} \equiv 0\left(\bmod p_{i}\right) .

On the other hand,
mn1+n1m=mn+mn[(mφ(pjp))φ((p1p2pkpi)c)1]+nm+j=1mCmjnmjMj, \begin{array}{l} m^{n_{1}}+n_{1}^{m} \\ =m^{n}+m^{n}\left[\left(m^{\varphi\left(p_{j}^{p}\right)}\right)^{\varphi}\left(\left(\frac{p_{1} p_{2}-p_{k}}{p_{i}}\right)^{c}\right)-1\right]+ \\ \quad n^{m}+\sum_{j=1}^{m} \mathrm{C}_{m}^{j} n^{m-j} M^{j}, \end{array}
vpi(j=1mCmjnmjMj)vpi(M)t1 v_{p_{i}}\left(\sum_{j=1}^{m} \mathrm{C}_{m}^{j} n^{m-j} M^{j}\right) \geqslant v_{p_{i}}(M) \geqslant t-1 \text {, }

Therefore, vpi(mn[(mφ(pit))φ((p1p2pkpi)t)1]+v_{p_{i}}\left(m^{n}\left[\left(m^{\varphi\left(p_{i}^{t}\right)}\right)^{\varphi\left(\left(\frac{p_{1} p_{2} \cdots p_{k}}{p_{i}}\right)^{t}\right)}-1\right]+\right.
j=1mCmjnmjMj)t1 \left.\sum_{j=1}^{m} \mathrm{C}_{m}^{j} n^{m-j} M^{j}\right) \geqslant t-1 \text {. }

But vpi(mn+nm)max1ik{αi}mn+nmv_{p_{i}}\left(m^{n}+n^{m}\right) \leqslant \max _{1 \leqslant i \leqslant k}\left\{\boldsymbol{\alpha}_{i}\right\}m^{n}+n^{m}, so mn1+n1mm^{n_{1}}+n_{1}^{m} has a prime factor different from p1,p2,,pkp_{1}, p_{2}, \cdots, p_{k}, meaning it has at least k+1k+1 distinct prime factors.
Thus, the conclusion holds for k+1k+1.
In summary, for any positive integer kk, there exists a positive integer nn such that mn+nmm^{n}+n^{m} has at least kk distinct prime factors.
Proof by induction on kk.
When k=1k=1, take n=mn=m.
Assume the conclusion holds for kk, i.e., there exists a positive integer nn such that mn+nmm^{n}+n^{m} has at least kk distinct prime factors.
Now prove the case for k+1k+1.
If mn+nmm^{n}+n^{m} has at least k+1k+1 distinct prime factors, then the conclusion holds for k+1k+1.
If mn+nmm^{n}+n^{m} has exactly kk distinct prime factors, let mn+nm=p1α1p2α2pkαkm^{n}+n^{m}=p_{1}^{\alpha_{1}} p_{2}^{\alpha_{2}} \cdots p_{k}^{\alpha_{k}}.
Take t>max1ik{αi}+12Z+t>\max _{1 \leqslant i \leqslant k}\left\{\alpha_{i}\right\}+1 \geqslant 2 \in \mathbf{Z}_{+},
n1=n+φ((p1p2pk)t)n_{1}=n+\varphi\left(\left(p_{1} p_{2} \cdots p_{k}\right)^{t}\right).
Let M=φ((p1p2pk)t)M=\varphi\left(\left(p_{1} p_{2} \cdots p_{k}\right)^{t}\right).
By Euler's theorem,
\begin{array}{l} m^{n_{1}}+n_{1}^{m}=m^{n+M}+(n+M)^{m} \\ \equiv m^{n}\left(m^{\varphi\left(p_{i}^{t}\right)}\right)^{\varphi}\left(\left(\frac{p_{1} p_{2} \cdots p_{k}}{p_{i}}\right)^{t}\right)+ \\ \quad\left[n+\left(p_{1} p_{2} \cdots p_{k}\right)^{t-1} \prod_{i=1}^{k}\left(p_{i}-1\right)\right]^{m}

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.