Minste felles multiplum og største felles divisor: Forskjell mellom sideversjoner
m Teksterstatting – «</tex>» til «</math>» |
|||
(Én mellomliggende sideversjon av samme bruker vises ikke) | |||
Linje 1: | Linje 1: | ||
==Definisjon== | ==Definisjon== | ||
La < | La <math>a</math> og <math>b</math> være heltall. Da finnes det heltall <math>r,s</math> slik at | ||
< | <math>ar=bs</math> | ||
og verdien av < | 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 < | 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== | ==Sammenheng med primtallsfaktorisering== | ||
La < | 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 | Da er | ||
< | <math>\text{lcm}(a,b)=p_1^{M_1}p_2^{M_2}...p_n^{M_n}</math> | ||
og | og | ||
< | <math>\gcd(a,b)=p_1^{m_1}p_2^{m_2}...p_n^{m_n}</math> | ||
Fra denne sammenhengen, og at < | 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== | ==Euklids algoritme== | ||
Dersom < | 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 < | 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 < | 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 (< | 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:Tallteori]] | ||
[[kategori:lex]] | [[kategori:lex]] |
Siste sideversjon per 5. feb. 2013 kl. 20:59
Definisjon
La
og verdien av
Det finnes også et heltall
Sammenheng med primtallsfaktorisering
La
Da er
og
Fra denne sammenhengen, og at
Euklids algoritme
Dersom
Ettersom vi kan finne heltall
Ettersom vi også har
Dette er euklids algoritme. Hvis vi fortsetter denne prosessen, vil vi etter et endelig antall (