En küçük ortak Kat - Least common multiple

2, 3, 4, 5 ve 7 kombinasyonlarının en küçük ortak katlarını gösteren bir Venn şeması (6, her ikisi de zaten temsil edilen 2 × 3 olduğundan atlanır).
Örneğin, kartlarının en fazla 5 oyuncuya eşit olarak bölünmesini gerektiren bir kart oyunu, en az 60 kart gerektirir; bu sayı 2, 3, 4 ve 5 setin kesişimindeki sayıdır, ancak 7 set değildir.

Olarak aritmetik ve sayı teorisi , en küçük ortak katı , en düşük ortak katı ya da en küçük ortak katı iki tamsayı , bir ve b , genellikle belirtilen, LCM ( a ,  b ) , en küçük pozitif tam sayı olduğu bölünebilir hem a ve b . Tam sayıların sıfıra bölümü tanımsız olduğundan, bu tanım ancak a ve b sıfırdan farklıysa anlam kazanır. Ancak, bazı yazarlar (LCM tanımlayan bir , 0), tüm 0 olarak a olmak LCM alınması sonucu olan, en küçük üst bağlı olarak kafes bölünebilme.

lcm, kesirler toplanmadan, çıkarılmadan veya karşılaştırılmadan önce kullanılabilen " en küçük ortak payda " dır (lcd) . İkiden fazla tamsayının lcm'si de iyi tanımlanmıştır: her biri tarafından bölünebilen en küçük pozitif tamsayıdır.

genel bakış

Bir sayının katı , o sayı ile bir tamsayının çarpımıdır. Örneğin, 10, 5'in katıdır, çünkü 5 × 2 = 10, yani 10, 5 ve 2'ye bölünebilir. 10, hem 5'e hem de 2'ye bölünebilen en küçük pozitif tam sayı olduğundan, 5'in en küçük ortak katıdır ve 2. Aynı prensibe göre, 10 da -5 ve -2'nin en küçük ortak katıdır.

gösterim

İki a ve b tamsayısının en küçük ortak katı lcm( a , b ) olarak gösterilir. Bazı eski ders kitapları [ a , b ]'yi kullanırken, J programlama dilini kullanır a*.b.

Örnek

${\displaystyle \operatöradı {lcm} (4,6)}$

4'ün katları:

${\displaystyle 4,8,12,16,20,24,28,32,36,40,44,48,52,56,60,64,68,72,76,...}$

6'nın katları:

${\displaystyle 6,12,18,24,30,36,42,48,54,60,66,72,...}$

4 ve 6'nın ortak katları , her iki listede de bulunan sayılardır:

${\ Displaystyle 12,24,36,48,60,72,...}$

Bu listede en küçük sayı 12'dir. Dolayısıyla en küçük ortak kat 12'dir.

Uygulamalar

Basit kesirleri toplama, çıkarma veya karşılaştırma sırasında paydaların en küçük ortak katı (genellikle en küçük ortak payda olarak adlandırılır ) kullanılır, çünkü kesirlerin her biri bu payda ile bir kesir olarak ifade edilebilir. Örneğin,

