Uzajamno Prosti Brojevi

Dva prirodna broja ne moraju biti prosta da bi bila uzajamno prosta, bitno je samo da nijedan delilac jednog ne bude među deliocima drugog.

Ekvivalentno prethodnom tvrđenju, najveći zajednički delitelj dva uzajamno prosta broja je 1.

Dakle, ako prema osnovnoj teoremi aritmetike predstavimo ta dva broja kao proizvode njihovih faktora:

${\displaystyle n=p_{1}\cdot p_{2}\cdot ...\cdot p_{i}}$
${\displaystyle m=q_{1}\cdot q_{2}\cdot ...\cdot q_{j}}$

tada nijedan ${\displaystyle p_{k}\,}$ ne sme biti jednak nijednom od ${\displaystyle q_{l}\,}$.

Nekada se uzajamno prosti brojevi zovu relativno prosti brojevi.

• Spisak prostih brojeva
• Deljivost
• Faktorizacija
• Eratostenovo sito
• Euklidov algoritam