i) Find all infinite arithmetic progressions formed with positive integers such that there exists a number $N \in \mathbb{N}$, such that for any prime $p$, $p > N$, the $p$-th term of the progression is also prime. ii) Find all polynomials $f(X) \in \mathbb{Z}[X]$, such that there exist $N \in \mathbb{N}$, such that for any prime $p$, $p > N$, $| f(p) |$ is also prime. Dan Schwarz
Problem
Source: Romanian TST 4 2007, Problem 4
Tags: algebra, polynomial, modular arithmetic, induction, number theory proposed, number theory
23.05.2007 21:14
Valentin Vornicu wrote: i) Find all infinite arithmetic progressions formed with positive integers such that there exists a number $N \in \mathbb{N}$, such that for any prime $p$, $p > N$, the $p$-th term of the progression is also prime. Answer $p,p,...$ or $1,2,...$, here $p$ is a prime. Assume that $a,a+d,a+2d,...$ is that arithmetic progressions, here $a\in\mathbb{N}$ and $d\in\mathbb{N}_{0}$. If $d=0$ we have $p,p,...$. If $d\geq 1$. we will prove that $a=d=1$. If $a>1$, assume that $q$ is a prime such that $q|a$, then we have infinite primes $P$ such that $P\equiv 1\pmod{q}$ and $a+(P-1)d\equiv 0\pmod{q}$, contradiction, so $a=1$. If $d>1$, assume that $q$ is a prime such that $d\not\equiv 1\pmod{q}$ and $\gcd (d,q)=1$. Choose $k\in\mathbb{N}$ satisfy $kd\equiv-1\pmod{q}$. Then because $\gcd (k+1,q)=1$ therefore we have infinite primes $P$ such that $P\equiv k+1\pmod{q}$, now $1+(P-1)d\equiv 1+kd\equiv 0\pmod{q}$, contradiction. And we're done.
23.05.2007 21:21
Here is a proof using Dirichlet's theorem... the difficulty of this problem depends only on the possibility to use it. Obviously if $f(x) = x$, then f is ok. Suppose $f \neq x$. Take some prime $p > N$ such that $f(p) = q \neq p$ and q is prime. Then p,q are coprime, and by Dirichlet's theorem, there exists a prime $p'$ such that $p' \equiv p \pmod q$. But then $q | f(p')$, this forces $f(p') =q$. Always by Dirichlet's, we can take infinity primes like p', and we have $f(p') = q$ at infinite points, what forces $f$ to be constant. Therefore the only solutions are $f(x) = x$, $f(x) = c$ where c is prime, of course.
23.05.2007 21:31
But i see that $f\equiv-x$ so is an answer.
23.05.2007 21:46
Ok, I just forgot the modulus sign... sorry
23.05.2007 22:42
edriv wrote: Ok, I just forgot the modulus sign... sorry You are right! P/S: Now AC Milan 1-0 Liverpool, Congrulation
23.05.2007 23:57
$2-1 \neq 1$, but $2-1$ means Milan has won!!
23.03.2013 17:01
$i)$ Suppose $nth$ term be $T_n=a+r(n-1)$ now $T_p$ is prime for a prime $p$ now define a sequence $p_n$ by $p_n=T_{p_{n-1}}$ and $p_0=$ , easy induction gives $p_n=(a-r)\frac {r^n-1}{r-1}+pr^n$ now if $a=1$ then $T_n=n$ otherwise take $p>N,r$ and then $p|p_{p-1}$ a contra. So $T_n=n$ is only solution. $ii)$ First I'll show set of prime divisors of $|f(n)|$ is infinite. To show $f$ has infinitely many prime divisors let max number of prime divisors of $f$ is $k$ and for $f(n)$.Let $f(n)=\prod_{i=1}^{k} p_i^{x_i}$ consider the numbers $f(n+\prod_{i=1}^{k} p_i^{x_i+r}=m_r)$ for all $r\in\mathbb N$ So clearly $\prod_{i=1}^{k} p_i^{x_i+r}|f(m_r)-\prod_{i=1}^{k} p_i^{x_i}$. Now obviously $f(m)$ also shares same prime divisors. Now letting $P(m)=\prod p_i^{y_i}$ we must have now $min(x_i,y_i)> x_i$ absurd so they must be equal.Hence $f(m_r)$ is constant for all $r\in\mathbb N$ which implies $f(x)$ is constant. Now if $f(0)=0$ then taking $f(x)=xg(x)$ we get $g(x)=\pm 1$ for infinitely many prime $x$ and that implies $f(x)=\pm x$ for all $x$. Now for other case take prime $p>N,q$ such that $(q,f(0))=1$ and $q|f(n)\implies f(n+qk)$ now so by dirichlet there are infinitely many prime $p'$ such that $q|f(p')$ now also $q|f(p)$ but as $|f(p)|$ is prime so $f(p)=\pm q$ but it's absurd.So $f(x)=\pmx$ or constant.