3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @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) $\endgroup$ – liaombro May 25 at 15:50
2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

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

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


$\endgroup$
  • 1
    $\begingroup$ 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)$ $\endgroup$ – liaombro May 25 at 16:12
  • 3
    $\begingroup$ 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. $\endgroup$ – liaombro May 25 at 16:17
  • 2
    $\begingroup$ But you wrote "Thus m=1 is a counter-example". If it's not, how do you support that statement "... doesn't require ..."? $\endgroup$ – liaombro May 25 at 16:25
  • 2
    $\begingroup$ @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)$ $\endgroup$ – Mike May 25 at 16:42
  • 2
    $\begingroup$ @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 $\endgroup$ – Mike May 25 at 16:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.