NWD kk: NWD(p,q) =1. To oznacza, że dla p istnieje odwrotność p' modulo q. pp'=qr+1 1. Jak uzasadnić, że p' < q ? 2. Jak uzasadnić, że NWD(r,p')=1 ?

kochanus_niepospolitus: 1) Niewprost ∄_{p' < q} p*p' = qr + 1 ; r∊N₊ oraz NWD(r,p) < p zatem: ∃_w<q p' = w + q*s ; s∊N₊ L = p*p' = p*(w + qs) = pw + pqs = qr + 1 = P pw + pqs = qr + 1 ⇔ pw = q(ps−r) + 1 ⇔ p*w = q*o + 1 ; o ∊ N₊ ponieważ ps ≠ r sprzeczność c.n.w.

jc: p p' = q r + 1 Jeśli d|r i d|p', to d | p p' − q r = 1, a więc NWD(r,p')=1.