Delbarhet og Divisjon

Dette innlegget har allerede blitt vist 1931 ganger!

Definisjon: b deler a hvis det finnes en q slik at a = q*b (ba ⇔ ∃q: a = q*b)

Notasjon: ba

Heltallsdivisjon: Gitt a og b > 0 finns det en q og r slik at a = q*b + r og 0 ≤ r < q (Her kalles q kvotienten og r resten)

Største felles divisor til a og b er det største tallet d slik at da og db (notasjon: gcd(a,b).
Det finnes alltid en x og y slik at gcd(a,b) = ax + by

a og b er relativt primiske hvis gcd(a,b) = 1. Dette er ekvivalent med å si at det finnes et heltall x og et heltall y slik at ax + by = 1.

Gitt a og b relativt primiske:

  • Hvis ab så er gcd(a,b) = b
  • gcd(a,b) = gcd(b, a mod b)