Find all Arithmetic progressions $a_{1},a_{2},...$ of natural numbers for which there exists natural number $N>1$ such that for every $k\in \mathbb{N}$: $a_{1}a_{2}...a_{k}\mid a_{N+1}a_{N+2}...a_{N+k}$
Problem
Source: Iran TST 2013:TST 2,Day 1,Problem 2
Tags: modular arithmetic, number theory, greatest common divisor, number theory proposed
24.04.2013 14:45
it is actually a beautiful number theory problem, my soloution: let $ K>N $ and let $ t=a_{1}a_{2}...a_{N} $ and let $ a_{i}=ia+b $ where $ \gcd(a,b)=1$ (we can take out the greatest common divisor w.l.o.g) then we have $ t\mid a_{k+1}a_{k+2}...a_{N+k} $ for every natural $K>N$ so if $a>0$ $ t\mid ((k+1)a+b)((k+2)a+b)...((N+k)a+b) , \gcd(a_{i},a)=1 \Rightarrow \gcd(t,a)=1 \Rightarrow \exists c : ac \equiv 1 \pmod{t} $ $ ((k+1)+bc)((k+2)+bc)...((N+k)+bc)a^N \equiv ((k+1)a+b)((k+2)a+b)...((N+k)a+b) \pmod{t} $ now put $k=st-bc $ for a big $s$ then $ ((k+1)+bc)((k+2)+bc)...((N+k)+bc)a^N \equiv N!a^N \equiv 0 \pmod{t} $ $ t \mid N!a^N \Rightarrow N!a^N \leq t \leq N!a^N \Rightarrow b=0 $
24.04.2013 16:40
mlm95 wrote: Find all Arithmetic progressions $a_{1},a_{2},...$ of natural numbers for which there exists natural number $N>1$ such that for every $k\in \mathbb{N}$: $a_{1}a_{2}...a_{k}\mid a_{N+1}a_{N+2}...a_{N+k}$ Edit : wrong sol
24.04.2013 21:05
subham1729 wrote: $a+xd|N+y-x$ since we can take $(a,d)=1$ then, $N>N+y-x\geq a+xd$ ,but as there are are infinitely many such $x$ so it's absurd, now so we must have $d=0$ so that we can't apply dirichlet. what if $ x=N+y $ by the way $a,2a,3a,... $ is a soloution of the problem because $N! \mid (k+1)(k+2)...(k+N) $
26.04.2013 20:25
sco0orpiOn wrote: It is actually a beautiful number theory problem A very beautiful one ! Beside the trivial solutions, I mean $a_n = nx$, all constant AP are also fit into statement. So as one can see, you miss the case that $a$ vanish . proposed by Yahya Motevassel
26.04.2013 21:44
Quote: A very beautiful one ! Beside the trivial solutions, I mean , all constant AP are also fit into statement. So as one can see, you miss the case that vanish . proposed by Yahya Motevassel yes you were right but i seperate the case when $a>0$ and $a=0$ when $ a>0 ,a_{n}=na $ and when $a=0,a_{n}$ is constant
27.04.2013 00:13
Let $a_n=a_0+nd$. If $a_0=0$ or $d=0$ then $(a_n)$ fits all conditions. Now let $a_0\cdot d\neq 0$ and WLOG let $(a_0,d)=1$. Note that for $k>N$ we will have \[M=a_1\cdot a_2\cdots a_N\mid a_{k+1}\cdot a_{k+2}\cdots a_{k+N}=R\] Note that $M>N!$ therefore there must exist prime $p$ with $v_p(M)>v_p(N!)$. So if we on the start take such $k$ for which $p^{v_p(M)}\mid M\mid a_0+dk$ then we will have $R\equiv d^NN! \mod p^{v_p(M)}$ which is contradiction.
25.03.2018 20:45
Let $a_n=a_0+nr$ and suppose $wlog$ $gcd(a_0,r)=1$ we have $gcd(a_i,a_j)=gcd(a_0+ir,a_0+jr)=gcd(a_0+ir,(i-j)r)$ and since $gcd(a_0,r)=1$ we get that $gcd(a_i,a_j)=gcd(a0+ir,(i-j))$ thus , $gcd(a_i,a_j)$ is lower or equal to $i-j$ $a_i|(N-i)*...*(N-i+k)$ since $a_i|a_{k+1}*...*a_{k+N}$ and $gcd(a_i,a_j) | (i-j)$ using the fact that $gcd(a_i,a_j) | (i-j)$ again we get that $a_1*...*a_k|N!*(k+N)!$ since $N$ is fixed , when k goes to infinity we have $N!*(k+N)! \leq r^k*k! \leq a_1*a_2*...*a_k$ if $ r>1$ thus , $r=0$ which makes the arithmetic progression constant $or$ $r=1$ which leads to $a_0=0$ easily
30.08.2021 20:51
The only solutions include $a_N=n^2 \text{ for some } n \in \mathbb{N}$ Write $a_n=a+nd$ for some integer $n \ge 1$ and some $d \ge 1$ Assume that $\gcd(a,d)=1$(since if not then dividing by their greatest common divisor will make things fine) By the condition,$a_{1}a_{2}...a_{N}\mid a_{N+1}a_{N+2}...a_{N+k}$,since $a_1 a_2......... a_N>N!$,choose an positive prime $p$ such that $\nu_p(a_1........a_N)>\nu_p(N!)$ By construction,$p$ must divide one of $a_1,a_2,.........,a_N$ Since $p \nmid d$ by the previous sentence,there must exist an integer $k$ by CRT such that $dk \equiv -a \pmod {p^{v_p(a_1 a_2..........a_N)}}$ hence $\nu_p(N!)<\nu_p(a_1........a_N) \le \nu_p(a_{k_1}........a_{k+N})=\nu_p(a_k+d)+\nu_p(a_k+2d).........=\nu_p(d)+\nu_p(2d)+.............=\nu_p(N!)$,a contradiction.
25.01.2022 00:38
My answer is the arithmetic progressions such that $a_i=ik$ with $k$ be a fixed positive integer and the constant sequence. First we can write $a_i=(i-1)u+v$. Suppose that $u$ is positive, WLOG $(u,v)=1$ Well we just have to prove this: Key Claim: $a_1a_2\dots a_N \mid N!u^N$ Proof: in the original problem take $k=N+r$, let the polynomial $P(x)=((N+x)u+v)((N+x+1)u+v)(\dots)((2N+x-1)u+v)$, then : $$a_{1}a_{2}\dots a_{N+r}\mid a_{N+1}a_{N+2}\dots a_{2N+r} \implies a_1\dots a_N \mid a_{N+r+1}\dots a_{2N+r}=P(r)$$So applying finite differences the main term of $P(x)$ is $u^{N}x^{N}$ so the last finite difference is $N!u^N$, this implies the claim. $\square$ But we have that $(u,v)=1$ the $(a_i,u)=1$ so $a_1a_2\dots a_N \mid N!$, but $a_i \ge i$ then equality occurs so $a_i=i$ Finally when $u$ is positive and $(u,v)=1$ we have $a_i=i$ this implies that $a_i=it$ with $t$ fixed if $u$ is positive (not necessarily $(u,v)=1$), if $u=0$ we have $a_i=k$ with $k$ fixed. And that's the answer
13.10.2023 18:36