Given k is a positive integer, m is a positive odd number. Prove: there exists a positive integer n, such that mn+nm has at least k distinct prime factors. (65th Romanian National Team Selection Test)
Solution
≡mn+nm≡0(modpi).
On the other hand, mn1+n1m=mn+mn[(mφ(pjp))φ((pip1p2−pk)c)−1]+nm+∑j=1mCmjnm−jMj, vpi(j=1∑mCmjnm−jMj)⩾vpi(M)⩾t−1,
But vpi(mn+nm)⩽max1⩽i⩽k{αi}mn+nm, so mn1+n1m has a prime factor different from p1,p2,⋯,pk, meaning it has at least k+1 distinct prime factors. Thus, the conclusion holds for k+1. In summary, for any positive integer k, there exists a positive integer n such that mn+nm has at least k distinct prime factors. Proof by induction on k. When k=1, take n=m. Assume the conclusion holds for k, i.e., there exists a positive integer n such that mn+nm has at least k distinct prime factors. Now prove the case for k+1. If mn+nm has at least k+1 distinct prime factors, then the conclusion holds for k+1. If mn+nm has exactly k distinct prime factors, let mn+nm=p1α1p2α2⋯pkαk. Take t>max1⩽i⩽k{αi}+1⩾2∈Z+, n1=n+φ((p1p2⋯pk)t). Let M=φ((p1p2⋯pk)t). 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.