Minste felles multiplum og største felles divisor: Forskjell mellom sideversjoner

Siste sideversjon per 5. feb. 2013 kl. 20:59

Definisjon

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

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

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

Sammenheng med primtallsfaktorisering

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

Da er

og

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

Euklids algoritme

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

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

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

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

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

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

@@ Linje 1: / Linje 1: @@
-Minste felles multiplum skrives ofte MFM. Dersom vi skal finne minste felles multiplum av 12 og 18 starter vi med å faktorisere begge tallene: 12 = 2·2·3 og 18 = 2·3·3. I dette tilfellet blir MFM = 2·2·3·3 = 36, fordi 36 er det minste tallet både 12 og 18 går opp i, altså deres minste felles multiplum.
+==Definisjon==
-Vi skriver det slik:
+La <math>a</math> og <math>b</math> være heltall. Da finnes det heltall <math>r,s</math> slik at
-mfm(12, 18) = 36
+<math>ar=bs</math>
-Dette finne vi ved å samle primtallsfaktorene fra 2 og oppover, der flest antall "like" er tellende; vi samler 2-er faktorene fra 12 fordi 12 har to 2-er faktorer mens 18 bare har en. Treerfaktorene kommer fra 18 fordi 18 har to 3-er faktorer mot 12's ene.
+og verdien av <math>ar</math> og <math>bs</math> kalles da et felles multiplum av <math>a</math> og <math>b</math>. Det minste felles multiplumet til <math>a</math> og <math>b</math> er det minste slike multiplumet og noteres ved <math>\text{lcm}(a,b)</math> (Les: Least common multiple).
-Det største tallet som går opp i både 12 0g 18 er 6. Vi sier at 6 er største felles divisor, sfd, eller største felles mål.
-Vi skriver det slik:
+Det finnes også et heltall <math>t</math> slik at <math>t</math> deler både <math>a</math> og <math>b</math>. Det største slike tallet <math>t</math> kalles den største felles divisoren til <math>a</math> og <math>b</math> og noteres ved <math>\gcd(a,b)</math> (Les: Greatest common divisor).
-sfd ( 12, 18) = 6
+==Sammenheng med primtallsfaktorisering==
-Sammenhengen mellom minste felles multiplum og største felles divisor er:
+La <math>a</math> og <math>b</math> ha primtallsfaktoriseringer gitt ved <math>a=p_1^{a_1}p_2^{a_2}...p_n^{a_n}</math> og <math>b=p_1^{b_1}p_2^{b_2}...p_n^{b_n}</math>, der <math>a_i,b_i=0,1,2,\,...</math>. La så <math>M_i=\max(a_i,b_i)</math> og <math>m_i=\min(a_i,b_i)</math>.
-a·b = mfm (a ,b)· sfd (a, b)
+Da er
+<math>\text{lcm}(a,b)=p_1^{M_1}p_2^{M_2}...p_n^{M_n}</math>
+og
+<math>\gcd(a,b)=p_1^{m_1}p_2^{m_2}...p_n^{m_n}</math>
+Fra denne sammenhengen, og at <math>M_i+m_i=a_i+b_i</math> er det rett frem å vise at
+<math>\gcd(a,b)\cdot \text{lcm}(a,b) = a\cdot b</math>
+==Euklids algoritme==
+Dersom <math>a, b, r</math> er heltall, gjelder <math>\gcd(a,b)=\gcd(a-rb,b)</math>, fordi alle faktorer som deler <math>b</math>, også deler <math>rb</math>.
+Ettersom vi kan finne heltall <math>c</math> og <math>k_0</math> slik at <math>a=bc+k_0</math> og <math>0\leq d < |b|</math>, har vi dermed at
+<math>gcd(a,b)=gcd(b,k_0)</math>.
+Ettersom vi også har <math>b=t_0 k_0 + k_1</math> for heltall <math>t_0,k_</math> får vi at
+<math>gcd(a,b)=gcd(b,k_0)=gcd(k_0,k_1)</math> og så videre.
+Dette er euklids algoritme. Hvis vi fortsetter denne prosessen, vil vi etter et endelig antall (<math>N</math>) steg komme til et punkt der <math>k_{N-1}=t*k_{N}</math>, 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</math>
 ----
+[[Kategori:Tallteori]]
 [[kategori:lex]]