I have shown the case in which $p=2$, so now I'm considering $p\geq 3$. I see that $p^{2}-p = p(p-1)$, in which case we can apply the Chinese Remainder Theorem to obtain $a\equiv [b,b] \mod{[p,\phi(p)]}$, since $p$ and $(p-1)$ are coprime and $\phi(p)=(p-1)$ where $\phi$ is Euler's totient function. Also, I see that $a\equiv b \pmod{\phi(p)}$ implies that $x^a\equiv x^b \pmod{p}$ for some $x\in \Phi(p)$ by the Fermat-Euler theorem. However, I'm not sure if this is the best approach or how to continue from here. Any help is appreciated, thanks!

Edit: Now I see that $x^a\equiv x^b \pmod{p}$ is true for all $x\in \mathbb{Z}$. Because $p$ is prime, $x$ will either be coprime, or a multiple of $p$. In each case the statement is still true. This is why we can let $x = b$. Then we can use $a^a\equiv b^a \pmod{p}$ and $b^a\equiv b^b \pmod{p}$, and we're done.

  • 1
    $\begingroup$ You are basically done. By $a\equiv_p b$ we have $a^a\equiv_p b^a$. Then, as you said yourself (set $x=b$), we have $b^a\equiv_p b^b$. $\endgroup$ – Arthur Mar 4 '18 at 22:48


By the Chinese remainder theorem, the hypothesis is equivalent to $a\equiv b\mod p$ AND $a\equiv b\mod p-1$.

Now lil' Fermat states that $\;a^a\equiv \bigl((a\bmod p)^{a\bmod p-1}\bigr)\bmod p$, and similarly for $b$.


Fix $p\ge 3$ and note that $p(p-1)\mid a-b$ iff $p\mid a-b$ and $p-1 \mid a-b$. So $a$ and $b$ have the same remainder modulo $p$ and modulo $p-1$. Moreover, the sequences $(a^n)_{n\ge 1}$ and $(b^n)_{n\ge 1}$ are periodic modulo $p-1$, which implies that $$ a^x \equiv b^y \bmod{p} $$ whenever $x \equiv y \bmod{p-1}$. But $x=a$ and $y=b$ verify this condition by hypothesis.


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.