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

  • 5
    $\begingroup$ The notation $x \equiv y \pmod p$ means $p$ divides $x-y$ and vice versa $\endgroup$ – sharding4 Jun 7 '17 at 16:20
  • $\begingroup$ 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. $\endgroup$ – Alex Vong Jun 7 '17 at 16:41
  • 1
    $\begingroup$ $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$. $\endgroup$ – Χ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.

  • $\begingroup$ 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 $\endgroup$ – Leo Jun 7 '17 at 17:45
  • $\begingroup$ 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$ $\endgroup$ – user370967 Jun 7 '17 at 17:47

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.