Hogyan döntöm el, hogy mik a prímek egy Z(n)-es gyűrűben?

Ugyanúgy, mint egyébként; egy szám prím, hogyha pontosan két osztója van, ami az 1 és önmaga.

Felírod a számok szorzatát. Mondjuk Z4-ben:

0*0=0

0*1=0

0*2=0

0*3=0

1*0=0

1*1=1

1*2=2

1*3=3

2*0=0

2*1=2

2*2=0

2*3=6=2

3*0=0

3*1=3

3*2=6=2

3*3=9=1

Látható, hogy egyedül a 3 áll elő kétféleképpen, tehát a 3 prímszám, a többi nem.

Azért, mert mindegyik szorzatos felírás esetén az egyik tényező egység (egységek azok, amelyek az 1-nek osztói (vagyis, hogy van multiplikatív inverzük)).

1*6 és 6*1-et nem kell magyarázni.

2*3-nál a 3 egy egység Z8-ban, mert 3*3=1

2*7-nél a 7 egy egység Z8-ban, mert 7*7=1

5*6-nál az 5 egy egység, mert 5*5=1.

Ezeket úgy lehet megtalálni, hogy meg kell nézni, hogy az adott számnak minden felbontása olyan-e, hogy legalább az egyik tényező relatív prím a modulushoz, mert azoknak mindig van multiplikatív inverze (euklideszi algoritmussal megtalálható). Ha minden szorzat felbontás ilyen, akkor az a szám prím modulo n.