# How to prove $p(z-y)(zy)(z^2-yz+y^2) \mid x^p-(z-y)^p \Rightarrow x=z-y$?

Assume $p>2$ prime and $1<x<y<z$ coprime. How to prove the following: $$p(z-y)(zy)(z^2-yz+y^2) \mid x^p-(z-y)^p \Rightarrow x=z-y$$

I remember it as an extra exercise which I couldn't solve when I was a student. It still bothers me...

I can only proof a partial statement: the case that $p \nmid \phi \big( p(z-y)(zy)(z^2-yz+y^2) \big)$ whereby $\phi(m)=m\displaystyle\prod_{\substack{q \mid m \\ q \ prime}}{(1-\frac{1}{q})}$ is Euler's totient function.

Let $n=p(z-y)(zy)(z^2-yz+y^2)$ and $\text{rad}(n)=\displaystyle\prod_{\substack{p \mid n \\ p \ prime}}{p}$ the radical of $n$.

We know that for $q>2$ prime, $s^k \equiv 1 \pmod{q}$ has $\gcd(k,q-1)$ solutions (See link). Thus for all prime divisors $q>2$ of $n$ with $p \nmid q-1$ the relation $s^p \equiv t^p \pmod{q}$ implies $q \mid s-t$. Stated differently, the map $s \mapsto s^p \pmod{q}$ is injective on $[1 \dots q]$. Also for the case $q=2$.

We conclude that $n \mid x^p-(z-y)^p$ and $p \nmid \phi(n)$ implies $\text{rad}(n) \mid x-(z-y)$. For the last step I must assume that $y<\text{rad}(p(z-y)(zy)(z^2-yz+y^2))$ to ensure that $x,z-y \in [1 \dots \text{rad}(n)]$. This assumption seems obvious but I've never seen any proof of this statement (See question).

Who can help me with the missing parts?

• Can you comment on where this question is coming from? Jul 3, 2015 at 12:19
• The question arose from extra exercises at the University of Groningen around 1977. It was to encourage excellence. I forgot which professor took the initiative. Professor Floris Takens was asked for input but his entry was too difficult for youngsters to understand. Disappointed that his input was rejected, he swiftly came with the above exercise including the request to mention at least one practical application. Because one of the university staff (or foreign friends of Takens) quickly returned a valid concise proof using elementary math, the exercise was accepted. Jul 4, 2015 at 19:44
• Just for the sake of completeness: do you mean that $x,y,z$ are coprime or pairwise coprime? thanks. Oct 2, 2015 at 1:07
• I mean that $x,y,z$ are pairwise coprime. Oct 3, 2015 at 16:03

This is just an approach, rather than an answer.

Let us consider the case $z-y=1$. Then we have $0<x<y$, with $x$ coprime to $y$ and $y+1$ and $$py(y+1)(y^2+y+1)\Big| (x^p-1).$$ In fact, divisibility implies that $x$ is coprime to both $y$ and $y+1$, so we simply have $$py(y+1)(y^2+y+1)\Big| (x^p-1), ~~0<x<y.$$ It is clear we need $p$ to divide $gcd(\phi(y),\phi(y+1),\phi(y^2+y+1))$ or else we can conclude that $x$ is $1$ modulo one of these numbers, so $x=1$ in view of $0<x<y$. We also see that we need $p$ at least $5$, and more likely $7$ or higher.

Computer search certainly finds $y$ and $p$ such that $p$ divide the gcd above, but then it is still a slim chance of finding $x$. So far, a computer search of mine came up empty.

• The case $z-y=1$ seems related to this question. Jul 4, 2015 at 19:53

The following reasoning is derived from exercise 1.19.13 in the excellent book about polynomials with Barbeau. This exercise is based on problem A2 from the 37th Putnam Competition in 1976. All lower case symbols used are representing non-negative integers unless specified differently.

Define $F_n=(x+y)^n-x^n-y^n$, $G_n=(x+y)^n+x^n+y^n$, $P=xy(x+y)$, and $Q=x^2+xy+y^2$. We have: $F_0=-1$, $G_0=3$, $F_1=0$, $G_2=2Q$, $F_3=3P$, $G_4=2Q^2$, $F_5=5PQ$ and $G_6=2Q^3+3P^2$. The polynomials $F_2, F_4,F_6,G_1,G_3$ and $G_5$ can not be written in terms of $P$ and $Q$. By multiplication one can easily verify that $$F_n=QF_{n-2}+PG_{n-3}$$ $$G_n=QG_{n-2}+PF_{n-3}$$ In the first line we can replace $G_{n-3}$ and $F_{n-2}$ $$F_n=Q(QF_{n-4}+PG_{n-5})+P(QG_{n-5}+PF_{n-6})=Q^2F_{n-4}+2PQG_{n-5}+P^2F_{n-6}$$

