Prove that $m^{2013}-m^{20}+m^{13}-2013$ has at least $N$ prime divisors

Solution 1:

The following solution deliberately avoids finding the prime factorization of $2013$, thanks to the rather generous exponents occuring in the given expression.

Let's introduce the $p$-adic valuation: If $p\in\mathbb P$ is a prime and $n\in\mathbb Z\setminus\{0\}$ let $v_p(n)$ denote the exponent of $p$ in $n$, that is $v_p(n)=\max\{r\in\mathbb Z: p^r|n\}$. For convenience, $v_p(0)=+\infty$. Then $$\tag1v_p(ab)=v_p(a)+v_p(b)$$ and $$\tag2v_p(a\pm b)\ge\min\{v_p(a),v_p(b)\}$$ and more specifically $$\tag3v_p(a\pm b)=\min\{v_p(a),v_p(b)\}\quad \text{if }v_p(a)\ne v_p(b).$$ Right from $2013<2^{11}$ we get the (awfully crude) estimate $$\tag4 v_p(2013)<11\quad\text{for all }p\in\mathbb P.$$ Let $$S=\{p\in\mathbb P\mid\exists m\colon m^{2013}-m^{20}+m^{13}-2013\equiv 0\pmod p\}$$ be the set of primes occuring as prime divisors of the considered expression. For example, $$\tag5 p\in\mathbb P,\, p|2013\implies p\in S$$ follows from considering $m=0$.

Assume that the set $S$ is finite. Let $$M=\prod_{p\in S}p.$$

• If $p$ is a prime $\notin S$, then $v_p(M^{2013}-M^{20}+M^{13}-2013)=0$ by definition of $S$ and also $v_p(2013)=0$ because of $(5)$.
• And for $p\in S$, we have $v_p(M^{2013}-M^{20}+M^{13})\ge 13v_p(M)\ge 13>v_p(2013)$ from $(1)$, $(2)$, and $(4)$; hence $v_p(M^{2013}-M^{20}+M^{13}-2013)=v_p(2013)$ by $(3)$.

Thus $v_p(M^{2013}-M^{20}+M^{13}-2013)=v_p(2013)$ for all primes $p$. This implies $$M^{2013}-M^{20}+M^{13}-2013=\pm2013.$$ But from $(5)$ we have $S\ne\emptyset$, i.e. $M\ge 2$ and hence $$\begin{align}M^{2013}-M^{20}+M^{13}-2013&=(M^{1993}-1)M^{20}+M^{13}-2013\\&>M^{13}-2013\ge2^{13}-2013>2013,\end{align}$$ contradiction! We conclude from this contradiction that the set $S$ is infinite.

Given $N$, we can therefore select $N$ distinct primes $p_k\in S$, $k=1,\ldots, N$. For each $k$, there exists $m_k\in\mathbb Z$ such that $m_k^{2013}-m_k^{20}+m_k^{13}-2013\equiv 0\pmod{p_k}$. Using the Chinese remainder theorem, there exists $m\in\mathbb N$ such that $m\equiv m_k\pmod{p_k}$ for all $k$. Then $$ m^{2013}-m^{20}+m^{13}-2013\equiv m_k^{2013}-m_k^{20}+m_k^{13}-2013\equiv 0\pmod{p_k},$$ i.e. at least the $N$ different primes $p_k$ are divisors of $ m^{2013}-m^{20}+m^{13}-2013$.

Remark: The same argument works with any expression of the form $m^rf(m)+c$, where $f$ is a polynomial and $c$ is not divisible by any $r$th prime power and $f(m)\ge1$ if $m\ge \prod_{p|c}p$.

Solution 2:

I guess it works for any non-constant polynomial with integer coefficients.

Let $f(x)=\sum_{i=0}^na_ix^i$, $n\ge 1$, with $a_n\ne 0$ and all $a_i$ integers. We show that $\{p \textrm{ prime: there is an integer } m \textrm{ such that } p \textrm{ divides } f(m)\}$ is an infinite set.

If $a_0=0$ the assert is clear. Let's assume $a_0\ne 0$.

Suppose the set is finite and let $p_1,...,p_k$ be all of them. Let $g(x)=f(a_0x)/a_0$. Then $g(x)$ is a non-constant polynomial with integer coefficients with constant term 1. Let $m_c=c\cdot p_1\cdots p_k$ where $c$ is any integer. Since $g(m_c)$ has no prime factor other than $p_1$, ..., $p_k$ while $g(m_c)$ is congruent to 1 mod every $p_i$, it follows that $g(m_c)=1$ for every $c$. But $g(x)=1$ has at most $n$ roots, a contradiction.

To answer the original question, use Chinese Remainder Theorem as Hagen von Eitzen did above.