Let $k$ be a nonzero natural number and $m$ an odd natural number . Prove that there exist a natural number $n$ such that the number $m^n+n^m$ has at least $k$ distinct prime factors.
Problem
Source: Romania TST 2014 Day 1 Problem 4
Tags: induction, modular arithmetic, number theory, relatively prime, prime factorization, number theory unsolved
Zlun
26.12.2014 00:44
ComplexPhi wrote: Let $k$ be a nonzero natural number and $m$ an odd natural number . Prove that there exist a natural number $n$ such that the number $m^n+n^m$ has at least $k$ distinct prime factors. We first prove by induction that there exists $k$ primes $p_1,p_2,...,p_k$ ($>m$) satisfying $\gcd((p_1-1)..(p_k-1),p_1p_2...p_k))=1$, for $k=1$ it's easy, if $p_1,p_2,...,p_{k-1}$ are already found then by Dirichlet theorem we can find $p_k$ large enough ($> \max_i\{p_i-1\}$) and having the form $p_k=tN+2$ where $N=p_1p_2...p_{k-1}$, such $p_k$ is obviously the good one to finish the induction ! Now by the Chinese remainder theorem we can find $n$ satisfying the two conditions $n \equiv -1 \pmod{ p_1p_2...p_k}$ and $n\equiv 0 \pmod{(p_1-1)..(p_k-1)}$, by Fermat's little theorem we can easily see that $m^n+n^m$ has at least $p_1...,p_k$ as a prime divisors.
tahanguyen98
29.01.2015 09:34
A solution without Dirichlet's Theorem
First we state the lemma and prove it:
Lemma: Let $p$ be and odd prime, $m>1$ and $m+1$ is not divisible by $p$ then the number $m^{p^k}$ has at least $k$ distinct prime factors
Proof:
To prove this lemma, we have a small statement as follow:
Statement: $m^{p^l}+1$ is not divisibly by $p$, indeed, assume the contrary, $p|m^{p^l}+1 \rightarrow p|m^{2p^l}-1$ then $ord_{p}(m)|2p^l$ but $ord_{p}(m)|p-1$ thus $ord_{p}(m)|gcd(2p^l,p-1)=1,2$
#If $ord_{p}(m)=1$ then $p|m-1$ implies $p|m^{p^l}-1$, but since $p|m^{p^l}+1$ then $p|2$ a contradiction!
#if $ord_{p}(m)=2$ then $p|m^2-1$ implies $p|m+1$ (because if $p|m-1$ then $ord_{p}(m)=1$ a contradiction) but this is also a contradiction since we assume that $m+1$ is not divisible by $p$
__
Now, come back to our lemma, $m^{p^k}+1=(A+1)(A^{p-1}-...-A+1)$ where $A$ is $m^{p^{k-1}}$
Let $d=gcd(A+1,A^{p-1}-...-A+1)$ then $A \equiv -1 \pmod{d}$ thus $A^{p-1}-...-A+1 \equiv p \pmod{d}$, hence $d|p$ but from above claim, we prove that $A+1=m^{p^{k-1}}+1$ is not divisible by $p$ then $d=1$ so $A+1,A^{p-1}-...+A-1$ are relatively prime, immediately, we have $A^{p-1}+...+A+1$ has at least a prime factor which doesn't occur in prime factorization of $A+1$, and note that $A+1=m^{p^{k-1}}+1$ applying the above proof for $k-1$ times, we obtain $m^{p^k}$ has at least $k$ distinct prime factors...
_________________
Come back to our problem
Case 1: $m>1$, first, for convenience, choose $n=m^t$ for which $t$ will be chosen later.
Thus $m^n+n^m=m^{m^t}+m^{tm}=m^{tm}(m^{m^t-tm}+1=m^{tm}((m^m)^{m^{t-1}-t}+1)$
It suffices prove for $(m^m)^{m^{t-1}-t}+1$ that it will have $k$ distinct prime factors
First, we prove there exist $t$ such that $p^k|m^{t-1}-t$ with $p$ is an odd prime and $p|m$ since $m>1$ and $m$ is an odd number
$p^k|m^{t-1}-t$ simply choose $t=p^k$ thus $t-1=p^k-1>k$ then $p^k|m^{t-1}-t$ (since $p|m$)
So, we have $m^{t-1}-t=p^k.w$ with $w$ is an integer
Now, $(m^m)^{m^{t-1}-t}+1=(m^{mw})^{p^k}+1$ since $m^{mw}+1 \equiv 1 \pmod {p}$ (since $p|m)$ so $m^{mw}+1$ is not divisibly by $p$, applying the lemma, we obtain $(m^{mw})^{p^k}+1$ has at least $k$ prime factors, <QED>
Case 2: $m=1$ then $m^n+n^m=1+n$ this is obviously easy, simply choose $n=p_1.p_2...p_k-1$ with $p_1,...,p_k$ are distinct primes number <QED>
Wolstenholme
31.03.2015 19:53
This solution is similar to tahanguyen98's, but the use of Zsigmondy's Theorem makes it much shorter. Firt note that if $ m = 1 $ the problem is trivial so assume $ m > 1. $ Let $ n = m^r $ for some $ r $ to be determined later. Then $ m^n + n^m = m^{rm}\left(m^{m^r - rm} - 1\right). $ Let $ p $ be an odd prime that divides $ m $ and let $ r = p^k. $ Then since $ p^k \vert m^r - rm $ we have that $ m^{p^j} - 1 \vert m^{m^r - rm} - 1 $ for all $ j \in \{1, 2, \dots, k\} $ and by Zsigmondy's Theorem each of these divisors contains a "new" prime factor so we have found $ k $ distinct prime factors as desired.
Pythagorasauras
13.05.2015 23:22
Wolstenholme wrote: This solution is similar to tahanguyen98's, but the use of Zsigmondy's Theorem makes it much shorter. Firt note that if $ m = 1 $ the problem is trivial so assume $ m > 1. $ Let $ n = m^r $ for some $ r $ to be determined later. Then $ m^n + n^m = m^{rm}\left(m^{m^r - rm} - 1\right). $ Let $ p $ be an odd prime that divides $ m $ and let $ r = p^k. $ Then since $ p^k \vert m^r - rm $ we have that $ m^{p^j} - 1 \vert m^{m^r - rm} - 1 $ for all $ j \in \{1, 2, \dots, k\} $ and by Zsigmondy's Theorem each of these divisors contains a "new" prime factor so we have found $ k $ distinct prime factors as desired. I think there is a mistake because $ m^n + n^m = m^{rm}\left(m^{m^r - rm} + 1\right). $, not $ m^n + n^m = m^{rm}\left(m^{m^r - rm} - 1\right). $
anantmudgal09
22.09.2015 08:39
Another overkill( why are Romanian problems so interesting yet hard that heavy artillery comes in?) Choose primes $p_1<p_2<...<p_k$ such that $p_1> 10^{1,000,000,000} $(lol) with the condition $p_j \equiv 2$ mod $p_1...p_{j-1}$ (Dirichlet's Theorem Guarantees this) Now choose $n \equiv 0$ mod $p_i-1$ $\forall 1\le i\le k$ and $n \equiv -1$ mod$p_1$ $\forall 1\le i\le k$ ( CRT guarantees this construction) Now we are done.
for63434
06.10.2016 18:57
i have a solution without using Dirichlet or Zsigmondy's theorem let $n=m^x$ then $m^n+n^m=m^{m^x}+m^{mx}=m^{mx}(m^{m^x-mx}+1)$ so lets prove that there exists x which $m^{m^x-mx}+1$ has $k$ distinct divisors. now lets set a prime $r$ which is a divisor of $m$ then we can easily prove that (by mathematical induction) $m^{r^s}+1$ has at least $s$ distinct divisors (because $r$ is coprime with $m+1$) now if you let $x=r^k2t$ and the distinct divisors of $m^{r^k}+1$ $p_1 \cdots p_k$ since $r^k \mid m^{x-1}-x$(when you fix $t$ large enough) we can say that $p_i \mid m^{r^k}+1 \mid m^{m^{x-1}-x}+1 \mid (m^{m^{x-1}-x})^m+1=m^{m^x-mx}+1$ so there exists $x=r^k2t$ which $m^{m^x-mx}+1$ has $k$ distinct divisors $p_1 \cdots p_k$ And the proof is completed. I will be ready for feedbacks... please tell me if i'm right or wrong...
nikolapavlovic
09.04.2017 14:33
It suffices to show that $\omega(m^n+n^m)$ can get arbitrary large for fixed odd $m$.Set $n=mk$ and i'll show that $\omega(m^k+mk)$ goes to infinity that is $\omega(m^{k-1}+k)$.Let $f(a)=m^a+a+1$, notice that $f(a+s\cdot p(p-1))\equiv _p f(a)$ $\forall p$ $p>> m$.Let $a\equiv 0\pmod {p-1}$ and $a\equiv -2 \pmod{p}$ such $a$ surely exisxts byCRT and $p\mid f(a)$.Now just choose bunch of primes $\{p_i\}_{i=1}^s$ so that $\forall i,j$ we have that $(p_i(p_i-1),p_j(p_j-1))=1$ and construct : $$A\equiv a_i \pmod {p_i(p_i-1)}, \forall i\leq s$$Where $f(a)\equiv 0\pmod {p_i}$.Now $\omega(f(A))>s$ and hence the desired follows.$\blacksquare$