# Prove that $x^{13}-y^{14}-x+y$ is divisble by $157$.

Natural numbers $$x,y$$ are such that $$x^{12}-y^{13}$$ is divisible by $$157$$. Prove that $$x^{13}-y^{14}-x+y$$ is also divisble by $$157$$.

Off the cuff I tried to multiply first expression by some quantities to get to the $$x^{13}-y^{14}-x+y$$, but that would demand from $$x^{12}-y^{13}$$ to contain $$\pm 1$$ to obtain terms $$x$$ or $$y$$.

The key fact to me seems that $$157$$ is prime and can be expressed as $$12 \times 13 +1$$.

I checked by hand, in search of patterns, few cases in more general statement $$n^2+n+1|x^n-y^{n+1} \rightarrow n^2+n+1|x^{n+1}-y^{n+2}-x+y$$ and for $$n=1,2$$ it seems true.

• Good idea! Fermat's little theorem might help! Feb 6 at 17:07
• @Peter Thank you for correction Feb 6 at 17:17
• @Peter Crossed my mind! But I'm mainly interested in very elementary solution since the problem is dedicated to middle/ high schoolers Feb 6 at 17:35

It’s true if $$x$$ or $$y$$ is 0 mod 157, so we can assume both $$x$$ and $$y$$ are invertible mod 157. By the key fact you identified, along with the fundamental theorem of finite abelian groups, the group $$k^*$$ of units in the field $$k=\mathbf{Z}/157\mathbf Z$$ is naturally the direct product of a cyclic group $$H$$ of order 12 and a cyclic group $$K$$ of order 13. But $$H$$ consists of the 13th powers in $$k^*$$, and $$K$$ of the 12th powers, so $$x^{12}$$ is in $$K$$, and $$y^{13}$$ is in $$H$$. But $$H\cap K = \{1\}$$, so we must have $$x^{12}= y^{13}=1$$ mod 157.

In particular, both $$x^{13}-x$$ and $$y^{14}-y$$ are zero mod 157 and you’re done.

$$\!\bmod \color{#90f}{p\!=\!n^2\!+\!n\!+\!1}\!:\ \left[y^{\color{#0a0}{n+1}}\equiv x^{\color{#c00}n}\right]^{\color{#c00}{n+1}}\!\!\Rightarrow y^{\color{#0a0}{n+1}}\equiv \color{#c00}1\Rightarrow x^{n}\,\equiv\, 1\,$$ by lil Fermat, for $$\,x,y\not\equiv 0,\,$$ by

\!\!\begin{align} \text{ expt arithmetic: }\bmod p\!-\!1\!:\ &\color{#c00}{n(n\!+\!1)} = p\!-\!1\equiv \color{#c00}0,\ \ \ {\rm so}\ \ x^{\color{#c00}{n(n+1)}}\equiv x^{\color{#c00}0}\equiv \color{#c00}1\\[.2em] \underset{{\rm add}\ \color{#0a0}{n+1}}\Longrightarrow\, &(\color{#0a0}{n\!+\!1})(\color{#c00}{n\!+\!1})\equiv \color{#0a0}{n\!+\!1},\,\ {\rm so}\ \ y^{(\color{#0a0}{n+1})(\color{#c00}{n+1})}\!\equiv y^{\color{#0a0}{n+1}}\end{align}

Thus $$\ x\cdot x^n - y\cdot y^{n+1}\equiv x\cdot 1 - y\cdot 1\$$ proves OP (for $$\color{#90f}{\rm prime}\ p$$). More generally:

\!\left.\begin{align}{\bf Lemma}\ \bmod m\!:&\ \ y^k\equiv x^n,\ (x,m)\!=\!1\\ \bmod{\phi=\phi(m)}\!:&\ \ \color{#c00}{nk}\equiv 0,\ \ \ \color{#0a0}{kk\mid k}\end{align}\right\}\,\Rightarrow\, y^k\equiv 1

Proof: $$\ \ \ \bmod m\!: \ y^{kk}\!\equiv x^{\color{#c00}{nk}}\equiv 1\$$ so $$\,y^k\equiv 1,\,$$ by $$\,\color{#0a0}{kk\mid k}\pmod{\!\phi},\,$$ where we applied the Congruence Power Rule, and Euler's totient $$(\phi)$$ theorem, and mod order reduction.

Cor.  Lemma holds if $$\,\phi \! =\! \bar nk,\ (k,\bar n)\!=\!1,\ \bar n\mid n,\,$$ e.g. $$\rm\color{#90f}{prime}$$ $$\,\color{#90f}{m \!=\! kn\!+\!1,\ k \!=\! n\!+\!1}\,$$ (OP).
Proof $$\ \phi^{\phantom{|^{|^|}}}\!\!\!\!=\bar nk\mid \color{#c00}{nk}.\,$$ $$(k,\bar n)\!=\!1\Rightarrow jk = 1 \!+\! i\:\!\bar n$$ $$\underset{\times\,k}\Rightarrow jk^2\! = k\! +\! i\phi\Rightarrow \color{#0a0}{k^2\mid k}\pmod{\!\phi}$$

• Note that this approach uses only lil Fermat and basic congruence laws - no knowledge of group theory (or primitive roots) is required. Feb 6 at 18:41

Leave out the trivial case when $$157|x,y$$. Take the primitive root $$g$$ of $$\mod 157$$. Therefore we know that if $$x^{12}\equiv g^k\mod 157$$, $$k$$ is a multiple of $$12$$. If $$y^{13}\equiv g^k\mod 157$$, $$k$$ is a multiple of $$13$$. Since $$x^{12} \equiv y^{13} \equiv g^k\mod 157$$, $$k$$ is a multiple of $$12$$ and a multiple of $$13$$, which is a multiple of $$156$$, which is $$0$$. Therefore, $$x^{12} \equiv y^{13} \equiv 1\mod 157$$, and $$x^{13}-y^{14}-x+y\equiv x-y-x+y\equiv 0\mod 157$$.

If you need a solution WITHOUT primitive root, we can do it like this: we also leave out the trivial case when $$157|x,y$$. Then, wun the following code in Python:

set((x**12)%157 for x in range(1,156))
Out[1]: {1, 14, 16, 39, 46, 67, 75, 93, 99, 101, 108, 130, 153}

set((y**13)%157 for y in range(1,156))
Out[2]: {1, 12, 13, 22, 28, 50, 107, 129, 135, 144, 145, 156}


Here you can see the intersection of set of all the $$x^{12}$$s and the set of all $$y^{13}$$'s is only $$\{1\}$$. This also yields $$x^{12} \equiv y^{13} \equiv 1\mod 157$$