Getalteorie: Deelbaarheid en Delingsalgoritme

• Getalteorie is 'n tak van wiskunde wat hoofsaaklik gewy is aan die studie van heelgetalle en heelgetal-waardeerde funksies.

Deelbaarheid

• 'n Heelgetal a is deelbaar deur 'n heelgetal b as daar 'n heelgetal k bestaan sodanig dat a = bk.
• Notasie: b | a (lees as "b deel a").
• As b | a, dan is b 'n deler of faktor van a, en a is 'n veelvoud van b.
• As b nie a deel nie, skryf ons b <binary data, 1 bytes><binary data, 1 bytes><binary data, 1 bytes> a.
• Elke heelgetal a is deelbaar deur 1, -1, a en -a. Hierdie word die triviale delers genoem.

Eienskappe van Deelbaarheid

• As a | b en a | c, dan a | (bx + cy) vir enige heelgetalle x en y.
• As a | b en b | c, dan a | c (transitiwiteit).
• As a | b en b | a, dan a = ±b.
• As a | b en a > 0 en b > 0, dan a ≤ b.
• As a | b, dan ca | cb vir enige heelgetal c.
• As ac | bc en c ≠ 0, dan a | b.

Delingsalgoritme

• Gegewe heelgetalle a en b met b > 0, bestaan daar unieke heelgetalle q en r sodanig dat a = bq + r, waar 0 ≤ r < b.
• a is die deeltal, b is die deler, q is die kwosiënt en r is die res.
• Die res r word ook aangedui as a mod b.

Grootste Gemeenskaplike Deler (GGD)

• Die grootste gemene deler van twee heelgetalle a en b (nie beide nul nie) is die grootste positiewe heelgetal wat beide a en b deel.
• Notasie: ggd(a, b) of (a, b).
• As ggd(a, b) = 1, dan is a en b relatief prima of kopriem.
• Eienskappe van GGD:
  • ggd(a, b) = ggd(b, a).
  • ggd(a, 0) = |a| vir a ≠ 0, en ggd(0, 0) is ongedefinieerd.
  • ggd(a, 1) = 1.
  • ggd(ca, cb) = |c| ggd(a, b).
  • As a | bc en ggd(a, b) = 1, dan a | c.

Euklidiese Algoritme

• 'n Doeltreffende metode om die grootste gemene deler van twee heelgetalle te bereken.
• Algoritme:
  • Gegewe a en b, met a > b, pas die delingsalgoritme herhaaldelik toe:
    • a = bq₁ + r₁, 0 ≤ r₁ < b
    • b = r₁q₂ + r₂, 0 ≤ r₂ < r₁
    • r₁ = r₂q₃ + r₃, 0 ≤ r₃ < r₂
    • ...
    • rₙ₋₂ = rₙ₋₁qₙ + rₙ, 0 ≤ rₙ < rₙ₋₁
    • rₙ₋₁ = rₙqₙ₊₁ + 0
  • Die laaste nie-nul res rₙ is die ggd(a, b).

Bézout se Identiteit

• Vir enige heelgetalle a en b, bestaan daar heelgetalle x en y sodanig dat ax + by = gcd(a, b). Die heelgetalle x en y word Bézout-koëffisiënte genoem.
• Die Euklidiese algoritme kan uitgebrei word om die Bézout-koëffisiënte te vind.

Kleinste Gemene Veelvoud (KGV)

• Die kleinste gemene veelvoud van twee positiewe heelgetalle a en b is die kleinste positiewe heelgetal wat deelbaar is deur beide a en b.
• Notasie: kgv(a, b).
• Verwantskap tussen GGD en KGV: a * b* = ggd(a, b) * kgv(a, b).

Priemgetalle

• 'n Priemgetal is 'n heelgetal groter as 1 wat slegs twee positiewe delers het: 1 en homself.
• 'n Heelgetal groter as 1 wat nie priem is nie, word saamgestel genoem.
• Die eerste paar priemgetalle is 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, ...
• 2 is die enigste ewe priemgetal.

Fundamentele Teorema van Rekenkunde

• Elke heelgetal groter as 1 kan uniek uitgedruk word as 'n produk van priemgetalle, tot op die volgorde van die faktore. Dit word die priemfaktorisering genoem.
• Formeel: Vir elke heelgetal n > 1, bestaan daar afsonderlike priemgetalle p₁, p₂,..., pₖ en positiewe heelgetalle α₁, α₂,..., αₖ sodanig dat *n = p₁ᵃ¹ * p₂ᵃ² ... * pₖᵃᵏ. Hierdie voorstelling is uniek.

