Ratkaisu:

\text{[math]}

Olkoon nyt $\text{[math]}$ ja oletetaan, että alkuluku $\text{[math]}$ jakaa luvun $\text{[math]}$ . Näytetään, kongruenssin avulla, ettei $\text{[math]}$ jaa lukua $\text{[math]}$ :

\text{[math]}

Tästä seuraa, että jos alkuluku $\text{[math]}$ jakaa luvun $\text{[math]}$ , niin se ei jaa lukua $\text{[math]}$ . Siispä lukujen $\text{[math]}$ ja $\text{[math]}$ suurin yhteinen tekijä on 1.