Let $x$ and $y$ be integers and let $p$ be a prime number. Suppose that there exist realatively prime positive integers $m$ and $n$ such that $$x^m \equiv y^n \pmod p$$Prove that there exists an unique integer $z$ modulo $p$ such that $$x \equiv z^n \pmod p \quad \text{and} \quad y \equiv z^m \pmod p$$
Problem
Source: Iran 3rd round 2017 Numbers theory final exam-P1
Tags: Iran 3rd Round, bezout, Orders
13.09.2017 20:29
Anyone has any idea?Thanks!!!
13.09.2017 22:38
Existence: By Bezouts identity there exists $a$ and $b$ such that $am+bn=1$. Now $$x\equiv x^{am+bn}\equiv x^{am}x^{bn}\equiv (y^ax^b)^n \pmod p$$and $$y\equiv y^{am+bn}\equiv y^{am}x^{bn}\equiv (y^ax^b)^m \pmod p$$Så $z\equiv y^ax^b \pmod p$ works. Uniqueness: Assume that we have two such $z$, $z_1$ and $z_2$. Then $z_1^n\equiv z_2^n\equiv x \pmod p$ and $z_1^m\equiv z_2^m \equiv y \pmod p$. Therefore $(z_1z_2^{-1})^n\equiv 1 \pmod p$ and $(z_1z_2^{-1})^m\equiv 1 \pmod p$. Since $\gcd(m,n)=1$ it follows that $z_1z_2^{-1}\equiv 1\pmod p$ and $z_1\equiv z_2\pmod p$ which proves uniqeuness.
13.05.2018 16:57
Wlog assume that $(p,x,y)=1$.Let $g$ be a primitive root modulo $p$.There exists $a,b \in \mathbb{Z}$ such that: $$x,y \equiv g^a , g^b \pmod p \implies g^{am} \equiv g^{bn} \pmod p \implies am \equiv bn \mod p-1$$So there exists a $k$ such that $am=bn+k(p-1)$.Take an integer $t$ such that $tn \equiv 1 \mod m$(since $(m,n)=1$ such a $t$ exists).We get that $m|b+kt(p-1)$.Let $b+kt(p-1)=lm$so: $$y \equiv g^b \equiv g^{b+kt(p-1)} \equiv g^{lm} \equiv (g^l)^m \pmod p$$The uniqueness follows from the fact that if we replace $t$ with $t+sm$,the congruities won't change modulo $p-1$ and since $a,b$ are defined uniquely,$l$ would be unique modulo $p-1$.
28.11.2020 11:11
Bezout's Lemma Solution. Since we are given $\gcd(m,n)=1$. It follows that $\exists a,b$ such that $am+bn=1$ from Bezout Lemma. Now notice the following: \begin{align*} x &\equiv x^{am+bn} \pmod{p} \\ &\equiv (x^{ma})(x^{bn}) \pmod{p} \\ &\equiv (y^{na})(x^{bn}) \pmod{p} \\ &\equiv (y^ax^b)^n \pmod{p} \\ \end{align*}Analogously, going other way around, we get $y \equiv (y^ax^b)^m$. Therefore, $z \equiv y^ax^b$ works. Now to show that this $z$ is unique. Let there $\exists z,z'$ which satisfies. Now $$z^n \equiv (z')^n \pmod{p} \implies \left(\frac{z}{z'}\right)^n \equiv 1 \pmod{p}$$whence we get $\operatorname{ord}_p(\tfrac{z}{z'}) \mid n$. Similarily $\operatorname{ord}_p(\tfrac{z}{z'}) \mid m$ which means $\operatorname{ord}_p(\tfrac{z}{z'}) \mid \gcd(m,n)=1$. Consequently, we get $z \equiv z'$ which finishes the problem. $\blacksquare$
28.11.2020 12:29
Let $r$ be a primitive root mod $p$.Assume that,$x \equiv r^a \pmod{p}$ and $y \equiv r^b \pmod{p}$.Then the condition is equivalent to $am=bn \pmod{p-1}$.Now,we can show easily that $z=r^t$ where $t=\frac{a}{n}=\frac{b}{m} \pmod{p-1}$ and since $m,n$ are coprime they both can't have anything in common with $p-1$(if one of them does say $m$,then $b$must have the same factor) which implies that $t$ is well defined in $\pmod{p-1}$ and is also unique which also implies $z$ is unique in $\pmod{p}$
21.01.2023 18:46
wow, second actual NT from any contest, I solved
handwritten solution images attached
13.09.2024 19:44
yayitsme wrote: Let $r$ be a primitive root mod $p$.Assume that,$x \equiv r^a \pmod{p}$ and $y \equiv r^b \pmod{p}$.Then the condition is equivalent to $am=bn \pmod{p-1}$.Now,we can show easily that $z=r^t$ where $t=\frac{a}{n}=\frac{b}{m} \pmod{p-1}$ and since $m,n$ are coprime they both can't have anything in common with $p-1$(if one of them does say $m$,then $b$must have the same factor) which implies that $t$ is well defined in $\pmod{p-1}$ and is also unique which also implies $z$ is unique in $\pmod{p}$ Why is it the case that if $\gcd(m,n) = 1$ and $am\equiv bn \pmod {p-1}$, then $\gcd(m,p-1) = \gcd(n,p-1) = 1$?
13.09.2024 20:47
If $p$ divides $x$, then from $x^m \equiv y^n$ it also divides $y$ and from $x\equiv z^n$, $y\equiv z^m$ the only possibility is $z\equiv 0 \pmod p$. From now on, suppose that $p$ does not divide $x$ or $y$. Let $g$ be a primitive root mod $p$. Write $x \equiv g^a \pmod{p}$, $y \equiv g^b \pmod{p}$, $z \equiv g^t \pmod p$. The given condition is equivalent to $am\equiv bn \pmod{p-1}$ and we want to show that there is a unique $t$ (mod $p-1$) such that $nt\equiv a \pmod {p-1}$ and $mt\equiv b \pmod {p-1}$. Since $\gcd(m,n) = 1$, by Bezout's lemma there are integers $A$ and $B$ with $Am+Bn = 1$. Note that $t\equiv Ab + Ba$ works since $nt \equiv Anb + Bna \equiv a + A(nb - am) \equiv a$ and similarly for $mt \equiv b$. Conversely, if $t$ satisfies the required congruences, then as $Amt + Bnt = t$, we have $Ab + Ba \equiv t \pmod {p-1}$ and so indeed there are no more possibilities for $t$.
13.09.2024 21:08
First note that there exists $a,b$ integers with $an+bm=1$ from Bezouts theorem, so... $$x \equiv x^{an+bm} \equiv x^{an} \cdot x^{bm} \equiv (x^ay^b)^n \pmod p$$$$y \equiv y^{an+bm} \equiv y^{an} \cdot y^{bm} \equiv (x^ay^b)^m \pmod p$$So $z \equiv x^ay^b \pmod p$ works, now we will prove this $z$ is unique, so suppose FTSOC that we have that some other $z'$ also works, then ${z'}^n \equiv z^n \pmod p$ and ${z'}^m \equiv z^m \pmod p$ if any $x,y,z,z'$ is $0$ then the rest are zero as well so suppose none is, then we get that $\left(\frac{z}{z'} \right)^{\gcd(m,n)} \equiv 1 \pmod p$ from a well known lemma but this just means $z \equiv z' \pmod p$, thus our $z$ is unique and we are done .
31.12.2024 09:16
similar to INMO '24 p3