# Cancellation law Proof

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

• The notation $x \equiv y \pmod p$ means $p$ divides $x-y$ and vice versa – sharding4 Jun 7 '17 at 16:20
• As an exercise, you can also check $x \equiv y \pmod{p}$ is an equivalence relation, so it "feels" like equality. Thus we are justified to use a notation that looks very similar to equality sign. – Alex Vong Jun 7 '17 at 16:41
• $x\equiv y \mod p$ can be equivalently stated as $x=y+kp$ for some integer $k$. This implies $x-y=kp \Rightarrow \frac{x-y}{p} = k$. – Χpẘ Jun 7 '17 at 17:12

$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.

• Yes, I was thinking of ux = uy (mod p) as if the remainder of both ux and uy was p, however, now I understand why that implies that p divides ux - uy. Thanks – Leo Jun 7 '17 at 17:45
• Ah, that's equivalent with the definition I used. Note: $a = b (mod n) \iff n|(a-b) \iff \exists k \in \mathbb{Z}: nk = a-b \iff a = b + nk$, hence a and b have the same remainder when we divide by $n$ – user370967 Jun 7 '17 at 17:47