الگوریتم اقلیدس

الگوریتم اقلیدس روشی موسوم به روش نردبانی یا تقسیمات متوالی برای یافتن بزرگترین مقسوم علیه مشترک (ب.م.م) دو عدد است.

بزرگترین مقسوم علیه مشترک دو عدد a و b را به‌صورت نشان می‌دهند. برای محاسبه عدد بزرگتر را بر عدد کوچکتر تقسیم می کنیم؛ اگر باقی‌مانده صفر بود، پس عدد کوچکتر همان ب.م.م دو عدد است؛ وگرنه عدد کوچکتر را بر باقی‌مانده تقسیم قبلی تقسیم می‌کنیم و این فرایند را تا جایی پیش می‌بریم تا به باقی مانده صفر برسیم.

مثال: برای محاسبهٔ عدد بزرگتر یعنی ۱۸ را بر ۱۲ تقسیم می‌کنیم و سپس ۱۲ را بر باقی ماندهٔ تقسیم قبل (باقی‌مانده ۱۸ تقسیم بر ۱۲ مساوی با ۶ است) تقسیم می‌کنیم. ۱۲ تقسیم بر ۶ باقی‌مانده صفر دارد؛ بنابراین .

اثبات الگوریتم اقلیدس

برای این که ثابت کنیم چرا با الگوریتم فوق ب.م.م به‌دست می‌آید، به لم زیر توجه کنید:

لم: اگر آن‌گاه

اثبات: فرض می‌کنیم و . پس

شبه کد الگوریتم اقلیدسی:
procedure gcd(a,b:positive integers)
x:=a
y:=b
while y≠۰
r:=x mod y
x:=y
y:=r
return x{gcd(a,b)is x}

الگوریتم اقلیدسی از تقسیم‌هایی از مرتبهٔ O(log b) برای پیدا کردن بزرگترین مقسوم علیه‌های مشترک اعداد صحیح a و b استفاده می‌کند که در آن a≥b است.
وقتی الگوریتم اقلیدسی در پیدا کردن a≥b, gcd(a,b) به کار گرفته می‌شود دنبالهٔ تساوی‌های زیر (که در آن a=R0 و b=R1) به دست می‌آید.
R0=R1q1+R2 0≤R2<R1
R1=R2q2+R3 0≤R3<R2
.
.
.
Rn-2=Rn-1qn-1+Rn 0≤Rn>Rn-1
Rn-1=Rnqn
در به‌دست آوردن n , Rn=gcd(a,b) تقسیم به‌کار رفته‌است. دقت کنید که خارج قسمت‌های q1,q2,q3,...qn-1 حداقل ۱ هستند. به علاوه qn≥۲ چون Rn<Rn-1 در نتیجه
Rn≥۱=F2
Rn-1≥2Rn≥2F2=F3
Rn-2≥Rn-1+Rn≥F3+F2=F4
.
.
.
R2≥R3+R4≥Fn-1+Fn-2=Fn
b=R1≥R2+R3≥Fn+Fn-1=Fn+1
بنابراین، در استفاده از الگوریتم اقلیدسی برای پیدا کردن gcd(a,b) با n , a≥b تقسیم به‌کار می‌رود، آنگاه b≥Fn+1.

منابع

Read other articles:

Dewan Perwakilan Rakyat Daerah Kabupaten Tasikmalaya ᮓᮦᮝᮔ᮪ ᮕᮀᮝᮊᮤᮜ᮪ ᮛᮠᮚᮒ᮪ ᮓᮆᮛᮂᮊᮘᮥᮕᮒᮦᮔ᮪ ᮒᮞᮤᮊ᮪ᮙᮜᮚDéwan Pangwakil Rahayat Daérah Kabupatén TasikmalayaDewan Perwakilan RakyatKabupaten Tasikmalaya2019-2024JenisJenisUnikameral Jangka waktu5 tahunSejarahSesi baru dimulai2 September 2019PimpinanKetuaAsep Sopari Al Ayubi, S.P. (Gerindra) sejak 8 Oktober 2019 Wakil Ketua IH. Ami Fahmi, S.T. (PKB) sejak 8 Oktober 2019 Wa...

 

Gusnul Yakin (lahir 17 Maret 1956) adalah pelatih sepak bola berkewarganegaraan Indonesia. Dia adalah mantan pelatih klub Liga Super 2008/09 Arema Malang dari 13 Agustus 2008 hingga 30 Juni 2009.[1] Gusnul merupakan mantan pemain sepak bola. Sebelumnya Gusnul melatih Persibo Bojonegoro dan berhasil membawa klub tersebut menjadi juara Divisi Satu 2007 yang membuat Persibo berkompetisi di Divisi Utama musim 2008. Karier di Arema Malang Menggantikan Bambang Nurdiansyah saat musim kompeti...

 