${\displaystyle {2 \21'den fazla}+{1 \6'dan fazla}={4 \42'den fazla}+{7 \42'den fazla}={11 \42'den fazla}}$

burada payda 42 kullanılmıştır, çünkü 21 ve 6'nın en küçük ortak katıdır.

Dişliler sorunu

Bir makinede sırasıyla m ve n dişleri olan iki birbirine geçen dişli olduğunu ve dişlilerin birinci dişlinin merkezinden ikinci dişlinin merkezine çizilen bir çizgi parçası ile işaretlendiğini varsayalım . Dişliler dönmeye başladığında, çizgi segmentini yeniden hizalamak için birinci dişlinin tamamlaması gereken dönüş sayısı kullanılarak hesaplanabilir . Birinci vites , yeniden hizalama için dönüşleri tamamlamalıdır . O zamana kadar ikinci vites dönüş yapmış olacaktır . ${\displaystyle \operatöradı {lcm} (m,n)}$${\displaystyle \operatöradı {lcm} (m,n) \m üzerinde}$${\displaystyle \operatöradı {lcm} (m,n) \n üzerinde}$

Gezegensel hizalama

Bir yıldızın etrafında dönen ve yörüngelerini tamamlamak için sırasıyla l , m ve n birim zaman alan üç gezegen olduğunu varsayalım . l , m ve n'nin tamsayılar olduğunu varsayalım . Gezegenlerin bir ilk lineer hizalanmadan sonra yıldızın etrafında hareket etmeye başladığını varsayarsak, tüm gezegenler zaman birimlerinden sonra tekrar lineer bir hizalamaya ulaşırlar . Şu anda, birinci, ikinci ve üçüncü gezegen tamamlamış olacak , ve yıldızın etrafında sırasıyla yörüngeleri. ${\görüntüleme stili \operatöradı {lcm} (l,m,n)}$${\displaystyle \operatöradı {lcm} (l,m,n) \üzer l}$${\displaystyle \operatöradı {lcm} (l,m,n) \m üzerinde}$${\displaystyle \operatöradı {lcm} (l,m,n) \n üzerinde}$

Hesaplama

En büyük ortak böleni kullanma

Aşağıdaki formül, en küçük ortak çarpanı hesaplama sorununu , aynı zamanda en büyük ortak çarpan olarak da bilinen en büyük ortak böleni (gcd) hesaplama sorununa indirger :

${\displaystyle \operatöradı {lcm} (a,b)={\frac {|ab|}{\gcd(a,b)}}.}$

Bu formül tam olarak biri olduğunda da geçerlidir bir ve b , 0, gcd yana ( a , 0) = | bir |. Her iki Ancak, bir ve b , 0 ile, bu formül neden olur sıfıra bölme ; lcm(0, 0) = 0 özel bir durumdur.

Öklid algoritması gibi sayıların çarpanlara ayrılmasını gerektirmeyen gcd'yi hesaplamak için hızlı algoritmalar vardır . Yukarıdaki örneğe dönecek olursak,

${\displaystyle \operatöradı {lcm} (21,6)={21\cdot 6 \over \gcd(21,6)}={21\cdot 6 \over \gcd(3,6)}={21\cdot 6 \üzerinde 3}={\frac {126}{3}}=42.}$

Gcd (dolayı bir , b ) her ikisinin bir böleni olan a ve b , bölünerek LCM hesaplamak için daha etkilidir önce çarpılması:

${\displaystyle \operatöradı {lcm} (a,b)=\left({|a| \over \gcd(a,b)}\right)\cdot |b|=\left({|b| \over \ gcd(a,b)}\sağ)\cdot |a|.}$

Bu, hem bölme hem de çarpma için bir girdinin boyutunu küçültür ve ara sonuçlar için gereken depolamayı azaltır (yani, a × b hesaplamasında taşma ). Gcd (dolayı bir , b ) her ikisinin bir böleni olan a ve b ara sonuç tam sayı saklanabilir, böylece, bölme, bir tam sayı elde etmek için sağlanmaktadır. Bu şekilde uygulandığında, önceki örnek şöyle olur:

${\displaystyle \operatöradı {lcm} (21,6)={21 \over \gcd(21,6)}\cdot 6={21 \over \gcd(3,6)}\cdot 6={21 \üzer 3}\cdot 6=7\cdot 6=42.}$

Asal çarpanlara ayırmayı kullanma

Benzersiz ayrıştırma teoremi 1'den her pozitif tam sayı ürünü olarak yalnızca tek bir şekilde yazılabilir gösterir asal sayılar . Asal sayılar, birleştirildiğinde bileşik bir sayı oluşturan atomik elementler olarak düşünülebilir .

Örneğin:

${\displaystyle 90=2^{1}\cdot 3^{2}\cdot 5^{1}=2\cdot 3\cdot 3\cdot 5.}$

Burada 90 bileşik sayısı, 2 asal sayısının bir atomundan, 3 asal sayısının iki atomundan ve 5 asal sayısının bir atomundan oluşur.

Bu gerçek, bir dizi sayının lcm'sini bulmak için kullanılabilir.

Örnek: lcm(8,9,21)

Her bir sayıyı çarpanlarına ayırın ve asal sayı kuvvetlerinin çarpımı olarak ifade edin .

${\displaystyle {\begin{aligned}8&=2^{3}\\9&=3^{2}\\21&=3^{1}\cdot 7^{1}\end{aligned}}}$

lcm, her bir asal sayının en yüksek gücünün çarpılmasının ürünü olacaktır. Üç asal sayı olan 2, 3 ve 7'nin en yüksek kuvveti sırasıyla 2 ³ , 3 ² ve 7 ^1'dir . Böylece,

${\displaystyle \operatöradı {lcm} (8,9,21)=2^{3}\cdot 3^{2}\cdot 7^{1}=8\cdot 9\cdot 7=504.}$

Tamsayı çarpanlarına ayırma için bilinen bir genel verimli algoritma olmadığından, bu yöntem en büyük ortak bölene indirgemek kadar verimli değildir .

Aynı yöntem, her dairede gösterilen iki sayının her birinin asal çarpanlarına ayrılması ve kesişmede ortak olarak paylaştıkları tüm faktörler ile aşağıdaki gibi bir Venn şemasıyla da gösterilebilir . Daha sonra lcm, diyagramdaki tüm asal sayıların çarpılmasıyla bulunabilir.

İşte bir örnek:

48 = 2 × 2 × 2 × 2 × 3,

180 = 2 × 2 × 3 × 3 × 5,

iki "2" ve bir "3" ortak payda:

En küçük ortak kat = 2 × 2 × 2 × 2 × 3 × 3 × 5 = 720

En büyük ortak bölen = 2 × 2 × 3 = 12

Bu aynı zamanda en büyük ortak bölen (gcd) için de geçerlidir, ancak Venn şemasındaki tüm sayıları çarpmak yerine yalnızca kesişimdeki asal çarpanları çarpar. Böylece 48 ve 180'in gcd'si 2 × 2 × 3 = 12'dir.

Basit bir algoritma kullanma

Bu yöntem, birkaç tamsayının lcm'sini bulmak için kolayca çalışır.

Sonlu bir pozitif tamsayı dizisi olsun X = ( x ₁ , x ₂ , ..., x _n ), n > 1. Algoritma aşağıdaki adımlarla ilerler: her m adımında X dizisini inceler ve günceller ^{( m )} = ( x ₁ ^{( m )} , x ₂ ^{( m )} , ..., x _{, n} ^{( m )} ), X, ⁽¹⁾ = X , burada X, ^{( m )} olan m, yineleme inci X olduğu, Algoritmanın m adımında X , vb. İncelemenin amacı, X ^{( m )} dizisinin en küçük (belki de birçok elemandan birini) seçmektir . x _{k 0} ^{( m )} öğesinin seçilen öğe olduğunu varsayarsak , X ^{( m +1)} dizisi şu şekilde tanımlanır:

x _k ^{( m +1)} = x _k ^{( m )} , k ≠ k ₀

x _{k 0} ^{( m +1)} = x _{k 0} ^{( m )} + x _{k 0} ⁽¹⁾ .

Diğer bir deyişle, en azından eleman mukabil artar x elemanlarının geri kalanı geçmesi ise X ^{( m )} için X ^{( m + 1)} değişmez.

Algoritma, X ^{( m )} dizisindeki tüm elemanlar eşit olduğunda durur . Ortak değerleri L tam olarak lcm( X ) 'dir.

Örneğin, X = X ⁽¹⁾ = (3, 4, 6) ise, algoritmadaki adımlar şunları üretir:

X ⁽²⁾ = (6, 4, 6)

X ⁽³⁾ = (6, 8, 6)

X ⁽⁴⁾ = (6, 8, 12) - ikinci 6'yı seçerek

X ⁽⁵⁾ = (9, 8, 12)

X ⁽⁶⁾ = (9, 12, 12)

X ⁽⁷⁾ = (12, 12, 12) yani lcm = 12.

Tablo yöntemini kullanma

Bu yöntem herhangi bir sayıda sayı için çalışır. Bir tablodaki tüm sayıları dikey olarak listeleyerek başlayın (bu örnekte 4, 7, 12, 21 ve 42):

İşlem, tüm sayıları 2'ye bölerek başlar. 2 bunlardan herhangi birini eşit olarak bölerse, tablonun en üstündeki yeni bir sütuna 2 yazın ve sağdaki boşluğa her sayının 2'ye bölünmesinin sonucunu yazın. bu yeni sütun. Bir sayı eşit olarak bölünemiyorsa, sayıyı tekrar yazmanız yeterlidir. 2 sayıların hiçbirine eşit olarak bölünmezse, bu prosedürü bir sonraki en büyük asal sayı olan 3 ile tekrarlayın (aşağıya bakın).

Şimdi, 2'nin en az bir sayıyı böldüğünü varsayarak (bu örnekte olduğu gibi), 2'nin tekrar bölünüp bölünmediğini kontrol edin:

2, geçerli sütunda artık herhangi bir sayıyı bölmediğinde, bir sonraki daha büyük asal sayıya bölerek prosedürü tekrarlayın, 3 artık bölmediğinde, sonraki daha büyük asal sayıları deneyin, 5 sonra 7, vb. sayılar 1'e düşürüldü (son asal bölenin altındaki sütun sadece 1'lerden oluşuyor).

Şimdi, lcm'yi elde etmek için üst satırdaki sayıları çarpın. Bu durumda 2×2×3×7=84 olur .

Genel bir hesaplama algoritması olarak, yukarıdakiler oldukça verimsizdir. Bunu asla yazılımda uygulamak istemezsiniz: çok fazla adım atıyor ve çok fazla depolama alanı gerektiriyor. Önce gcd'yi hesaplamak için Euclid'in algoritması kullanılarak ve ardından bölme yoluyla lcm'nin elde edilmesiyle çok daha verimli bir sayısal algoritma elde edilebilir .

formüller

aritmetiğin temel teoremi

Göre aritmetiğin temel teoremi , pozitif bir tamsayı ürünüdür asal sayılar ve bu temsil asal sayıların sipariş özgü kalmıştır:

${\displaystyle n=2^{n_{2}}3^{n_{3}}5^{n_{5}}7^{n_{7}}\cdots =\prod _{p}p^{n_ {P}},}$

burada n ₂ , n ₃ , ... üsleri negatif olmayan tam sayılardır; örneğin, 84 = 2 ² 3 ¹ 5 ⁰ 7 ¹ 11 ⁰ 13 ⁰ ...

Verilen iki pozitif tamsayı ve , bunların en küçük ortak katı ve en büyük ortak bölenleri formüllerle verilir. ${\textstyle a=\prod _{p}p^{a_{p}}}$${\textstyle b=\prod _{p}p^{b_{p}}}$

${\displaystyle \gcd(a,b)=\prod _{p}p^{\min(a_{p},b_{p})}}$

ve

${\displaystyle \operatöradı {lcm} (a,b)=\prod _{p}p^{\max(a_{p},b_{p})}.}$

Dan beri

${\displaystyle \min(x,y)+\max(x,y)=x+y,}$

bu verir

${\displaystyle \gcd(a,b)\operatöradı {lcm} (a,b)=ab.}$

Aslında, negatif üslere izin verilirse, her rasyonel sayı asal sayıların çarpımı olarak benzersiz bir şekilde yazılabilir. Bu yapıldığında, yukarıdaki formüller geçerli kalır. Örneğin:

${\displaystyle {\begin{aligned}4&=2^{2}3^{0},&6&=2^{1}3^{1},&\gcd(4,6)&=2^{1} 3^{0}=2,&\operatöradı {lcm} (4,6)&=2^{2}3^{1}=12.\\[8pt]{\tfrac {1}{3}}& =2^{0}3^{-1}5^{0},&{\tfrac {2}{5}}&=2^{1}3^{0}5^{-1},&\ gcd \left({\tfrac {1}{3}},{\tfrac {2}{5}}\sağ)&=2^{0}3^{-1}5^{-1}={\ tfrac {1}{15}},&\operatöradı {lcm} \left({\tfrac {1}{3}},{\tfrac {2}{5}}\sağ)&=2^{1}3 ^{0}5^{0}=2,\\[8pt]{\tfrac {1}{6}}&=2^{-1}3^{-1},&{\tfrac {3}{ 4}}&=2^{-2}3^{1},&\gcd \left({\tfrac {1}{6}},{\tfrac {3}{4}}\sağ)&=2 ^{-2}3^{-1}={\tfrac {1}{12}},&\operatöradı {lcm} \left({\tfrac {1}{6}},{\tfrac {3}{ 4}}\sağ)&=2^{-1}3^{1}={\tfrac {3}{2}}.\end{hizalı}}}$

kafes-teorik

Pozitif tamsayı olabilir kısmi sıralı bölünebilme için: eğer bir bölme b (olduğundan, eğer B bir bir tamsayı katı arasında bir ) geç bir ≤ b (eşdeğer ya da b ≥ bir ). (Burada ≤'nin genel büyüklük tabanlı tanımının kullanılmadığına dikkat edin.)

Bu sıralamaya göre, pozitif tamsayılar , gcd tarafından verilen karşılama ve lcm tarafından verilen birleşim ile bir kafes haline gelir . Kanıt, biraz sıkıcı olsa da basittir; bu, lcm ve gcd'nin karşılama ve katılma aksiyomlarını karşıladığını kontrol etmek anlamına gelir. lcm ve gcd'yi bu daha genel bağlama yerleştirmek, aralarında bir ikilik oluşturur :

gcd, lcm, ≤ ve ≥ tamsayı değişkenlerini içeren bir formül doğruysa, gcd'yi lcm ile değiştirerek ve ≥'yi ≤ ile değiştirerek elde edilen formül de doğrudur. (Unutmayın ≤ böler olarak tanımlanır).

Aşağıdaki ikili formül çiftleri, genel kafes-teorik özdeşliklerin özel durumlarıdır.

Bu kafesin dağıtıcı olduğu da gösterilebilir ; yani, lcm gcd'ye dağıtır ve gcd, lcm'ye dağıtır:

${\displaystyle \operatöradı {lcm} (a,\gcd(b,c))=\gcd(\operatöradı {lcm} (a,b),\operatöradı {lcm} (a,c)),}$

${\displaystyle \gcd(a,\operatöradı {lcm} (b,c))=\operatöradı {lcm} (\gcd(a,b),\gcd(a,c)).}$

Bu kimlik kendinden çiftlidir:

${\displaystyle \gcd(\operatöradı {lcm} (a,b),\operatöradı {lcm} (b,c),\operatöradı {lcm} (a,c))=\operatöradı {lcm} (\gcd(a) ,b),\gcd(b,c),\gcd(a,c)).}$

Başka

• Let D ürünü olabilir ω ( D (olduğunu) farklı asal sayılar D olan squarefree ).

Sonra

${\displaystyle |\{(x,y)\;:\;\operatör adı {lcm} (x,y)=D\}|=3^{\omega (D)},}$

burada mutlak çubuklar || bir kümenin kardinalitesini gösterir.

• Hiçbiri sıfır değilse , o zaman${\displaystyle a_{1},a_{2},\ldots ,a_{r}}$

${\displaystyle \operatöradı {lcm} (a_{1},a_{2},\ldots ,a_{r})=\operatöradı {lcm} (\operatöradı {lcm} (a_{1},a_{2}, \ldots ,a_{r-1}),a_{r}).}$

değişmeli halkalarda

En küçük ortak kat, genel olarak değişmeli halkalar üzerinde aşağıdaki gibi tanımlanabilir : a ve b , değişmeli bir R halkasının elemanları olsun . Yaygın bir çoklu bir ve b bir elemandır m arasında R , her iki olduğu bir ve b bölme m (, orada mevcut elemanlar X ve Y ve R bu şekilde ax = m ve tarafından = m ). Bir en sık birden bir ve b ortak diğer hiçbir birden için anlamda, en az bir ortak çoklusu olmaktadır n arasında bir ve b , m, böler  n .

Genel olarak, değişmeli bir halkadaki iki elemanın en az ortak katı veya birden fazlası olamaz. Bununla birlikte, elemanların aynı çiftinin her iki en yaygın katları olan iştirak . Bir de tek çarpanlara etki , herhangi iki unsur bir En küçük ortak katı var. Bir de ana doğru etki , en az ortak çoklusu , bir ve b ile oluşturulan idealleri kesiştiği bir jeneratör olarak karakterize edilebilir bir ve b (ideallerin toplama kesişimi bir idealdir).

Ayrıca bakınız

• anormal iptal
• asal tam sayılar
• Chebyshev işlevi

Notlar

Referanslar

• Crandall, Richard; Pomerance, Carl (2001), Asal Sayılar: Hesaplamalı Bir Perspektif , New York: Springer , ISBN 0-387-94777-9
• Hardy, GH; Wright, EM (1979), Sayılar Teorisine Giriş (Beşinci baskı) , Oxford: Oxford University Press , ISBN 978-0-19-853171-5
• Landau, Edmund (1966), İlk Sayı Teorisi , New York: Chelsea
• Long, Calvin T. (1972), Sayı Teorisine Temel Giriş (2. baskı), Lexington: DC Heath and Company , LCCN  77-171950
• Pettofrezzo, Anthony J.; Byrkit, Donald R. (1970), Sayı Teorisinin Elemanları , Englewood Cliffs: Prentice Hall , LCCN  77-81766