6
$\begingroup$

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.

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

3 Answers 3

5
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

$\!\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}$

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

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$

$\endgroup$

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.