Generalized Euclid's lemma

Statement

Let $n$ , $a$ and $b$ be integers. If $n \mid a b$ and $n$ and $a$ are coprime, then $n \mid b$ .

Remarks

When $n$ is a prime $p$ and $p \nmid a$ , then $p$ and $a$ are coprime. So this result implies Euclid's lemma. The proof uses Bézout's identity: from $n x + a y = 1$ we get $b = n b x + a b y$ , and $n$ divides both terms. For example, $5 \mid 3 \cdot 10$ and $\gcd(5, 3) = 1$ , so $5 \mid 10$ .

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Where this leads

1 page builds on this one.

Cancellation in congruences

Tag	`03BAREW1Z5`
URI	`m2://03BAREW1Z5`
Kind	statement, proposition
Writing	W0 stub
MSC	11A05
Status	This copy of the site has no build data. Run `m2 status 03BAREW1Z5`.
Uses	Coprime integers, Divisibility

Generalized Euclid's lemma

Statement

Remarks

Reading path

Where this leads

Further reading

What this page needs for W1

What links here

Used by