Krypterings sætninger

Det svarer til at bevise at a^k(p-1)(q-1) ≡ a mod (p*q) Der forudsættes p≠q  p og q primtal ellers gælder den ikke.

Der forudsættes Fermats lille sætning a^p-1 ≡ 1 mod p  a indeholder ikke primfaktoren p. Opløfter man venstre side og højre får man a^k(p-1) ≡ 1 mod p Ganger man dette med a får man a^k(p-1)+1 ≡ a mod p som også gælder hvis a indeholder faktoren p. Heraf fås  a^k(p-1)+1 ≡ a mod p <=> a^k(p-1)+1-a ≡ 0 mod p <=> p| (a^k(p-1)+1-a)

sætningen a^k(p-1)(q-1) ≡ a mod (p*q) omskrives tilsvarende a^k(p-1)(q-1) ≡ a mod (p*q) <=> a^k(p-1)(q-1) -a ≡ 0 mod (p*q) <=> p*q | ( a^k(p-1)(q-1)-a)  <=> p | ( a^k(p-1)(q-1)-a) og q | ( a^k(p-1)(q-1)-a) hvilket er opfyldt ifølge sætningen ovenfor.

Den anden er åbenlyst opfyldt for a=0. Hvis a ikke indeholder faktorene p og q gælder der x=a +k₁*p og x=a+ k₂*q. Begge dele kan kun lade sig gøre hvis k₁ indehokder q og k₂ indeholder p altså x=a+ k*p*q