Distributie van priemgetalle

• Daar is oneindig baie priemgetalle (Euclides se bewys).
• Die priemgetalstelling bepaal dat die aantal priemgetalle minder as of gelyk aan x, aangedui deur π(x), ongeveer x / ln(x) is.

Kongruensies

• As a en b heelgetalle is en m 'n positiewe heelgetal is, dan is a kongruent aan b modulo m as m | (a - b).
• Notasie: a ≡ b (mod m).
• As a nie kongruent is aan b modulo m nie, skryf ons a <binary data, 1 bytes><binary data, 1 bytes><binary data, 1 bytes> b (mod m).
• a ≡ b (mod m) as en slegs as a en b dieselfde res het wanneer dit deur m gedeel word.

Eienskappe van Kongruensies

• As a ≡ b (mod m) en c ≡ d (mod m), dan:
  • a + c ≡ b + d (mod m).
  • a - c ≡ b - d (mod m).
  • ac ≡ bd (mod m).
  • aⁿ ≡ bⁿ (mod m) vir enige positiewe heelgetal n.
• As a + c ≡ b + c (mod m), dan a ≡ b (mod m).
• As ac ≡ bc (mod m) en ggd(c, m) = 1, dan a ≡ b (mod m).
• As ac ≡ bc (mod mc), dan a ≡ b (mod m).

Lineêre Kongruensies

• 'n Lineêre kongruensie is 'n kongruensie van die vorm ax ≡ b (mod m).
• Die kongruensie ax ≡ b (mod m) het 'n oplossing as en slegs as ggd(a, m) | b.
• As ggd(a, m) = d en d | b, dan het die kongruensie d afsonderlike oplossings modulo m.
• Om ax ≡ b (mod m) op te los, vind die multiplikatiewe inverse van a modulo m. As a⁻¹ bestaan, dan x ≡ a⁻¹b (mod m).
• Die multiplikatiewe inverse van a modulo m bestaan as en slegs as ggd(a, m) = 1.

Chinese Reststelling (CRT)

• Laat m₁, m₂,..., mₖ paarsgewys relatief prima positiewe heelgetalle wees. Dan het die stelsel kongruensies:
  • x ≡ a₁ (mod m₁)
  • x ≡ a₂ (mod m₂)
  • ...
  • x ≡ aₖ (mod mₖ)
• het 'n unieke oplossing modulo M = m₁m₂...mₖ.
• Die oplossing kan soos volg gevind word:
  • Laat M = m₁m₂...mₖ.
  • Laat Mᵢ = M / mᵢ.
  • Vind yᵢ sodanig dat Mᵢyᵢ ≡ 1 (mod mᵢ).
  • Dan x ≡ a₁M₁y₁ + a₂M₂y₂ + ... + aₖMₖyₖ (mod M).

Fermat se klein stelling

• As p 'n priemgetal is en a 'n heelgetal is wat nie deelbaar is deur p nie, dan a^(p-1) ≡ 1 (mod p).
• 'n Alternatiewe vorm: Vir enige heelgetal a en priem p, a^p ≡ a (mod p).

Euler se Totient-funksie

• Euler se totient-funksie, aangedui deur φ(n), is die aantal positiewe heelgetalle kleiner as of gelyk aan n wat relatief prima is tot n.
• Eienskappe:
  • As p priem is, dan φ(p) = p - 1.
  • As p priem is en k 'n positiewe heelgetal is, dan φ(pᵏ) = pᵏ - p^(k-1) = pᵏ(1 - 1/p).
  • As m en n relatief prima is, dan φ(mn) = φ(m)φ(n) (multiplikatiewe eienskap).
  • As *n = p₁ᵃ¹ * p₂ᵃ² ... * pₖᵃᵏ die priemfaktorisering van n is, dan φ(n) = n(1 - 1/p₁)(1 - 1/p₂)...(1 - 1/pₖ).

Euler se Stelling

• As a en n relatief priem positiewe heelgetalle is, dan a^(φ(n)) ≡ 1 (mod n).
• Fermat se klein stelling is 'n spesiale geval van Euler se stelling waar n 'n priemgetal is.