Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

for positive integer $N>1$,There always exists $m$ such that $$m^{2013}-m^{20}+m^{13}-2013$$ has at least $N$ prime divisors

Thank you all, this is good problem, but I don't know how to solve it.

share|improve this question
2  
Source?${}{}{}$ –  Gerry Myerson Jul 7 '13 at 11:20
    
N is the no. of divisors including 1, right? –  Rohinb97 Jul 7 '13 at 13:05
    
yes,Thank you @Rohinb97 –  math110 Jul 7 '13 at 13:12
    
@math110: How do you include $1$ in your prime divisors list? –  Inceptio Jul 7 '13 at 13:24
2  
SOURCE?${}{}{}$ –  Gerry Myerson Jul 8 '13 at 12:59
show 7 more comments

2 Answers 2

up vote 10 down vote accepted

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$.

share|improve this answer
    
It's good job,But I don't undestand your solution.Thank you –  math110 Jul 7 '13 at 13:53
    
He is saying that if any no. has factors like 3,11,61 then the term only has these as it's prime factors. But he contradicted to prove that the above set is infinite. So it mus pt be true in general also. –  Rohinb97 Jul 7 '13 at 13:58
    
@math110 Where did I lose you specifically? –  Hagen von Eitzen Jul 7 '13 at 14:02
    
oh,Thank you,@HagenvonEitzen,+1 –  math110 Jul 7 '13 at 14:11
    
Why the downvote? –  Hagen von Eitzen Jul 7 '13 at 14:20
show 1 more comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.