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

Fra Matematikk.net
Hopp til: navigasjon, søk
m Teksterstatting – «</tex>» til «</math>»
 
(Én mellomliggende sideversjon av samme bruker vises ikke)
Linje 1: Linje 1:
==Definisjon==
==Definisjon==


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


<tex>ar=bs</tex>
<math>ar=bs</math>


og verdien av <tex>ar</tex> og <tex>bs</tex> kalles da et felles multiplum av <tex>a</tex> og <tex>b</tex>. Det minste felles multiplumet til <tex>a</tex> og <tex>b</tex> er det minste slike multiplumet og noteres ved <tex>\text{lcm}(a,b)</tex> (Les: Least common multiple).
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 <tex>t</tex> slik at <tex>t</tex> deler både <tex>a</tex> og <tex>b</tex>. Det største slike tallet <tex>t</tex> kalles den største felles divisoren til <tex>a</tex> og <tex>b</tex> og noteres ved <tex>\gcd(a,b)</tex> (Les: Greatest common divisor).
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 <tex>a</tex> og <tex>b</tex> ha primtallsfaktoriseringer gitt ved <tex>a=p_1^{a_1}p_2^{a_2}...p_n^{a_n}</tex> og <tex>b=p_1^{b_1}p_2^{b_2}...p_n^{b_n}</tex>, der <tex>a_i,b_i=0,1,2,\,...</tex>. La så <tex>M_i=\max(a_i,b_i)</tex> og <tex>m_i=\min(a_i,b_i)</tex>.
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


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


og
og


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




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


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


==Euklids algoritme==
==Euklids algoritme==


Dersom <tex>a, b, r</tex> er heltall, gjelder <tex>\gcd(a,b)=\gcd(a-rb,b)</tex>, fordi alle faktorer som deler <tex>b</tex>, også deler <tex>rb</tex>.
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 <tex>c</tex> og <tex>k_0</tex> slik at <tex>a=bc+k_0</tex> og <tex>0\leq d < |b|</tex>, har vi dermed at
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


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




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


<tex>gcd(a,b)=gcd(b,k_0)=gcd(k_0,k_1)</tex> og så videre.
<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 (<tex>N</tex>) steg komme til et punkt der <tex>k_{N-1}=t*k_{N}</tex>, og vi får da at
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


<tex>\gcd(a,b)=\gcd(k_{N-1},k_N)=\gcd(t\cdot k_N,k_N)=k_N</tex>
<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 a og b være heltall. Da finnes det heltall r,s slik at

ar=bs

og verdien av ar og bs kalles da et felles multiplum av a og b. Det minste felles multiplumet til a og b er det minste slike multiplumet og noteres ved lcm(a,b) (Les: Least common multiple).


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

Sammenheng med primtallsfaktorisering

La a og b ha primtallsfaktoriseringer gitt ved a=p1a1p2a2...pnan og b=p1b1p2b2...pnbn, der ai,bi=0,1,2,.... La så Mi=max(ai,bi) og mi=min(ai,bi).

Da er

lcm(a,b)=p1M1p2M2...pnMn

og

gcd(a,b)=p1m1p2m2...pnmn


Fra denne sammenhengen, og at Mi+mi=ai+bi er det rett frem å vise at

gcd(a,b)lcm(a,b)=ab

Euklids algoritme

Dersom a,b,r er heltall, gjelder gcd(a,b)=gcd(arb,b), fordi alle faktorer som deler b, også deler rb.

Ettersom vi kan finne heltall c og k0 slik at a=bc+k0 og 0d<|b|, har vi dermed at

gcd(a,b)=gcd(b,k0).


Ettersom vi også har b=t0k0+k1 for heltall Missing superscript or subscript argument får vi at

gcd(a,b)=gcd(b,k0)=gcd(k0,k1) og så videre.


Dette er euklids algoritme. Hvis vi fortsetter denne prosessen, vil vi etter et endelig antall (N) steg komme til et punkt der kN1=tkN, og vi får da at

gcd(a,b)=gcd(kN1,kN)=gcd(tkN,kN)=kN