Theorem

Euclid's lemma

Arithmetic • Number System • Divisibility

Formula

a ∣ b c, g cd (a, b) = 1 \Rightarrow a ∣ c

a ∣ b c

and

g cd (a, b) = 1

, then

a ∣ c

; the special case of a prime,

p ∣ b c \Rightarrow p ∣ b

p ∣ c

, is what makes prime factorisation unique.

How to use it

1Check the coprimality before drawing the conclusion; without it the step is invalid.
2Use it to strip a factor that is coprime to the divisor off a divisibility statement.
3Chain it with $a ∣ ab$ and $ab ∣ c d \Rightarrow a ∣ c d$ to reach a conclusion about a single letter.

It is given that

7

divides

5 n

, where

n

is an integer. What follows about

n

Step-by-step

Answer

7 ∣ n

Watch out

Coprimality is essential:

6 ∣ 4 \times 3

yet

6

divides neither

4

nor

3

. The lemma concludes divisibility of the other factor, never of the coprime one.

Builds on

Also known as

Euclid's lemma, coprime divisor divides the other factor, a divides bc with gcd 1, prime dividing a product