Relacija deljivosti

Naravno število b imenujemo k-kratnik naravnega števila a, če lahko zapišemo

b = k • a,

kjer je k tudi naravno število. V tem primeru pravimo, da je a delitelj števila b ali a deli b.

Deljivost je relacija med števili. če število a deli število b, to zapišemo z znaki a | b.

Zgled: Število 5 ima večkratnike: 5, 10, 15, 20, … Število 5 je delitelj vseh svojih večkratnikov. Vsako naravno število ima nešteto večkratnikov, toda le nekaj deliteljev, ker delitelj ne more biti večji od števila.

Vsako naravno število, razen 1, ima vsaj dva delitelja: 1 in samo sebe.

Izrek: Relacija deljivosti je tranzitivna:

(a | b) in (b | c) sledi a | c

Dokaz: Po definiciji obstajata taki naravni števili k in m, da velja
b = k • a in c = m • b. Zato je c = m • b = m • k • a = (km)a, torej a | c.

Izrek: če a deli števili b in c, potem deli a tudi vsoto b + c in razliko b - c.

(a | b) in (a | c) sledi a | (b + c) in a | (b - c)

Dokaz: Po definiciji zapišemo b = k • a, c = m • a.
Zato je b + c = (k + m)a in b - c = (k - m)a.
Torej a deli b + c in b - c.

Zgledi:

• 4 | 20, ker je 20 = 4 • 5

• 3 | 6 in 6 | 12 sledi 3 | 12 (tranzitivnost)

• Dokažimo, če velja (a | b) in (b | a) potem a = b
  Dokaz: Iz (a | b) sledi, da je b = k • a. Iz (b | a) pa sledi, da je a = m • b.
  Potem je b = k • a = k • m • b = (km)b. To pa je mogoče le, če sta k in m enaka 1.
  Od tod pa sledi, da velja a = b.

• Dokažimo, da je razlika kvadratov dveh zaporednih lihih števil deljiva z 8.
  Dokaz: (2n + 1)² - (2n - 1)² = 8n