Minste felles multiplum og største felles divisor

Definisjon

La <math>a</tex> og <math>b</tex> være heltall. Da finnes det heltall <math>r,s</tex> slik at

<math>ar=bs</tex>

og verdien av <math>ar</tex> og <math>bs</tex> kalles da et felles multiplum av <math>a</tex> og <math>b</tex>. Det minste felles multiplumet til <math>a</tex> og <math>b</tex> er det minste slike multiplumet og noteres ved <math>\text{lcm}(a,b)</tex> (Les: Least common multiple).

Det finnes også et heltall <math>t</tex> slik at <math>t</tex> deler både <math>a</tex> og <math>b</tex>. Det største slike tallet <math>t</tex> kalles den største felles divisoren til <math>a</tex> og <math>b</tex> og noteres ved <math>\gcd(a,b)</tex> (Les: Greatest common divisor).

Sammenheng med primtallsfaktorisering

La <math>a</tex> og <math>b</tex> ha primtallsfaktoriseringer gitt ved <math>a=p_1^{a_1}p_2^{a_2}...p_n^{a_n}</tex> og <math>b=p_1^{b_1}p_2^{b_2}...p_n^{b_n}</tex>, der <math>a_i,b_i=0,1,2,\,...</tex>. La så <math>M_i=\max(a_i,b_i)</tex> og <math>m_i=\min(a_i,b_i)</tex>.

Da er

<math>\text{lcm}(a,b)=p_1^{M_1}p_2^{M_2}...p_n^{M_n}</tex>

og

<math>\gcd(a,b)=p_1^{m_1}p_2^{m_2}...p_n^{m_n}</tex>

Fra denne sammenhengen, og at <math>M_i+m_i=a_i+b_i</tex> er det rett frem å vise at

<math>\gcd(a,b)\cdot \text{lcm}(a,b) = a\cdot b</tex>

Euklids algoritme

Dersom <math>a, b, r</tex> er heltall, gjelder <math>\gcd(a,b)=\gcd(a-rb,b)</tex>, fordi alle faktorer som deler <math>b</tex>, også deler <math>rb</tex>.

Ettersom vi kan finne heltall <math>c</tex> og <math>k_0</tex> slik at <math>a=bc+k_0</tex> og <math>0\leq d < |b|</tex>, har vi dermed at

<math>gcd(a,b)=gcd(b,k_0)</tex>.

Ettersom vi også har <math>b=t_0 k_0 + k_1</tex> for heltall <math>t_0,k_</tex> får vi at

<math>gcd(a,b)=gcd(b,k_0)=gcd(k_0,k_1)</tex> og så videre.

Dette er euklids algoritme. Hvis vi fortsetter denne prosessen, vil vi etter et endelig antall (<math>N</tex>) steg komme til et punkt der <math>k_{N-1}=t*k_{N}</tex>, og vi får da at

<math>\gcd(a,b)=\gcd(k_{N-1},k_N)=\gcd(t\cdot k_N,k_N)=k_N</tex>

---