Thus $F_n \equiv Q^2F_{n-4}+P^2F_{n-6} \pmod{PQ}$. Suppose $n=6k+j$ and $0 \le j < 6$. This replacement can be repeated $k$ times until we end with the term $Q^{2k}F_{n-4k}+P^{2k}F_j$ modulo $PQ$. We conclude that if and only if $j=1,5$ the last term $P^{2k}F_j$ vanishes modulo $PQ$.

Let $n-4k=4m+i$. Note that assuming $j=1,5$ implies $i=1,3$. After $m$ steps we end with the term $Q^{2(k+m)}F_{i}$ modulo $PQ$, and as $F_i \equiv 0 \pmod{P}$ we conclude that if $xy(x+y) \not =0$ $$xy(x+y)(x^2+xy+y^2) \mid (x+y)^n-x^n-y^n \Leftrightarrow n\equiv{1,5} \pmod{6}$$

The next step is to look at non-negative coprime solutions of $$xy(x+y)(x^2+xy+y^2) \mid (x+y)^n-y^n$$ If we assume that $n\equiv{1,5} \pmod{6}$, rewriting yields $(x+y)^n-y^n=F_n+x^n$ and we can use $F_n \equiv 0 \pmod{PQ}$. Thus the problem reduces to solving $$x^n = k*xy(x+y)(x^2+xy+y^2)$$ A solution is $x=0$. Suppose now $x>0$. This implies $y>0$ because $y=0$ is impossible. As $y \mid x^n$, we conclude that prime divisors of $y$ are also prime divisors of $x$. The condition that $x,y$ are coprime implies that the only option is $y=1$. The relation becomes $x^n = k*x(x+1)(x^2+x+1)$ which has no positive solution as both $x,x+1$ are coprime. In total we find that if $n\equiv{1,5} \pmod{6}$, $x=0$ is the only solution.

Now we proof the following statement if $n=1,2,3$ or $n=1,5 \pmod{6}$, and $0<x<y<z$ coprime $$(z-y)(zy)(z^2-yz+y^2) \mid x^n-(z-y)^n \Rightarrow x=z-y$$ A trivial solution is $x=z-y$. Assume $x \not = z-y$ and thus $k \not = 0$ if $x^n-(z-y)^n=k*(z-y)(zy)(z^2-yz+y^2)$. Note that $k$ can be negative.

Case $n=1,2,3$. Suppose $x>z-y$, thus $k>0$. We have $x^n-(z-y)^n=k*(z-y)(zy)(z^2-yz+y^2)> k*(1)(y^2)(y^2-y^2+y^2)= k*y^4$ as $z>y$. Thus $x^n> k*y^4+(z-y)^n$ which implies $y<x \Rightarrow \Leftarrow x<y$.

Now suppose $x<z-y$, thus $k<0$. Note that $y^2-yz+y^2=(z-y)^2+yz$. We have $(z-y)^n-x^n=(-k)*(z-y)(zy)(z^2-yz+y^2)$ $= (-k)*zy(z-y)^3+(-k)*(z-y)(zy)^2$. Thus $(z-y)^n > (-k)*zy(z-y)^3+x^n \Rightarrow \Leftarrow$. In total we conclude that there is only one solution.

Case $n=1,5 \pmod{6}$. Define $t=z-y$ and note that $(z-y)(zy)(z^2-yz+y^2)$ $=ty(y+t)(t^2+ty+y^2)$ which divides $x^n-(z-y)^n=\big((x-(z-y)\big)+t)^n-t^n$. Now we can apply our earlier finding to conclude that $x-(z-y)=0$. QED

A final remark. The question posed has as extra condition that $p$ is a prime larger than 2. It is well-know that for primes $p>3$ we have $p \equiv 1,5 \pmod{6}$, and by Fermat's Little Theorem $p \mid (x+y)^p-x^p-y^p$. Unfortunately, this condition put me on the wrong track for a long time :(