¿Cómo resolver la siguiente ecuación en $\mathbb{Z}_n$?

Question

Dado un $n\in\mathbb{N}$, $a\in \mathbb{Z}_n$ y $x,y\in\mathbb{Z}$, cómo plantear a la solución de la ecuación siguiente:

$a^x \equiv a^y \mod n$

Creo que desde aquí yo puedo deducir que:

$x \equiv y \mod \varphi (n)$

¿Pero si es así, no sé por qué? ¿Podría alguien ayudar con una explicación?

Answer 1

Incluso el mucho más fuerte supuesto que $a^x\equiv a^y \pmod{n}$ no implica que el $\varphi(n)$ divide $x-y$. Por ejemplo, que $n=15$. Entonces $\varphi(n)=8$. Sin embargo, si el $a$ es relativamente prima a $15$ y $a^4\equiv 1\pmod{3}$ y $a^4\equiv 1\pmod{5}$, que $a^4\equiv 1\pmod{15}$.

Para obtener más información, por favor busque la función de Carmichael y exponente menos universal.