A generalization which is harder: Suppose that $m,n$ are natural numbers ,$n$ is not divisible by 3 and $gcd(m^{2n}+m^{n}+1,2nm^{2n-1}+nm^{n-1}+1)=1$ .Prove that the number $ (m^{2n}+m^{n}+m+1)^{2n}+(m^{2n}+m^{n}+m+1)^{n}+1 $ has at least $2d(n)$ distinct prime factors where $d(n)$ is the number of positive divisors of n.

some solutions?

hint

goodar2006 wrote:

hint

goodar2006, can you explain more? I don't know what property the form $n^{2n}+n^n+n+1$ has. I can only proof $ (n^{2n}+n^n+n+1)^{2n}+(n^{2n}+n^n+n+1)^n+1 $ has $d(n)$ distinct prime divisors.

Here is an additional hint which may help you solve the problem: note that $\Phi_{3k}(x)|\Phi_{3k}(x^{2n} + x^n + x + 1)$ when $k|n$ as a polynomial identity. Can you finish from here?

what if n=1 ?

$4^2 + 4 + 1$ has $2 = 2d(1)$ prime factors so what is the problem

Any full solution?..

Can anyone help please?i still do not have any idea

I'm going to follow dinoboy's hint above. Let $\Phi_{3k}(x)$ be the cyclotomic polynomial of order $3k$. Then for every $k \mid n$ we have $\Phi_{3k}(x) | x^{2n} + x^n + 1$. This is because if $\alpha$ is a primitive root of unity of order $3k$, then $\alpha^{3n} = 1$ but $\alpha^{n} \neq 1$ since $3k \nmid n$. Thus $\alpha^{2n} + \alpha^n + 1 = 0$. This implies $\Phi_{3k}(x) \mid x^{2n} + x^n + 1$, and consequently $\Phi_{3k}(x) \mid \Phi_{3k}(x^{2n} + x^n + x + 1).$ Letting $x = n$, we have $\Phi_{3k}(n) \mid \Phi_{3k}(n^{2n} + n^n + n + 1)$ as integers. For different $k$ dividing $n$, choose any primes $p_k$ that divides $\Phi_{3k}(n)$. We claim that these primes are distinct. In fact, by standard argument either $n$ has multiplicative order $3k$ ($mod~p_k$), or $p_k \mid 3k$. In the former case $p_k$ is indeed different from other $p_j$. In the the latter scenario, either $p_k = 3$ or $p_k \mid n$, which is ruled out as $\Phi_{3k}(n) \equiv 1~(mod~n)$. To prove the claim it remains to show $p_k = p_j = 3$ cannot happen. This is because $\Pi_{k \mid n} \Phi_{3k}(n) = n^{2n} + n^n + 1$ is not divisible by $9$. With the claim, we have $p_k \mid \Phi_{3k}(n) \mid \Phi_{3k}(n^{2n} + n^n + n + 1) \mid (n^{2n} + n^n + n + 1)^{2n} + (n^{2n} + n^n + n + 1)^n + 1$. Thus as people have pointed out above, the number has at least $d(n)$ distinct prime divisors. To squeeze another $d(n)$ prime divisors, we will choose primes $q_k \neq p_k$ that divides $\Phi_{3k}(n^{2n} + n^n + n + 1)$. Suppose for the time being that $q_k \neq p_k$ is feasible. We need to show $q_k \neq p_j$ and $q_k \neq q_j$. The former is because if $p_j \mid \Phi_{3k}(n^{2n} + n^n + n + 1)$, then from $p_j \mid \Phi_{3j}(n) \mid n^{2n}+n^n+1$ we have $p_j | \Phi_{3k}(n)$, contradicting our earlier proof that $\Phi_{3j}(n)$ and $\Phi_{3k}(n)$ are co-prime. To prove $q_k \neq q_j$, we run the same Zsigmondy-type argument as above. In fact, since $q_k \mid \Phi_{3k}(n^{2n} + n^n + n + 1)$, either $n^{2n} + n^n + n + 1$ has multiplicative order $3k$ ($mod~p_k$), or $q_k | 3k$. The former leads directly to $q_k \neq q_j$. The latter leads to either $q_k \mid n$ or $q_k = 3$. But $\Phi_{3k}(x)$ is equal to $1~(mod~x-1)$, unless $k = 3^t$ in which case the residue is $3$. Thus $\Phi_{3k}(n^{2n} + n^n + n + 1) \equiv 1,3~(mod~n)$. So $q_k$ cannot both divide $n$ and $\Phi_{3k}(n^{2n} + n^n + n + 1)$. That leaves us with the final case $q_k = 3$, which can be resolved in the same way as in the previous paragraph. Now we only need to check $p_k \neq q_k$ can be achieved. Suppose for contradiction that for some $k \mid n$, $\Phi_{3k}(n) = p^a$ and $\Phi_{3k}(n^{2n}+n^{n}+n+1) = p^b$ with prime $p$ and positive integers $a, b$. First we estimate the size of $\Phi_{3k}(x)$ in the following lemma: Lemma. Denote by $rad(3k)$ the product of distinct prime divisors of $3k$ and let $t = \frac{3k}{rad(3k)}$. Then for $x \geq n \geq 3$ it holds that $$ \Phi_{3k}(x) = x^{\phi(3k)}(1 \pm \lambda \cdot x^{-t}), ~\lambda \in (\frac{1}{2}, \frac{3}{2}),$$where the plus/minus sign depends on whether $3k$ has odd/even number of distinct prime factors. Proof. We have $\Phi_{3k}(x) = x^{\phi(3k)} \cdot \prod_{d | 3k} (1 - x^{-d})^{\mu(\frac{3k}{d})}$. The result follows by observing that the dominant term in the product is $(1-x^{-t})^{\mu(rad(3k))}.$ With this lemma we also have $\Phi_{3k}(n^{2n}+n^{n}+n+1) = (n^{2n}+n^n+n+1)^{\phi(3k)} (1 \pm \delta \cdot n^{-2nt}) = n^{2n\phi(3k)} (1+ (\phi(3k)+\epsilon)n^{-n})(1 \pm \delta \cdot n^{-2nt})$, collecting dominant terms and secondary terms only. Here $\delta \in (0.5, 1.5)$ and $\epsilon$ is small for $n$ large. Therefore $$p^{b - 2na} = \frac{\Phi_{3k}(n^{2n}+n^{n}+n+1)}{\Phi_{3k}(n)^{2n}} = \frac{(1+ (\phi(3k)+\epsilon)n^{-n})(1 \pm \delta \cdot n^{-2nt})}{(1 \pm \lambda\cdot n^{-t})^{2n}}.$$Suppose $t > 1$, then the denominator is about $1 \pm 2\lambda n^{-t+1}$. The error term here dominates that in the numerator because $t \leq \frac{n}{2}$ ($rad(3k) \geq 6$ unless $k = 1$) and $\phi(3k) \leq 2n$. Thus $p^{b-2na} \neq 1$ for large $n$. However, all the error terms vanish as $n$ becomes large, so we also have $\frac{1}{2} < p^{b-2na} < 2$, contradiction! Lastly consider $t = 1$. Then the denominator $(1 \pm \frac{\lambda}{n})^{2n}$ converges to $e^{\pm 2}$ since $\lambda \to 1$ as $n$ becomes large (refining the lemma). From the crucial equation above we then deduce that for large $n$, $p^{b-2na}$ must be very close to $e^{\pm 2}$. But $e^2$ is not an integer, so again we obtain a contradiction. So we have proved the result for all large $n$. I wonder if there is a better approach to the second part avoiding this much algebra.