Euklides lemma

Sats. Om ett primtal delar produkten av två heltal så delar primtalet åtminstone en av faktorerna. 

Bevis. Låt primtalet $p$ dela produkten av heltalen $a$ och $b$.

    $a\cdot b=p \cdot \lambda$.

Anta att $p$ varken delar $a$ eller $b$. Då är den största gemensamma delaren till $a$ och $p$ talet $1$ och Bezouts identitet säger att det då existerar heltal $(u,v)$ sådana att

    $pu+av=1$.

Multiplicera denna likhet med $b$ för att få $p\cdot(bu+v\lambda) = b,$ vilken visar att $p$ delar $b$. Denna motsägelse visar att primtalet $p$ delar åtminstone ett av talen $a$ och $b$.