Dolní Brusnice Dolní Brusnice (Tschechien) Basisdaten Staat: Tschechien Tschechien Region: Královéhradecký kraj Bezirk: Trutnov Fläche: 386 ha Geographische Lage: 50° 27′ N, 15° 44′ O50.457515.728888888889361Koordinaten: 50° 27′ 27″ N, 15° 43′ 44″ O Höhe: 361 m n.m. Einwohner: 393 (1. Jan. 2023)[1] Postleitzahl: 544 72 Kfz-Kennzeichen: H Verkehr Straße: Dvůr Králové nad Labem – Mostek Bahnans...

Wainumá-Marieté Falado(a) em: Colômbia Total de falantes: 0 Família: Arawak Japurá-Colômbia  Wainumá-Marieté Códigos de língua ISO 639-1: -- ISO 639-2: --- O wainumá (ou wainambɨ) e o marieté constituem duas variedades de uma língua extinta da família linguística arawak falada na Colômbia.[1][2] Alguns vocabulários do wainumá foram recolhidos por Spix e Martius em 1820, por Johann Natterer em 1832, e por Alfred Russel Wallace em 1851.[3] Umas palavr...

 

هذه المقالة يتيمة إذ تصل إليها مقالات أخرى قليلة جدًا. فضلًا، ساعد بإضافة وصلة إليها في مقالات متعلقة بها. (أبريل 2019) رالف فينزيل معلومات شخصية تاريخ الميلاد 22 يوليو 1918  الوفاة 6 نوفمبر 2001 (83 سنة)   ليكسينغتون، كنتاكي  مواطنة الولايات المتحدة  الطول 72 بوصة  الوزن 205

 

1993 greatest hits album by The Firesign TheatreShoes For Industry! The Best of the Firesign TheatreGreatest hits album by The Firesign TheatreReleased1993 [1]GenreComedyLength151:10LabelLaugh.comColumbia Records (former) [2]ProducerThe Firesign TheatreThe Firesign Theatre chronology Eat or Be Eaten(1985) Shoes For Industry! The Best of the Firesign Theatre(1993) Back From the Shadows: The Firesign Theatre's 25th Anniversary Reunion Tour(1994) Shoes For Industry: The B...

Internationaler Flughafen KatowiceMiędzynarodowy Port Lotniczy Katowice Das neue Terminal B am Flughafen Katowice Kenndaten ICAO-Code EPKT IATA-Code KTW Koordinaten 50° 28′ 27″ N, 19° 4′ 48″ O50.47425277777819.080019444444303Koordinaten: 50° 28′ 27″ N, 19° 4′ 48″ O Höhe über MSL 303 m  (994 ft) Verkehrsanbindung Entfernung vom Stadtzentrum 34 km nördlich von Katowice Straße Tarnowskie...

 

Taiwanese manga publisher This article does not cite any sources. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Ever Glory Publishing – news · newspapers · books · scholar · JSTOR (February 2018) (Learn how and when to remove this template message) Ever Glory Publishing Co., Ltd.長鴻出版社股份有限公司TypePrivateIndustrypublicationGenremangaFoundedTaina...

 

