Find all polynomials $P$ with integer coefficients which satisfy the property that, for any relatively prime integers $a$ and $b$, the sequence $\{P (an + b) \}_{n \ge 1}$ contains an infinite number of terms, any two of which are relatively prime.
Problem
Source:
Tags: algebra, polynomial, modular arithmetic, induction, number theory, relatively prime, algebra unsolved
10.12.2010 23:35
Rijul saini wrote: Find all polynomials $P$ with integer coefficients which satisfy the property that, for any relatively prime integers $a$ and $b$, the sequence $\{P (an + b) \}_{n \ge 1}$ contains an infinite number of terms, any two of which are relatively prime. There is no such polynomial. If $P(x)=a_0+a_1x+...+a_mx^m$, take a prime $p$ that divides $a_0+a_1+...+a_m$ and put $a=p,b=1$. Then for all integer $n$, $P(an+b)\equiv P(1)\equiv 0 \pmod p$.
11.12.2010 17:21
spanferkel wrote: Rijul saini wrote: Find all polynomials $P$ with integer coefficients which satisfy the property that, for any relatively prime integers $a$ and $b$, the sequence $\{P (an + b) \}_{n \ge 1}$ contains an infinite number of terms, any two of which are relatively prime. There is no such polynomial. If $P(x)=a_0+a_1x+...+a_mx^m$, take a prime $p$ that divides $a_0+a_1+...+a_m$ and put $a=p,b=1$. Then for all integer $n$, $P(an+b)\equiv P(1)\equiv 0 \pmod p$. Your interpretation of the problem is wrong. Read through the problem once again.
11.12.2010 17:55
Rijul saini wrote: spanferkel wrote: Rijul saini wrote: Find all polynomials $P$ with integer coefficients which satisfy the property that, for any relatively prime integers $a$ and $b$, the sequence $\{P (an + b) \}_{n \ge 1}$ contains an infinite number of terms, any two of which are relatively prime. There is no such polynomial. If $P(x)=a_0+a_1x+...+a_mx^m$, take a prime $p$ that divides $a_0+a_1+...+a_m$ and put $a=p,b=1$. Then for all integer $n$, $P(an+b)\equiv P(1)\equiv 0 \pmod p$. Your interpretation of the problem is wrong. Read through the problem once again. Sorry, I can't see what's wrong. Can you please give just one possible $P$ with that property, maybe I'll see it then. Or do you mean "for any relatively prime integers $a>1$ and $b>1$"?
12.12.2010 13:24
every such sequence will contain infinitely many terms...so i think the problem says that there exists infinitely many coprime terms. If so,$P(x)=x$ satisfies the property since Dirichlet's theorem says that there exists infinitely many primes of the form $an+b$
12.12.2010 13:25
I can't prove it,of course
12.12.2010 13:29
spanferkel wrote: Rijul saini wrote: Find all polynomials $P$ with integer coefficients which satisfy the property that, for any relatively prime integers $a$ and $b$, the sequence $\{P (an + b) \}_{n \ge 1}$ contains an infinite number of terms, any two of which are relatively prime. There is no such polynomial. If $P(x)=a_0+a_1x+...+a_mx^m$, take a prime $p$ that divides $a_0+a_1+...+a_m$ and put $a=p,b=1$. Then for all integer $n$, $P(an+b)\equiv P(1)\equiv 0 \pmod p$. Do I understand correct if his solution is correct, but he forgot the cases the sum of co's is $-1,0,1?$
12.12.2010 17:10
sankha012 wrote: every such sequence will contain infinitely many terms...so i think the problem says that there exists infinitely many coprime terms. If so,$P(x)=x$ satisfies the property since Dirichlet's theorem says that there exists infinitely many primes of the form $an+b$ Yeah, his interpretation is correct. The question asks for such a polynomial to have an infinite no. of pairwise coprime terms in those sequences.
12.12.2010 18:22
SCP wrote: spanferkel wrote: Rijul saini wrote: Find all polynomials $P$ with integer coefficients which satisfy the property that, for any relatively prime integers $a$ and $b$, the sequence $\{P (an + b) \}_{n \ge 1}$ contains an infinite number of terms, any two of which are relatively prime. There is no such polynomial. If $P(x)=a_0+a_1x+...+a_mx^m$, take a prime $p$ that divides $a_0+a_1+...+a_m$ and put $a=p,b=1$. Then for all integer $n$, $P(an+b)\equiv P(1)\equiv 0 \pmod p$. Do I understand correct if his solution is correct, but he forgot the cases the sum of co's is $-1,0,1?$ Yes you are right. When the sum of co's is $-1$ or $1$, there is no such $p$. I missed that. (Note that on the other hand, if the sum is $0$, any $p$ will do.) And I see that all polynomials $P(x)=\pm x^k$ for $k\in\mathbb N$ are OK by Dirichlet's theorem too. It seems to me these are the only ones. OK, I'll try a different proof for that: Take a polynomial $P(x)=a_0+a_1x+...+a_mx^m$, such that not all of $a_0,a_1,...,a_{m-1}$ are $0$. We can assume $gcd(a_0,a_1,...,a_{m})=1.$ Then we can choose $b$ such that $f(b)$ is not a power of $b$ and that there is a prime $p|f(b)$ with $(p,b)=1$. Then $f(pn+b)\equiv f(b)\equiv 0\pmod p$. Hope this is correct now.
14.12.2010 14:39
can anyone give a solution without using Dirichlet's Theorem?
14.12.2010 19:54
sankha012 wrote: can anyone give a solution without using Dirichlet's Theorem? It only remains to show that $f(x)=x$ has the property. We have to show that for $(a,b)=1$ there is an infinite subset of $S:=a\mathbb {N}+b$ of pairwise coprime numbers. Easy by induction: Start for example with $n_1=b+1$. If $n_1,...,n_k\in \mathbb N$ such that $(b,n_i)=1$ for all $i$ and $c_1,...,c_k\in S$ (where $c_i=an_i+b$) are pairwise coprime, we have $(c_i,b)=1$. Take $n_{k+1}=c_1\cdots c_k$.
15.12.2010 05:02
thnx...this proof is easier