For a given positive integer $n$ and prime number $p$, find the minimum value of positive integer $m$ that satisfies the following property: for any polynomial $$f(x)=(x+a_1)(x+a_2)\ldots(x+a_n)$$($a_1,a_2,\ldots,a_n$ are positive integers), and for any non-negative integer $k$, there exists a non-negative integer $k'$ such that $$v_p(f(k))<v_p(f(k'))\leq v_p(f(k))+m.$$Note: for non-zero integer $N$,$v_p(N)$ is the largest non-zero integer $t$ that satisfies $p^t\mid N$.
Problem
Source: 2017 China TSTST 1 Day 2 Problem 6
Tags: number theory, Polynomials, prime numbers, algebra, polynomial
17.03.2017 20:35
That is not right. The answer should be $n + v_p(n!)$.
17.03.2017 22:47
Can anyone solve this problem?
23.03.2017 17:54
I've seen the expression $n+v_p(n!)$ once too many times for this expression to just be a coincidental result, especially in China TST problems... am I just crazy?
25.03.2017 17:05
i solved this like this: step 1: first set a claim about n<=t and say you are gonna prove it for n=t+1 (i am talking about induction) step 2: prove that if a1~a(t+1) isn't all same for mod p, it is smaller than n+vp(n) step 3: so you get a1~a(t+1) is all same as (p-a) for mod p (0<=a<p) --> you get vp(f(x))=0 or else step 4: let x=a+py --> you can set y to be s (mod p) where s is least most number (mod p) among (a(i)+a)/p step 5: set algorithym for step 2~4 same to use it for y and (a(i)+a)/p
07.04.2017 05:56
How to guess the number n+vp(n!)??? Oh my god ??
07.04.2017 06:24
Let ai =pi we get m >= n +vp(n!)
07.04.2017 07:51
My solution Let ai =pi and chose k isnot divided by p So k' is divided by p . $k'=py$ and $v_p(f(k)) = n+(y+1)(y+2).......(y+n) >= n+v_p(n!)$ => $m >= n+v_p(n!)$ We will prove by induction Lemma Let $b_1 ; b_2 ; ................ ; b_n$ are n positive interger number then there exist k such that $ v_p(b_1+k)(b_2+k).................(b_n+k) <= v_p(n!)$ Prove the lemma by induction n = 1 suppose that 1<=k<=n-1 are true suppose with n are false take k=0 $v_p(b_1.b_2.............b_n)>=v_p(n!)$ suppose $b_{i1} ; b_{i2}.........................; b_{im}$ are divided by p if m = n take k=1 if m < n by induction there exist k such that $v_p(b_{i1}+k) (b_{i2}+k).........................(b_{im}+k)<= v_p(m!)$ => $m + v_p(m!)>v_p(n!)$ => m> n/p take k from 0 to p-1 => contraction Suppose f(k) is divided by p $(k+a_1)(k+a_2).................(k+a_n)$ is divide by p suppose $a_{i1}+k ; a_{i2}+k ......... a_{im}+k$ is divided by p Lett max $v_p(a_i+k)=t$ supose $a_{ji} = p^t.b_j$ i = 1 to q chose k' = p^t.z+k such that max $v_p(z+b_j)=1$ if f(k) is not divided by p $(k+a_1)(k+a_2).............(k+a_n)$ is not divided by p take $a_{i1};a_{i2} ............a_{im}$ is the longest sequence are congruent mod p so by induction we have QED so take $a_i = b_i.p-q$ take k' = kp+q use the lemma we have QED
07.04.2017 07:56
Wonderful
24.10.2017 15:35
Umm, sorry, but I can't understand when f(k) is divided by p. if we chose k' like that, then why it satisfy the condition of the problem? I think the point of that case is Vp(f(k'))>Vp(f(k)). I proved Vp(f(k'))≤Vp(f(k))+m but I can't proof that only Vp(f(k'))≥Vp(f(k)).
27.10.2017 11:26
@above because $v_p(k'+a_i) >= v_p(k+a_i)$ => $v_p(f(k')) > v_p(f(k))$
27.10.2017 13:22
Ohh, thanks.
30.10.2017 13:26
Pikachu05072001 wrote: @above because $v_p(k'+a_i) >= v_p(k+a_i)$ => $v_p(f(k')) > v_p(f(k))$ I think, you had been mistake. a_ji is not p^t.b_j but a_ji +k. If then, you may change k' = p^t.z +k. Then, by lemma there's z such that Vp(f(k'))≤Vp(f(k))+v_p(m!). But, we don't know the lower bound because $ v_p(b_1+k)(b_2+k).................(b_n+k) is could 0. (k is z, in this case) So we can't solve with your ways. I proved this case using the second case. If we suppose k' like that, our claim is change to second case with k=0. Because q<=n, the proof is complete. It's easy. If I wrong?
18.03.2018 13:54
Very nice problem. I add my solution. The answer is $\boxed{n+\nu_p(n!)}$. To show that $m\ge n+\nu_p(n!)$ is necessary (which is the important motivation), take $$f(x)=(x+p)(x+2p)...(x+np).$$and $k=1$. It's easy to see that whenever $p$ divides $f(k')$ then $p\mid k'$. Letting $k' = pr$, we notices that $$f(k') = p^n(r+1)(r+2)...(r+n)\implies p^nn!\mid f(k')$$so $m\ge n+\nu_p(n!)$ as desired. Now we show that $m=n+\nu_p(n!)$ works. We first prove the following lemma which is a special case of this problem. Lemma : Let $n,a_1, a_2,...,a_n\in\mathbb{Z}^+$ then there exists a positive integer $x$ such that the quantity $$f(x)=(x+a_1)(x+a_2)...(x+a_n)$$is divisible by $p$ but not $p^{n+\nu_p(n!)+1}$. Proof : We claim that we can pick $x\pmod{p^i}$ so that $p^i$ divides at most $\left\lfloor\frac{n}{p^{i-1}}\right\rfloor$ by induction on $i$. The base case $i=1$ is clear. (Note that we can even pick $x\equiv -a_1\pmod p$.) Suppose that we have picked $x\pmod{p^{i-1}}$. Let $x+b_1, x+b_2,...,x+b_k$ be those which is divisible by $p^{i-1}$ where $k\le \left\lfloor\frac{n}{p^{i-2}}\right\rfloor$. By pigeonhole, there exists residue class $y\pmod p$ which contains at most $\left\lfloor\frac{k}{p}\right\rfloor = \left\lfloor\frac{n}{p^{i-1}}\right\rfloor$ of numbers $$\frac{x+b_1}{p^{i-1}}, \frac{x+b_2}{p^{i-1}},...,\frac{x+b_k}{p^{i-1}}$$hence picking $x\pmod{p^i} = yp^{i-1}+x $ satisfies inductive condition. This process repeats until there are no terms divisible by $p^i$ so $$\nu_p(f(x)) \le n + \left\lfloor\frac{n}{p}\right\rfloor + \left\lfloor\frac{n}{p^2}\right\rfloor + ... = n+\nu_p(n!)$$hence we are done. $\blacksquare$ Back to the main problem. Fix any $k\in\mathbb{Z}^+$ and let $c_i = \nu_p(x+a_i)$. WLOG $c_1\ge c_2\ge ...\ge c_n$. By suitable translation we can assume that $a_1=0$. Pick $k'=p^{c_1}r$ for suitable $r$. We see that $$f(k') = p^{\nu_p(f(k))}\cdot r\left(p^{c_1-c_2}\cdot r + \frac{a_2}{p^{c_2}}\right)\left(p^{c_1-c_3}\cdot r + \frac{a_3}{p^{c_3}}\right)...\left(p^{c_1-c_n}\cdot r + \frac{a_n}{p^{c_n}}\right)$$Note that if $c_1>c_i$ for some $i$, then $p^{c_j} \| a_j$ for any $j\ge i$ so the later $n-i+1$ brackets never divisible by $p$. Thus we can ignore them and induct down on $n$. Otherwise, $c_1=c_2=...=c_n = c$ which implies $$f(k') = p^{\nu_p(f(k)) } \cdot r\left( r + \frac{a_2}{p^{c}}\right)\left( r + \frac{a_3}{p^{c}}\right)...\left( r + \frac{a_n}{p^{c}}\right)$$By lemma, we can pick $r$ so that $\nu_p$ of the right product is not exceed $n+\nu_p(n!)$ and greater than $0$ hence we are done.
18.03.2018 20:41
Is there any $p$-adic interpretation of this problem?