Emma Grigorievna GersteinNative nameЭ́мма Григо́рьевна Герште́йнBorn12 October 1903 (Julian)DvinskDied29 June 2002 (aged 97)MoscowResting placeVagankovo cemeteryLanguageRussianNationalityRussianAlma materMoscow State UniversityNotable worksMoscow MemoirsNotable awardsRussian Little Booker Prize Anti-Booker prize Emma Grigorievna Gerstein[notes 1] (Rus.: Э́мма Григо́рьевна Герште́йн, born October 25 (12 O.S.), 1903 Dvinsk, Russia...

1964 film directed by José Mojica Marins At Midnight I'll Take Your SoulTheatrical release posterDirected byJosé Mojica MarinsWritten byWaldomiro FrançaJosé Mojica MarinsMagda MeiProduced byArildo IruamGeraldo Martins SimõesIlídio Martins SimõesStarringJosé Mojica MarinsCinematographyGiorgio AttiliEdited byLuiz EliasMusic bySalatiel CoelhoHermínio GimenezProductioncompanyIndústria Cinematográfica ApoloDistributed byN.T.M.Release date 9 November 1964 (1964-11-09) Runn...

 

2014 film by Shinji Aramaki Appleseed AlphaBlu-ray Disc coverDirected byShinji AramakiWritten byMarianne KrawczykBased onAppleseedby Masamune ShirowProduced byJoseph ChouEiichi KamagataMusic byTetsuya TakahashiProductioncompaniesLucent PicturesSola Digital ArtsDistributed byStage 6 FilmsRelease dates July 15, 2014 (2014-07-15) (United States) January 17, 2015 (2015-01-17) (Japan) Running time93 minutesCountriesJapanUnited StatesLanguageEnglish Appleseed A...

 

Annual bike race in Australia Simpson Desert Bike ChallengeSimpson Desert Bike Challenge competitorStatusActiveLocation(s)Simpson DesertCoordinates25°02′48″S 136°44′37″E / 25.0466°S 136.7435°E / -25.0466; 136.7435CountryAustraliaInaugurated1987Most recent2019Organized byDesert Challenge Inc.Websitedesertchallenge.org Simpson Desert Bike Challenge - Fat Bikes are the best tool to tackle the sandy tracks SDBC 2018 - right after the start on day 1 The Simpson ...

Mujair Status konservasi Rentan (IUCN 3.1) Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata Kelas: Actinopterygii Ordo: Perciformes Famili: Cichlidae Genus: Oreochromis Spesies: O. mossambicus Nama binomial Oreochromis mossambicus(W. Peters), 1852 Mujair (Oreochromis mossambicus) adalah sejenis ikan yang biasa dikonsumsi. Penyebaran alami ikan ini adalah perairan Afrika dan di Indonesia pertama kali ditemukan oleh Pak Mujair di muara Sungai Serang pantai selatan Blitar, Jawa Ti...

 

Spanish politician and naturalist (1863–1945) This article relies largely or entirely on a single source. Relevant discussion may be found on the talk page. Please help improve this article by introducing citations to additional sources.Find sources: Odón de Buen y del Cos – news · newspapers · books · scholar · JSTOR (August 2021) Odón de Buen y del Cos Odón de Buen y del Cos (1863 in Zuera, Zaragoza Province, Aragon, Spain – 1945 in Mexico...

 

Company Douwe EgbertsDouwe Egberts building in Utrecht, Netherlands in 2002Product typeBeveragesOwnerJDE Peet'sCountryNetherlandsIntroduced1753MarketsWorldwideTaglineNo ordinary jar. No ordinary coffee.Websitewww.douwe-egberts.com Douwe Egberts is a Dutch brand of coffee which is majority-owned by JDE Peet's. It was founded in Joure, Netherlands, by Egbert Douwes in 1753 as De Witte Os (The White Ox), a general grocery shop. The company later started dealing specifically in coffee, tea, and t...

Village in Haryana, IndiaKhandaVillageKhandaLocation in Haryana, IndiaShow map of HaryanaKhandaKhanda (India)Show map of IndiaCoordinates: 28°55′10″N 76°53′53″E / 28.91944°N 76.89806°E / 28.91944; 76.89806Country IndiaStateHaryanaDistrictSonipatTehsilKharkhodaFounded byPandavaNamed forKhandava ForestGovernment • BodyGram PanchayatArea • Total20.59 km2 (7.95 sq mi)Population (2011)12,000Languages • ...

 

La Temporada 2021 del fútbol boliviano comprende todas las actividades supeditadas por la Federación Boliviana de Fútbol en lo que refiere a las competiciones en las categorías profesional y aficionado, tanto de carácter nacional e internacional, disputadas por clubes bolivianos, y también por las selecciones nacionales de este país, en sus diversas categorías llevadas a cabo durante todo el año 2021, desde el 1 de enero hasta el 31 de diciembre. Campeonatos de Equipos Masculino Torn...

 

2008 North Carolina lieutenant gubernatorial election ← 2004 November 4, 2008 (2008-11-04) 2012 →   Nominee Walter Dalton Robert Pittenger Party Democratic Republican Popular vote 2,133,058 1,915,012 Percentage 51.1% 45.9% County resultsDalton:      40–50%      50–60%      60–70%      70–80%Pittenger:      40–50% ...

Musician, songwriter, arranger, producer (1949–2019) This article is about the musician. For other uses, see Redbone. Leon RedboneRedbone in 2010Background informationBirth nameDickran GobalianBorn(1949-08-26)August 26, 1949[1]Nicosia, British CyprusDiedMay 30, 2019(2019-05-30) (aged 69)New Hope, Pennsylvania, U.S.GenresVaudevilleragtimejazzbluesOccupation(s)Musician, singer, songwriterInstrument(s)Guitar, vocalsYears activeLate 1960s–2015LabelsAugustWarner Bros.AtcoSugar Hil...

 

Indian actress (born 1983) Sanaya IraniIrani in 2016Born (1983-09-17) 17 September 1983 (age 40)[1]Mumbai, IndiaAlma materSydenham College[2]Occupation(s)Actress, dancer, modelYears active2006-presentKnown for Miley Jab Hum Tum Iss Pyaar Ko Kya Naam Doon? Rangrasiya Spouse Mohit Sehgal ​(m. 2016)​[3] Sanaya Irani (born 17 September 1983)[1] is an Indian actress. She is known for playing Gunjan in Miley Jab Hum Tu...

 

Strategi Solo vs Squad di Free Fire: Cara Menang Mudah!