Let $p$ be a prime number and $f\in \mathbb{Z}[X]$ given by \[ f(x) = a_{p-1}x^{p-2} + a_{p-2}x^{p-3} + \cdots + a_2x+ a_1 , \]where $a_i = \left( \tfrac ip\right)$ is the Legendre symbol of $i$ with respect to $p$ (i.e. $a_i=1$ if $ i^{\frac {p-1}2} \equiv 1 \pmod p$ and $a_i=-1$ otherwise, for all $i=1,2,\ldots,p-1$). a) Prove that $f(x)$ is divisible with $(x-1)$, but not with $(x-1)^2$ iff $p \equiv 3 \pmod 4$; b) Prove that if $p\equiv 5 \pmod 8$ then $f(x)$ is divisible with $(x-1)^2$ but not with $(x-1)^3$. Sugested by Calin Popescu.
Problem
Source: Romanian IMO Team Selection Test TST 2004, problem 18
Tags: modular arithmetic, quadratics, number theory proposed, number theory
26.05.2004 19:06
Obviously x-1|p(x) let q(x)=p'(x) r(x)=p''(x) If q(1)=0 (or (x-1)^2|p(x)) we get sum m*(a/m)=0. If p=4k+3 then sum(m)=(p-1)(p-2)/2 is odd, contradiction. If p=4k+1 then (a/p)=1 iff (p-a/p)=1 and residues group in pairs of sum p and the sum is 0. If p=8k+5 q(1)=0 or sum m^2*(m/p)=0. Grouping m with p-m we get (sum 2m^2+sum(p^2-2m))(m/p)=0. The latter sum is 0 by a) so we get sum (m/p)m^2=0 (m=1..(p-1)/2) But sum m62 is odd, contradiction.
26.05.2004 21:23
I didn't understand very well what Iura said, so I apologise if my solution is the same: Part a) is trivial. Let's prove part b). I will prove that $\sum_{i=1}^{p-1}{i^2\cdot(\frac{i}{p})} $ is 4 modulo 8. Note that $\sum_{i=1}^{\frac{p-1}{2}}{(2i)^2\cdot(\frac{2i}{p})}$ is congruent to 4 modulo 8 (just work modulo 2 with $ \sum_{i=1}{\frac{p-1}{2}}{i^2}$ mod 2). Thus, it is enough to prove that $\sum_{i=1}^{\frac{p-1}{2}}{(\frac{2i-1}{p})} $ is 0 mod 8. ( use the fact that $ x^2$ is 1 modulo 8 for any odd x). But this is easy, since we obviously have $\sum_{i=1}^{\frac{p-1}{2}}{(\frac{2i}{p})}+\sum_{i=1}^{\frac{p-1}{2}}{(\frac{2i-1}{p})}=0 $. Now, we also have $\sum_{i=1}^{\frac{p-1}{2}}{(\frac{2i}{p})}=\sum_{i=1}^{\frac{p-3}{2}}{(\frac{2\cdot(\frac{p-3}{2}-i)}{p})+1=1+\sum_{i=1}^{\frac{p-3}{2}}{(\frac{2i+1}{p})}=\sum_{i=1}^{\frac{p-1}{2}}{(\frac{2i-1}{p})} }$. The last two relations solve the problem.
25.01.2012 07:50
what does 'trivial' mean HERE?I've spent 0.5 hours on it! my solution for part 1:we only have to prove $\sum_{i=1}^{p-1}(\frac{i}{p})=0,\sum_{i=1}^{p-1}i(\frac{i}{p})=0$ if and only if $p=2 or p=4k+1$ when$p=4k+3$,then$\sum_{i=1}^{p-1}i(\frac{i}{p})\ne 0$ (that's because $\sum_{i=1}^{p-1}(-1)^{f(i)}(\frac{i}{p})$ is an odd.) when $p=4k+1$,we can pair the $\frac{p-1}{2}$ quadratic residues and non-quadratic ones,so adding up gets 0.
25.01.2012 08:31
Part a is quite trivial It suffices to examine $f(x) \cdot x$. Clearly this does not interfere with divisibility by $x-1$. Thus $f$ denoted below is just $f(x) \cdot x$. $f(1) = \sum_{i=1}^{p-1} \left ( \frac{i}{p} \right ) =0$ clearly. To show $(x-1)^2 \nmid f(x)$, it suffices to show $f'(1) =0$ iff $p \equiv 1 \pmod{4}$ The forward direction is trivial, just pair $i$ with $p-i$. The reverse direction is also trivial, if $p \equiv 3 \pmod{4}$ then we need to show $\sum_{i=1}^{p-1} i \left ( \frac{i}{p} \right ) \not = 0$. The LHS is a sum of $(p-1)/2$ even terms and $(p-1)/2$ odd terms and hence is odd, so we're done. Part b. can be dealt with in a similar fashion. We've already shown $(x-1)^2|P(x)$ so $(x-1)|P'(x)$. Hence we need to show $(x-1) \nmid (xP'(x))'$, or in other words show $\sum_{i=1}^{p-1} i^2 \left ( \frac{i}{p} \right ) \not = 0$. From the fact that for $p=5$ we have the sum is $4$, we are inspired to show the sum is $4 \pmod{8}$. Clearly if we take $\sum_{i=1}^{(p-1)/2} (2i)^2 \left ( \frac{2i}{p} \right )$ then it's $4 \pmod{8}$ because we simply have to show $\sum_{i=1}^{(p-1)/2} i^2 \left ( \frac{2i}{p} \right )$ is odd, which is trivial using above methods. Then we need to show $\sum_{i=1}^{(p-1)/2} (2i-1)^2\left ( \frac{2i-1}{p} \right ) \equiv 0 \pmod{8}$. As $2i - 1$ is odd we know $(2i-1)^2 \equiv 1 \pmod{8}$, hence we have to show $\sum_{i=1}^{(p-1)/2} \left ( \frac{2i-1}{p} \right ) \equiv 0 \pmod{8}$. However, this is easy... $\sum_{i=1}^{(p-1)/2} \left ( \frac{2i-1}{p} \right ) = \sum_{i=1}^{(p-1)/2} \left ( \frac{p-2i+1}{p} \right ) = \sum_{i=1}^{(p-1)/2} \left ( \frac{2i}{p} \right )$ But $\sum_{i=1}^{(p-1)/2} \left ( \frac{2i-1}{p} \right ) + \sum_{i=1}^{(p-1)/2} \left ( \frac{2i}{p} \right ) = 0$, hence they are both 0 and therefore we are done as this implies $\sum_{i=1}^{(p-1)/2} \left ( \frac{2i-1}{p} \right ) \equiv 0 \pmod{8}$.
23.08.2014 17:10
$a)$ We need to prove that $x^1||f(x+1)$ iff $p \equiv 3 \pmod 4$. $f(x+1) \equiv \sum_{i=1}^{p-1} i\left ( \frac{i}{p} \right ) (mod x^2)$. $p \equiv 1 \pmod 4$ then $\sum_{i=1}^{p-1} i\left ( \frac{i}{p} \right ) =0 $ $p \equiv 3 \pmod 4$ then $\sum_{i=1}^{p-1} i\left ( \frac{i}{p} \right ) \equiv \sum_{i=1}^{p-1} i= \frac{p(p-1)}{2} \equiv 1 \pmod 2$. $b)$ We need to prove that $x^2||f(x+1)$,where $p \equiv 5 \pmod 8$. $f(x+1) \equiv \sum_{i=1}^{p-1} i^2\left ( \frac{i}{p} \right )x^2 (mod x^3)$. $ \sum_{i=1}^{p-1}i^2\left ( \frac{i}{p} \right )= \sum_{0<i<p,2|i} i^2\left ( \frac{i}{p} \right )+\sum_{0<i<p,2 \nmid i} i^2\left ( \frac{i}{p} \right ) \equiv 4\sum_{0<i<p,2|i}\frac{i^2}{4}\left ( \frac{i}{p} \right )+\sum_{0<i<p,2 \nmid i}i^2\left ( \frac{i}{p} \right ) \equiv 4+\sum_{0<i<p,2 \nmid i}i^2\left ( \frac{i}{p} \right )\equiv4+\sum_{0<i<p,2 \nmid i} \left ( \frac{i}{p} \right )\equiv 4\pmod 8$.
20.11.2022 05:17
Valentin Vornicu wrote: Let $p$ be a prime number and $f\in \mathbb{Z}[X]$ given by \[ f(x) = a_{p-1}x^{p-2} + a_{p-2}x^{p-3} + \cdots + a_2x+ a_1 , \]where $a_i = \left( \tfrac ip\right)$ is the Legendre symbol of $i$ with respect to $p$ (i.e. $a_i=1$ if $ i^{\frac {p-1}2} \equiv 1 \pmod p$ and $a_i=-1$ otherwise, for all $i=1,2,\ldots,p-1$). a) Prove that $f(x)$ is divisible with $(x-1)$, but not with $(x-1)^2$ iff $p \equiv 3 \pmod 4$; b) Prove that if $p\equiv 5 \pmod 8$ then $f(x)$ is divisible with $(x-1)^2$ but not with $(x-1)^3$. Sugested by Calin Popescu. a As $f(1)=\sum\limits_{i=1}^{p-1}\left(\frac{i}{p}\right)=0$, and $$f'(1) =\sum\limits_{i=1}^{p-1}(i-1)\left(\frac{i}{p}\right) =\sum\limits_{i=1}^{p-1}i\left(\frac{i}{p}\right) =\sum\limits_{i=1}^{p-1}(p-i)\left(\frac{p-i}{p}\right) =(-1)^{\frac{p-1}{2}}\sum\limits_{i=1}^{p-1}(p-i)\left(\frac{i}{p}\right) =-(-1)^{\frac{p-1}{2}}f'(1)$$For $p\equiv 1\pmod 4$, we have $f'(1)=0$ and $(x-1)^2|f(x)$ For $p\equiv 3\pmod 4$, we have $$f'(1)=\sum\limits_{i=1}^{p-1}i\left(\frac{i}{p}\right)\equiv\sum\limits_{i=1}^{p-1}i=\frac{p}{p-1}\equiv 1\pmod 2$$so that $(x-1)||f(x)$