Let p be a prime number and f∈Z[X] given by f(x)=ap−1xp−2+ap−2xp−3+⋯+a2x+a1,where ai=(ip) is the Legendre symbol of i with respect to p (i.e. ai=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 whenp=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 2so that (x-1)||f(x)