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$.

Question

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?

Answer 1

$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.

Answer 2

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<r_3<107$, 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$.

---

Answer 3

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.

Answer 4

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.