# Let $m,n\in \mathbb{Z}$ and $p(x)=x^3+mx+n$ be such that if $107\mid p(x)-p(y)\implies 107\mid x-y$. Prove that $107\mid m$.

Let $$m,n\in \mathbb{Z}$$ and $$p(x)=x^3+mx+n$$ be such that for an integers $$x,y$$ we have: $$107\mid p(x)-p(y)\implies 107\mid x-y$$ Prove that $$107\mid m$$.

I'm not sure what to do here. I can only deduce that $$107\nmid x^2+xy+y^2+m$$

and since $$x\equiv y \pmod {107}$$ $$107\nmid 3x^2+m$$ Suppose $$107\nmid m$$ then expressing this with Legendre symbol we have $$\Big({-3m\over 107}\Big)=-1$$ Any sugestion?

$$p(x)-p(y)=x^3-y^3+m(x-y)=(x-y)(x^2 + xy + y^2+m)$$

The condition is $$x^2+xy+y^2 +m \not \equiv 0 \pmod{107}, \quad when \quad x\not\equiv y \pmod{107}$$

Setting $$y=0$$ we get $$x^2 + m \not \equiv 0 \quad when \quad x\not\equiv 0$$

Since $$-1$$ is quadratic nonresidue modulo 107 (because $$(-1)^{53}\equiv -1$$), we have that $$m \text{ is quadratic residue modulo 107}$$

Let $$m\equiv a^2 \not \equiv 0 \pmod{107}$$

Note Below I will write $$\frac{1}{y}$$ to mean some integer number such that $$y\cdot \frac{1}{y}\equiv 1 \pmod{107}$$. Such a number exists iff $$y\not\equiv 0$$. And $$\frac{x}{y}$$ means $$x\cdot \frac{1}{y}$$.

Rewrite the condition in the form $$x^2 + xy+ y^2 \not\equiv-a^2$$ $$\forall b\not\equiv 0 \quad (\frac{x}{y})^2 + \frac{x}{y} +1 \not\equiv -b^2$$ $$\forall b\not\equiv 0 \quad \lambda ^2 + \lambda + 1 \not \equiv -b^2$$

Plugging in $$\lambda=2$$ yields $$7$$, which is a quadratic non residue modulo 107.

That means that $$2^2 + 2 +1 \equiv -b^2$$ for some $$b$$, multiply that by $$\frac{a^2}{b^2}$$ to get $$\frac{\lambda^2 a^2}{b^2} + \lambda \frac{a^2}{b^2} + \frac{a^2}{b^2} \equiv -a^2$$ that is $$(\frac{\lambda a}{b})^2 + \frac{\lambda a}{b} \frac{a}{b} + (\frac{a}{b})^2 \equiv -a^2$$ since $$\lambda = 2 \not \equiv 1$$, we have a pair $$x=\frac{2 a}{b}$$ and $$y=\frac{a}{b}$$ contradicting the condition.

• @MariaMazur $x^2 = -m$ has no solutions. $-1$ is a quadratic nonresidue. If m was a q. nonresidue, then there would be solutions. (Because q. nonresidue times q. nonresidue is a q. residue, that is a well-known fact) – liaombro May 25 at 15:50

I think people are getting confused on the if-then here. I will restate the problem:

Problem 1 [restated] Let $$p(x) = x^3+mx$$ such that $$107 \not | m$$. Then prove or disprove the following: There exists an $$x,y$$ such that both conditions $$x \not \equiv_{107} y$$ and $$p(x)-p(y) \equiv_{107} 0$$ simultaneously hold.

So now we solve Problem 1 by proving the above statement.

Case 1: $$-m$$ a nonzero square mod 107. Let us first pick $$y$$ to be a multiple of 107. Then it suffices to show that $$-m$$ a nonzero square modulo 107 implies the existence of at least one nonegative integer $$a < 107$$ s.t. $$p(y)-p(y-a)$$ is a multiple of 107. However:

$$p(y)-p(x) = (y-x)(x^2+xy+y^2) + (y-x)m \equiv_{107} a(a^2) +am$$

so as long as $$-m$$ is a nonzero square modulo 107 there indeed exists such an $$a$$; namely $$a$$ satisfying $$a^2=-m$$. Thus, as long as $$y \equiv_{107} 0$$ and $$x=ka$$, it will follow that $$m|p(y)-p(x)$$. Then $$p(y)-p(x)$$; $$y \equiv_{107} 0$$ and $$x \equiv_{107} -a$$; $$a$$ as specified, will satisfy $$107|p(y)-p(x)$$ but $$107 \not | y-x$$

Case 2: $$-m$$ a nonzero nonsquare mod 107. Now let us pick $$y \equiv_{107} a$$ [for some positive integer $$a$$ less than 107] and $$x \equiv_{107} ka$$ for some $$k \not = 1$$ such that (A) $$1+k+k^2$$ is a nonzero non-square mod 107. [As in, we first set $$k \not =1$$ to meet (A) and then we find $$a$$ after. We show below the existence of such a $$k$$ [Claim 2].] So let us now assume the existence of such a $$k$$. Then:

