stroller wrote:

Close! Now you just need extra cares to deal with the rest It is clear that it suffices to show that for each $1\leq m\leq 100$, there exists a prime power that divides $N^m+m$ but not any other $N^{m'}+m'$ for some $1\leq m'\leq 100, m'\neq m$. If this is not the case for some $m$, then we have \[N^m+m\leq \prod_{m'\neq m, 1\leq m'< 100}\gcd(N^{m'}+m', N^m+m)\leq \prod_{m'=1}^{99}\left(m'^m+m^{m'}\right).\]This shows that \[N\leq \prod_{m'=1}^{99}\left(m'^m+m^{m'}\right)^{1/m}\leq \prod_{m'=1}^{99}\left(m'+(m^{1/m})^{m'}\right).\]We know that $m^{1/m}\leq 3^{1/3}$. Therefore \[N\leq 3^{4950/3}\prod_{i=1}^{99}\left(1+i3^{-i/3}\right)<3^{1650}\left(1+\frac{\sum_{i=1}^{99}i3^{-i/3}}{99}\right)^{99}<3^{1650}\left(1+\frac{3^{-1/3}}{(1-3^{-1/3})^2\cdot 99}\right)^{99}<2^{5000}.\]

We can prove that pairwise $\gcd\text{s} $ are not very big. $\gcd\left(N^{a_1}+a_1,N^{a_2}+a_2\right)$ is at most $a_1^{a_2}+a_2^{a_1}. $ Since the former divides $N^{a_1}a_2-(-a_1)^{-a_2}, $ the latter divides $N^{a_1}a_2-(-a_2)^{a_1}. $ It suffices to prove that each factor has a prime factor that the others don't. Product of all these $\gcd\text{s}$ are smaller than the factor. It will directly work for $N>2^{70000}. $ If we consider each $a_k $ individually we can get around $2^{3000}. $ Lemma- If $m\mid N^a + a, N^b + b$ then $m\mid(-a)^b - (-b)^a$. Proof- $N^a+a\mid N^{ab}-(-a)^b,N^b+b\mid N^{ab}-(-b)^a\implies m\,\text {divides both}.$ Thus $m $ divides the difference, which is $(-a)^b-(-b)^a. $

USJL wrote: ... wow thanks! I got what was in post #2 relatively quickly and thought I would need some other way to get a better bound, then searched for a long time to no avail

Wow another "size_goes_brrrrrr" problem . . any way here is

are "'size_goes_brrrrrr problem[s]' " considered a real category of problem

pog wrote: are "'size_goes_brrrrrr problem[s]' " considered a real category of problem they are infact the 5th subject in olympiad mathematics so we have: Algebra Number theory Combinatrics Geometry size go brrrrrrr

Solved with nukelauncher. The key is to spam the following: Claim: If \(m\) divides \(N^x+x\) and \(N^y+y\), then \(p\) divides \((-x)^y-(-y)^x\). Proof. Not hard: note that \((-x)^y\equiv\left(N^x\right)^y\equiv\left(N^y\right)^x\equiv(-y)^x\pmod m\). \(\blacksquare\) The goal is to show the following lemma: Lemma: Let \(N>2^{5000}\). For every \(1\le x\le 99\) there is a \(p\) such that \(\nu_p\left(N^x+x\right)\) is (unique and) maximal over all choices of \(x\). Proof. Assume for contradiction that for some \(1\le i\le99\), for every prime \(p\) there exists \(j\) with \(\nu_p(f(i))\le\nu_p(f(j))\). Then \[p^{\nu_p(f(i))}\quad\text{divides}\quad\left\lvert(-i)^j-(-j)^i\right\rvert.\]Hence it follows that \[N^i<f(i)\le\prod_{\substack{j=1\\ j\ne i}}^{99}\left\lvert(-i)^j-(-j)^i\right\rvert\le\prod_{j\ne i}\left(i^j+j^i\right).\] I claim the right-hand expression is at most \(2^{5000i}\), from which \(N<2^{5000}\) will follow. For \(i=1\), the conclusion is obvious, so assume \(i\ge2\). Observe the following: for \(x\ge y\), we have \(x^y\le y^x\) unless \(y=1\) or \((x,y)=(3,2)\). Therefore, \begin{align*} \prod_{j\ne i}\left(i^j+j^i\right)&\le17/16\cdot(i+1)/2\cdot\prod_{j\ne i}2\min\{i,j\}^{\max\{i,j\}}\\ &<17/16\cdot i\cdot2^{98}\cdot\prod_{j<i}j^i\cdot\prod_{j>i}i^j\\ &<17/16\cdot100\cdot2^{98}\cdot(i-1)!^i\cdot i^{(100+i)(99-i)/2}\\ &<17/16\cdot100\cdot2^{98}\cdot i^{i^2/2}\cdot i^{(100+i)(100-i)/2}\\ &=17/16\cdot100\cdot2^{98}\cdot i^{5000}\\ &\le17/16\cdot100\cdot2^{98}\cdot2^{5000(i-1)}\\ &<2^{5000i} \end{align*}where the second-to-last inequality comes from \(i\le2^{i-1}\). \(\blacksquare\) For each \(x\) in the lemma, let \(f(x)\) be that unique prime. Then \(f(a_1)\), \ldots, \(f(a_k)\) are distinct primes that divide the product in question, end proof.

@ above, where did you get $(i-1)!^i<i^{i^2/2}$? The other direction should be true.(j*(i-j)>i) We actually need to prove $2^{5000i}>2^{5000+i^2/2}$ which is not hard.

Suppose $p\mid N^a+a, N^b+b$ (here p is not necessarily a prime) Then $N^{ab}=(N^a)^b\equiv (-a)^b(\bmod\; p)$ and $N^{ab}=(N^b)^a\equiv (-b)^a(\bmod\; p)$ Therefore, $p\mid (-a)^b-(-b)^a$. This is small compared to $N$ given $N>2^{5000}$ and $1\le a,b<100$ In particular, $\frac{N^a+a}{\prod\limits_{b\ne a} \gcd(N^a+a, N^b+b)} \ge \frac{2^{5000a}}{\prod\limits_{b\ne a} a^b+b^a}$ If I claim this is $>1$, I'm done because this is a rational, and at most one of them is divisible by one prime, so there is a perfect matching between the sequence $N^i+i$ and primes. When $a=1$, the denominator is simply $100!$. When $a=2$, the value is $2^{10000}/(17){\prod\limits_{b\ne 2,3} 2^b+b^2}>2^{9995}{\prod\limits_{b\ne 2,3} 2^{b+1}}=2^{9995-5045}>1$ When $a=3$, this is $2^{15000}/2^{99}3^{5047}$ When $a\ge 4$, this is $2^{5000a}/(a+1)\prod\limits_{2<b<a} b^a \prod\limits_{a<b<100} a^b=2^{5000a}/(a+1)((a-1)!)^a \prod\limits_{a<b<100} a^b > 1$

Unfinished, will finish writeup later. Can anyone please check for fakesolve? The solutions above are quite different from mine. Define $P(k) = N^k + k$ for $k = 1, 2, \dots, 99$. Claim: $P(i)$ cannot divide $\prod_{j\neq i}P(j)^{\alpha_j}$ as polynomials with respect to $N$. proof: The modulus of the roots of $P(i)$ and $P(j)$ are all different except for $\{i, j\} = \{2, 4\}$. However, the roots of $P(2)$ and $P(4)$ are different, so all of the roots of these polynomials are different, hence divisibility can not occur. Now, suppose $\omega\prod_{i = 1}^k(N^{a_i} + a_i)=m\leq k - 1$, label the prime divisors as $p_1, p_2, \dots, p_m$then by pigeonhole there exists a number $a_\ell$ such that $\nu_{p_i}P(a_\ell)\leq \text{Max}\{\nu_{p_i}P(a_1),\nu_{p_i}P(a_2),\dots, \nu_{p_i}P(a_k)\}$ for $i = 1, 2, \dots, m$. Hence, \[P(a_\ell)\mid \prod_{i\neq \ell} P(a_i).\]We'll claim that this results in a contradiction with the size of $N$. By the claim above, when $P(a_i)$ is divided by $P(a_\ell)$, it should leave a nonzero remainder with degree less than $a_\ell$. Hence, \[P(a_\ell)\mid \prod_{i\neq \ell} P(a_i)\Longrightarrow P(a_\ell)\mid \prod_{i \neq\ell}((-a_\ell)^{\lfloor\frac{a_i}{a_\ell}\rfloor}N^{b_i} + a_i)\]Where $b_i$ is an nonnegative integer less than $a_{\ell}$. We then multiply the expressions below together two at a time, and replace the powers of $N$ larger than or equal to $N^{a_\ell}$ with $-a_i$ like what we did above. Every time we combine two expressions, the sum of the absolute value of coefficients won't be larger than $a_\ell$ times the product of the sum of the absolute value of coefficients of the two separate expressions. Thus, the sum of the absolute value of coefficients in the final expression is bounded by \[a_\ell^{97} (a_\ell^{\frac{a_1 + a_2 + \dots + a_k}{a_\ell}})\leq 2^{5000}\]Which results in a contradiction as this means $P(a_{\ell})$ can exceed the final expression. Hence, we are done.

Fitst notice that if $m \mid N^a+a, N^b+b$ then $(-a)^b \equiv N^{ab} \equiv (-b)^a \pmod m$ therefore $m \mid (-a)^b-(-b)^a$ and this gives a bound for $\gcd(N^a+a,N^b+b)$ trivially unless $a=b$ or $(a,b)=(4,2)$ (the latter is just a spam $\nu_p$ exercise) in which case just note that $N^2+2 \mid N^4-4$ therefore if $(a,b)=(2,4)$ then $m \mid 8$ so it is also bounded by a very small constant. Now we also claim that for each $1 \le \ell \le 99$ there exists a prime $p$ such that $\nu_p(N^{\ell}+\ell)$ is strictly maximal over all other possible choices, indeed if this was false then for some fixed $1 \le i \le 99$ for every prime $p$ we can always pick a $j \ne i$ also between $1$ and $99$ such that $\nu_p(N^i+i) \le \nu_p(N^j+j)$, we now prove this would in fact imply that, $N \le 2^{5000}$. Notice from an easy $\nu_p$ check using $\gcd$ definition we get that: \[N^i<N^i+i \le \prod_{\substack{j=1\\ i \ne j}}^{99} \gcd(N^i+i, N^j+j) \le \prod_{\substack{j=1 \\ i \ne j}}^{99} |(-i)^j-(-j)^i| \le \prod_{\substack{j=1 \\ i \ne j}}^{99} i^j+j^i \]Notice the last bound holds either way even if we had $(i,j)=(2,4)$ so we are fine, now: \[ N < \prod_{\substack{j= 1\\ i \ne j}}^{99} (i^j+j^i)^{\frac{1}{i}} \le \prod_{\substack{j=1 \\ i \ne j}}^{99} (i^{\frac{j}{i}}+j) \le \prod_{j=1}^{99} (e^{\frac{j}{e}}+j)=e^{\frac{4950}{e}} \cdot \prod_{j=1}^{99} (1+j \cdot e^{-\frac{j}{e}})<e^{\frac{4950}{e}} \left(1+\frac{\sum_{j=1}^{99} j \cdot e^{\frac{j}{e}}}{99} \right)^{99}<e^{\frac{4950}{e}} \left(1+\frac{e^{-\frac{1}{e}}}{(1-e^{-\frac{1}{e}})^2 \cdot 99} \right)^99<2^{5000} \]Which contradicts the assumption of the problem, therefore such prime $p$ for each $\ell$ exists and we just pick it, clearly we can't pick it twice from each and therefore there is at least $k$ prime divisors thus we are done .