Tuje število

Tuji števili sta v matematiki dve celi števili a in b, ki nimata skupnega delitelja razen 1 in -1, oziroma enakovredno, katerih največji skupni delitelj je enak 1. To značilnost običajno zapišemo kot D(a,b) = 1. Seveda je lahko med seboj tudi več tujih števil.

6 in 35 sta na primer tuji števili, 6 in 27 pa nista, saj sta deljivi s 3. 1 je tuje število vsakemu celemu številu, 0 pa je tuje le 1 in -1.

Z Evklidovim algoritmom ali neposredno z razcepom na prafaktorje je moč določiti ali sta dve števili tuji.

Eulerjeva funkcija φ(n) pozitivnega celega števila n da skupno število celih števil med 1 in n, ki so n tuja.

Značilnosti tujih števil

Dve zaporedni naravni števili a in a 1 sta si tuji. To dejstvo je uporabil Evklid pri svojem dokazu o neskončnem številu praštevil.

Dve naravni števili a in b sta tuji, če sta tuji števili $2^{a}-1$ in $2^{b}-1$.

Obstaja več pogojev, ki so enakovredni dejstvu da sta a in b tuji števili:

• obstajata takšni celi števili x in y, da velja linearna diofantska enačba $ax by=1$ (glej Bézoutova enakost).
• celo število b ima recipročno vrednost po modulu a: obstaja takšno celo število y, da velja by ≡ 1 (mod a). Ali z drugimi besedami, b je enota za kolobar $\mathbb {Z} /a\mathbb {Z}$ celih števil po modulu a.

Tako velja, če sta a in b tuji in br ≡ bs (mod a), potem r ≡ s (mod a) - saj lahko »delimo z b« pri modulu a. Velja še naprej, če sta tuji a in c ter a in d, sta tuji tudi a in cd - saj je produkt enote spet enota.

Če sta a in b tuji števili, in če a deli produkt bc, potem a deli c. To dejstvo izraža posplošitev Evklidove leme, ki pravi, da za praštevilo p, ki deli produkt bc, lahko velja ali da p deli b ali c.

Dve celi števili a in b sta tuji, če je točka s koordinatama (a, b) v kartezičnem koordinatnem sistemu »vidna« iz izhodišča (0, 0) v smislu, da med izhodiščem in točko (a, b) ni točke s celoštevilskimi koordinatami.

Verjetnost, da sta dve naključno izbrani celi števili tuji, je enaka (glej pi):

$\prod _{p}^{\infty }\left(1-{\frac {1}{p^{2}}}\right)=1/\prod {\frac {1}{1-p^{-2}}}={\frac {1}{\zeta (2)}}={\frac {6}{\pi ^{2}}}$

Tu je $\zeta$ Riemannova funkcija ζ(s). Verjetnost je približno 60 %. V splošnem je verjetnost, da je $k$ naključno izbranih števil tujih, enaka $1/\zeta (k)$.