$$p(y)-p(x) = (y-x)(x^2+xy+y^2) + (y-x)m \equiv_{107} (y-x)(1+k+k^2)(a^2) +(y-x)m$$

Then as $$(1+k+k^2)$$ is a nonzero nonsquare then for any nonzero nonsquare $$-m$$ there is a nonzero $$a$$ such that $$(1_k+k^2)a^2+m \equiv_{107} 0$$. Then $$p(y)-p(x)$$; $$y \equiv_{107} a$$ and $$x \equiv_{107} ka$$; $$k$$ and $$a$$ as specified, will satisfy $$107|p(y)-p(x)$$ but $$107 \not | y-x$$.

As $$-m$$ is either a nonzero square or nonsquare mod 107, the above gives a proof for Problem 1, modulo Claim 2 below.

Claim 2: There exists a $$k \not = 1$$ s.t. $$q(k) \doteq 1+k+k^2$$ is a nonsquare mod 107.

Note that $$q(-5) = 21$$ and 21 is a nonsquare mod 107.

Suppose $$107\nmid m$$.

Let $$d=x-y$$, then for all $$y$$ and $$d$$ we have:

if $$107\nmid d$$ then $$107\nmid d^2+3dy+3y^2+m$$

So:

• if we put $$y= -d$$ we get $$107\nmid d^2+m\implies \Big({-m\over 107}\Big) =-1$$
• if we put $$y= d$$ we get $$107\nmid 7d^2+m\implies \Big({-7m\over 107}\Big) =-1$$

Thus $$-1=\Big({-7m\over 107}\Big) =\Big({7\over 107}\Big)\Big({-m\over 107}\Big) =-\Big({7\over 107}\Big)$$

so $$\Big({7\over 107}\Big) =1$$

Thus, by quadratic reciprocity we have: $$\Big({107\over 7}\Big)=(-1)^{{107-1\over 2}{7-1\over 2}}=-1$$ But $$107 \equiv 9 =3^2 \pmod 7$$ A contradiction.

• I'm not sure if this is now OK. Would you please check? @Mike – Aqua May 26 at 12:43
• Looks perfectly fine – liaombro May 26 at 13:03

Given $$A \Rightarrow B \iff \overline{B} \Rightarrow \overline{A}$$, we are looking for $$107 \nmid x-y \Rightarrow 107 \nmid p(x)-p(y)$$ or $$107 \nmid x^2+xy+y^2+m$$ because $$p(x)-p(y)=(x-y)(x^2+xy+y^2+m)$$. Given $$x=107k_1+r_1, 0\leq r_1 < 107$$ $$y=107k_2+r_2, 0\leq r_2 < 107$$ then $$x^2+xy+y^2+m=107Q+r_1^2+r_1r_2+r_2^2+m$$ Obviously $$r_1$$ and $$r_2$$ can't be $$0$$ at the same time (because of $$107 \nmid x-y$$). Easy to check with a Python code (run here)

arr = []
for r1 in range(0, 107):
for r2 in range(0, 107):
if (r1!=0 or r2!=0):
rest = (r1*r1 + r1*r2 + r2*r2) % 107
arr.append(rest)

sorted(arr)
print set(arr)


that $$(r_1^2+r_1r_2+r_2^2) \pmod{107}$$ gives all values from $$1$$ to $$106$$ (never $$0$$) as possible remainders.

As a result, if we assume $$107 \nmid m$$ or $$m=107k_3+r_3, 0, there will be a pair $$x,y$$ such that $$(r_1^2+r_1r_2+r_2^2) \pmod{107} = 107-r_3$$ or $$107 \mid x^2+xy+y^2+m$$ contradiction. So $$m$$ has to be divisible by $$107$$.

• here's a counterexample for your claim about m=1 : take x=19, y=3. $$19^2 + 19\cdot 3+3^2 + 1=428$$ So, $107| p(19)-p(3)$, but $107 \nmid (19-3)$ – liaombro May 25 at 16:12
• You claim that for m=1 $p(x)=x^3 + x$ is an example of such function that $107∣p(x)−p(y)⇒107∣x−y$. That is wrong. – liaombro May 25 at 16:17
• But you wrote "Thus m=1 is a counter-example". If it's not, how do you support that statement "... doesn't require ..."? – liaombro May 25 at 16:25
• @rtybase good effort. But I think people are getting confused on the if-then. I know it tripped me up. If you were looking for a counterexample, you need to find a polynomial $p(x)$ of the form $p(x)=x^3+mx$ for some $m$ satisfying $107 \not | m$; such that for every $x,y$ integers: If $x \not \equiv_{107} y$ then $p(x) \not \equiv_{107} p(y)$. But for $p(x) = x^3+x$ note that $p(19) \equiv_{107} p(3)$ – Mike May 25 at 16:42
• @rtybase indeed it is. But you are asked to find the values of $m$ such that (X) input $107 | p(x) - p(y) \Rightarrow 107|x-y$ is true. Or more precisely, show that the only values of $m$ that satisfy (X) are a multiple of 107, OR find an $m$ that is not a multiple of 107 yet satisfies (X) anyway – Mike May 25 at 16:53