I don't have high level of knowledge in math so forgive me if I sound too ignorant.
I've been trying to understand a proof of Fermat's Little theorem in Wikipedia. There is a particular paragraph that confuses me:
"If $u$, $x$, and $y$ are integers, and $u$ is not divisible by a prime number $p$, and if
$$ux = uy \pmod p \tag{C}$$
then we may 'cancel' $u$ to get
$$x = y \pmod p \tag{D}$$
We can prove the cancellation law easily using Euclid's lemma, which generally states that if a prime $p$ divides a product $ab$ (where $a$ and $b$ are integers), then $p$ must divide $a$ or $b$. Indeed, the assertion (C) simply means that $p$ divides $ux − uy = u(x − y)$. Since p is a prime which does not divide $u$, Euclid's lemma tells us that it must divide $x − y$ instead; that is, (D) holds."
I understand Euler's Lemma, but even so, I can't comprehend why the fact that $p$ divides $(x-y)$ proves that (D) is true
Best Answer
$ux = uy \quad\bmod p$ means, by definition, that $p|(ux -uy)$
Equivalently, we have $p|(u(x-y))$, and given is that $p$ does not divide $u$. Hence, $p$ must divide $x-y$. So, we have $p|(x-y)$, which translates by definition to $x = y \quad \bmod p$
If you have any questions, or use another definition for modular equalities, I will edit my question. Please let me know.