یادگیری الگوریتم اقلیدسی در مدرسه الگوریتم اقلیدس - یافتن بزرگترین مقسوم علیه مشترک
در تجارت الکترونیکی گسترده است. همچنین از این الگوریتم در حل معادلات دیوفانتین خطی، در ساخت کسرهای ادامه دار به روش استورم استفاده شده است. الگوریتم اقلیدس ابزار اصلی برای اثبات قضایای نظریه اعداد مدرن است، مانند قضیه لاگرانژ بر مجموع چهار مربع و قضیه اساسی حساب.
یوتیوب دایره المعارفی
1 / 5
✪ ریاضی اعداد طبیعی: الگوریتم اقلیدس. مرکز آموزش آنلاین فاکسفورد
✪ الگوریتم اقلیدس
✪ الگوریتم اقلیدس، راه سریع gcd را پیدا کنید
✪ ریاضی 71. بزرگترین مقسوم علیه مشترک. الگوریتم اقلیدس - آکادمی علوم سرگرم کننده
✪ 20 while حلقه اقلیدس الگوریتم پایتون
زیرنویس
داستان
ریاضیدانان یونان باستان این الگوریتم را نامیده اند ἀνθυφαίρεσις یا ἀνταναίρεσις - «تفریق متقابل». این الگوریتم توسط اقلیدس کشف نشد، زیرا قبلاً در آن ذکر شده است توپکاارسطو. در «عناصر» اقلیدس، دو بار توصیف شده است - در کتاب هفتم برای یافتن بزرگترین مقسوم علیه مشترک دو عدد طبیعی و در کتاب X برای یافتن بزرگترین معیار مشترک دو کمیت همگن. در هر دو مورد، یک توصیف هندسی از الگوریتم برای یافتن "اندازه مشترک" دو بخش ارائه می شود.
شرح
الگوریتم اقلیدس برای اعداد صحیح
اجازه دهید a (\displaystyle a)و b (\displaystyle b)- اعداد صحیح همزمان با صفر برابر نیستند و دنباله ای از اعداد
a > b > r 1 > r 2 > r 3 > r 4 > … > r n (\displaystyle a>b>r_(1)>r_(2)>r_(3)>r_(4)>\ \dots \ >r_(n))با این واقعیت تعیین می شود که هر یک r k (\displaystyle r_(k))- این باقیمانده تقسیم عدد قبلی بر عدد قبلی است و عدد ماقبل آخر بر عدد آخر تقسیم می شود، یعنی:
a = b q 0 + r 1، (\displaystyle a=bq_(0)+r_(1)،) b = r 1 q 1 + r 2 , (\displaystyle b=r_(1)q_(1)+r_(2)،) r 1 = r 2 q 2 + r 3 , (\displaystyle r_(1)=r_(2)q_(2)+r_(3)،) ⋯ (\displaystyle \cdots) r k − 2 = r k − 1 q k − 1 + r k , (\displaystyle r_(k-2)=r_(k-1)q_(k-1)+r_(k)،) ⋯ (\displaystyle \cdots) r n − 2 = r n − 1 q n − 1 + r n , (\displaystyle r_(n-2)=r_(n-1)q_(n-1)+r_(n) r n − 1 = r n q n . (\displaystyle r_(n-1)=r_(n)q_(n).)سپس gcd( آ, ب) بزرگترین مقسوم علیه مشترک آو ب، برابر است با r n آخرین عضو غیر صفر این دنباله است.
وجود داشتنچنین r 1 , r 2 , ..., r n یعنی امکان تقسیم با باقی مانده متربر nبرای هر کل مترو کل n≠ 0 با استقرا در ثابت می شود متر.
صحتاین الگوریتم از دو عبارت زیر به دست می آید:
- اجازه دهید آ = ب⋅q + r، سپس gcd(a, b) = gcd(b, r).
اثبات
- GCD( r, 0) = rبرای هر غیر صفر r(زیرا 0 بر هر عدد صحیحی غیر از صفر بخش پذیر است).
الگوریتم هندسی اقلیدس
اجازه دهید دو بخش از طول داده شود آو ب. قسمت کوچکتر را از قسمت بزرگتر کم کنید و قسمت بزرگتر را با اختلاف حاصل جایگزین کنید. این عمل را آنقدر تکرار کنید تا قسمت ها برابر شوند. اگر این اتفاق بیفتد، بخش‌های اصلی قابل مقایسه هستند و آخرین بخش به‌دست‌آمده بزرگترین معیار رایج آنهاست. اگر معیار مشترکی وجود نداشته باشد، این فرآیند بی نهایت است. در این فرم الگوریتم توسط اقلیدس توصیف شده و با استفاده از قطب نما و خط کش پیاده سازی شده است.
مثال
برای نشان دادن، از الگوریتم اقلیدس برای یافتن gcd استفاده خواهد شد آ= 1071 و ب= 462. برای شروع، مضربی از 462 را از 1071 کم کنید تا اختلاف کمتر از 462 به دست آوریم. ما باید 462 را دو بار کم کنیم، ( q 0 = 2)، باقی مانده با 147 باقی مانده:
1071 = 2 × 462 + 147.
سپس مضربی از 147 را از 462 کم می کنیم تا اختلاف کمتر از 147 به دست آید. باید 147 را سه بار کم کنیم ( q 1 = 3)، باقی مانده با 21 باقی مانده:
462 = 3 x 147 + 21.
سپس مضرب 21 را از 147 کم می کنیم تا اختلاف کمتر از 21 به دست آید. باید 21 را هفت بار کم کنیم ( q 2 = 7)، بدون باقی مانده باقی می ماند:
147 = 7 × 21 + 0.
بنابراین دنباله a > b > r 1 > r 2 > r 3 > … > r n در این مورد خاص به شکل زیر است:
1071 > 462 > 147 > 21.
از آنجایی که آخرین باقیمانده صفر است، الگوریتم با 21 و gcd(1071, 462) = 21 به پایان می رسد.
به صورت جدولی مراحل به شرح زیر بود:
برنامه های کاربردی
الگوریتم اقلیدس توسعه یافته و رابطه بزوت
فرمول هایی برای r i (\displaystyle r_(i))می توان اینگونه بازنویسی کرد:
r 1 = a + b (− q 0) (\displaystyle r_(1)=a+b(-q_(0))) r 2 = b - r 1 q 1 = a (- q 1) + b (1 + q 1 q 0) (\displaystyle r_(2)=b-r_(1)q_(1)=a(-q_( 1))+b(1+q_(1)q_(0))) ⋮ (\displaystyle \vdots) GCD (a, b) = r n = a s + b t (\displaystyle (a,b)=r_(n)=as+bt)اینجا سو تیکل این نمایش بزرگترین مقسوم علیه مشترک، رابطه Bezout نامیده می شود و اعداد سو تی- ضرایب - Bezu . رابطه بزوت کلیدی در اثبات لم اقلیدس و قضیه اصلی حساب است.
کسرهای ادامه دار
الگوریتم اقلیدس کاملاً با کسرهای ادامه دار مرتبط است. نگرش آ/بیک نمایش کسری ادامه دار را می پذیرد:
a b = [ q 0 ; q 1 , q 2 , ⋯ , q n ] (\displaystyle (\frac (a)(b))=).در این حالت، کسر ادامه یافته بدون جمله آخر برابر است با نسبت ضرایب Bezout. تی/سبا علامت منفی گرفته شده است:
[ q 0 ; q 1 , q 2 , ⋯ , q n − 1 ] = − t s (\displaystyle =-(\frac (t)(s))).دنباله برابری هایی که الگوریتم اقلیدس را تعریف می کنند را می توان به شکل زیر بازنویسی کرد:
a b = q 0 + r 0 b b r 0 = q 1 + r 1 r 0 r 0 r 1 = q 2 + r 2 r 1 ⋮ r k − 2 r k − 1 = q k + r k r k − 1 ⋮ r N − 2 r N − 1 = q N (\displaystyle (\begin(تراز شده)(\frac (a)(b))&=q_(0)+(\frac (r_(0))(b))\\(\frac (b) )(r_(0)))&=q_(1)+(\frac (r_(1))(r_(0)))\\(\frac (r_(0))(r_(1)))& =q_(2)+(\frac (r_(2))(r_(1)))\\&()\ \vdots \\(\frac (r_(k-2))(r_(k-1) ))&=q_(k)+(\frac (r_(k))(r_(k-1)))\\&()\ \vdots \\(\frac (r_(N-2))(r_ (N-1)))&=q_(N)\پایان (تراز شده)))آخرین جمله در سمت راست یک معادله همیشه برابر است با متقابل سمت چپ معادله زیر. بنابراین، دو معادله اول را می توان به شکل زیر ترکیب کرد:
a b = q 0 + 1 q 1 + r 1 r 0 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (r_( 1))(r_(0))))))از تساوی سوم می توان برای جایگزینی مخرج عبارت استفاده کرد r 1 /r 0، دریافت می کنیم:
a b = q 0 + 1 q 1 + 1 q 2 + r 2 r 1 (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\ cfrac (1)(q_(2)+(\cfrac (r_(2))(r_(1))))))))آخرین نسبت باقیمانده r ک /r ک−1 را همیشه می توان با استفاده از تساوی بعدی در دنباله جایگزین کرد و تا آخرین معادله ادامه دهید. نتیجه یک کسر ادامه یافته است:
a b = q 0 + 1 q 1 + 1 q 2 + 1 ⋱ + 1 q N = [ q 0 ; q 1 , q 2 , … , q N ] (\displaystyle (\frac (a)(b))=q_(0)+(\cfrac (1)(q_(1)+(\cfrac (1)(q_ (2)+(\cfrac (1)(\ddots +(\cfrac (1)(q_(N))))))))))=)الگوریتم اقلیدس تعمیم یافته برای چند جمله ای ها
الگوریتم اقلیدس و الگوریتم اقلیدس توسعه یافته به طور طبیعیبه حلقه چند جمله ای تعمیم می دهد ک[ایکس] از یک متغیر روی یک فیلد دلخواه ک، از آنجایی که برای چنین چندجمله ای عمل تقسیم با باقی مانده تعریف شده است. هنگام اجرای الگوریتم اقلیدس برای چند جمله ای ها، مشابه الگوریتم اقلیدس برای اعداد صحیح، دنباله ای از باقیمانده های چند جمله ای (PRS) به دست می آید.
مثال حلقه ز[ایکس]
فرض کنید cont(f) طبق تعریف gcd ضرایب چند جمله‌ای f(x) از Z[x] باشد - محتواچند جمله ای ضریب تقسیم f(x) بر cont(f) نامیده می شود بخش ابتداییچند جمله ای f(x) و با primpart(f(x)) نشان داده می شود. این تعاریف برای یافتن gcd دو چند جمله ای مورد نیاز است p 1 (x)و p 2 (x)در حلقه Z[x]. برای چند جمله ای های روی اعداد صحیح، موارد زیر صادق است:
C o n t ((\displaystyle cont() NODNOD ( c o n t (p 1 (x)) , c o n t (p 2 (x)) ) , (\displaystyle \(cont(p_(1)(x)), cont(p_(2)(x))\),)
P r i m p a r t ((\displaystyle primpart() GCD ( p 1 (x) , p 2 (x) )) = (\displaystyle \(p_(1)(x),p_(2)(x)\))=) GCD (p r i m p a r t (p 1 (x)) , p r i m p a r t (p 2 (x)) ) . (\displaystyle \(primpart(p_(1)(x))،primpart(p_(2)(x))\).)
بنابراین، مسئله یافتن gcd دو چندجمله‌ای دلخواه به مسئله یافتن gcd چندجمله‌ای اولیه کاهش می‌یابد.
بگذارید دو چند جمله‌ای اولیه p 1 (x) و p 2 (x) از Z[x] وجود داشته باشد که رابطه بین توان‌های آنها برقرار است: deg(p 1 (x)) = m و deg (p 2 (x) ) = n، m > n. تقسیم چندجمله‌ای با باقیمانده به معنای تقسیم‌پذیری دقیق بالاترین ضریب سود بر بالاترین ضریب مقسوم‌کننده است؛ در حالت کلی، تقسیم با باقی مانده قابل انجام نیست. بنابراین، یک الگوریتم شبه تقسیم معرفی شده است، که با این وجود به فرد امکان می دهد یک شبه نصاب و یک شبه باقیمانده (prem) به دست آورد، که خود به مجموعه چند جمله ای ها روی اعداد صحیح تعلق دارند.
منظور ما از تقسیم شبه این است که خود تقسیم قبل از ضرب چند جمله ای است. p 1 (x) (\displaystyle p_(1)(x))بر (l c (p 2 (x))) m − n + 1 (\displaystyle (lc(p_(2)(x)))^(m-n+1))، به این معنا که
L c (p 2 (x)) m − n + 1 p 1 (x) = p 2 (x) q (x) + r 2 (x) , deg (r (x))< deg (p 2 (x)) , {\displaystyle lc(p_{2}(x))^{m-n+1}p_{1}(x)=p_{2}(x)q(x)+r_{2}(x),\deg(r(x))<\deg(p_{2}(x)),}
جایی که q (x) (\displaystyle q(x))و r (x) (\displaystyle r(x))- به ترتیب pseudopartial و pseudoresidue.
بنابراین، p 1 (x) , p 2 (x) ∈ Z [ x ] (\displaystyle p_(1)(x),p_(2)(x)\in Z[x])، علاوه بر این درجه (p 1) = n 1 ≥ درجه (p 2) = n 2 (\displaystyle \deg(p_(1))=n_(1)\geq \deg(p_(2))=n_(2) ). سپس الگوریتم اقلیدس شامل مراحل زیر است:
1. محاسبه محتویات GCD:
C:= (\displaystyle c:=) GCD (c o n t (p 1) , c o n t (p 2) ) (\displaystyle \(cont(p_(1)),cont(p_(2))\)).
2. محاسبه قطعات اولیه:
P 1 ' (x) := p r i m p a r t (p 1 (x)) ; (\displaystyle p_(1)"(x):=primpart(p_(1)(x));)
P 2 ' (x) := p r i m p a r t (p 2 (x)) . (\displaystyle p_(2)"(x):=primpart(p_(2)(x)).)
3. ساخت دنباله ای از باقیمانده های چند جمله ای:
P 1 ′ (x) , (\displaystyle p_(1)"(x))
P 2 ′ (x) , (\displaystyle p_(2)"(x))
P 3 (x) := p r e m (p 1 ′ (x) , p 2 ′ (x)) , (\displaystyle p_(3)(x):=prem(p_(1)"(x),p_(2 )"(ایکس)))
P 4 (x) := p r e m (p 2 ′ (x) , p 3 (x)) , (\displaystyle p_(4)(x):=prem(p_(2)"(x),p_(3) (ایکس)))
P 5 (x) := p r e m (p 3 (x) , p 4 (x)) , (\displaystyle p_(5)(x):=prem(p_(3)(x),p_(4)(x ))))
. . . (\displaystyle...)
P h (x) := p r e m (p h − 2 (x) , p h − 1 (x)) . (\displaystyle p_(h)(x):=prem(p_(h-2)(x),p_(h-1)(x)).)
بزرگترین مقسوم علیه مشترک
تعریف 2
اگر عدد طبیعی a بر یک عدد طبیعی $b$ بخش پذیر باشد، $b$ را مقسوم علیه $a$ و عدد $a$ را مضرب $b$ می نامند.
بگذارید $a$ و $b$ اعداد طبیعی باشند. عدد $c$ را برای $a$ و $b$ مقسوم علیه مشترک می نامند.
مجموعه مقسوم علیه های مشترک اعداد $a$ و $b$ متناهی است، زیرا هیچ یک از این مقسوم علیه ها نمی توانند بزرگتر از $a$ باشند. این بدان معنی است که در بین این مقسوم‌گیرنده‌ها بزرگترین مقسوم‌گیرنده وجود دارد که به آن بزرگترین مقسوم‌گیرنده مشترک اعداد $a$ و $b$ می‌گویند و برای نشان دادن آن از علامت استفاده می‌شود:
$gcd \ (a;b) \ یا \ D \ (a;b)$
برای پیدا کردن بزرگترین مقسوم علیه مشترک دو عدد:
- حاصل ضرب اعداد موجود در مرحله 2 را بیابید. عدد حاصل بزرگترین مقسوم علیه مشترک مورد نظر خواهد بود.
مثال 1
gcd اعداد $121$ و $132.$ را پیدا کنید
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
اعدادی را که در بسط این اعداد گنجانده شده اند انتخاب کنید
$242=2\cdot 11\cdot 11$
$132=2\cdot 2\cdot 3\cdot 11$
حاصل ضرب اعداد موجود در مرحله 2 را بیابید. عدد حاصل بزرگترین مقسوم علیه مشترک مورد نظر خواهد بود.
$gcd=2\cdot 11=22$
مثال 2
GCD مونومی های 63$ و 81$ را پیدا کنید.
با توجه به الگوریتم ارائه شده پیدا خواهیم کرد. برای این:
بیایید اعداد را به عوامل اول تجزیه کنیم
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
اعدادی را که در بسط این اعداد گنجانده شده اند انتخاب می کنیم
$63=3\cdot 3\cdot 7$
$81=3\cdot 3\cdot 3\cdot 3$
بیایید حاصل ضرب اعداد یافت شده در مرحله 2 را پیدا کنیم. عدد حاصل بزرگترین مقسوم علیه مشترک مورد نظر خواهد بود.
$gcd=3\cdot 3=9$
می توانید GCD دو عدد را به روش دیگری با استفاده از مجموعه مقسوم علیه اعداد پیدا کنید.
مثال 3
gcd اعداد $48$ و $60$ را پیدا کنید.
راه حل:
مجموعه مقسوم‌کننده‌های $48$: $\left\((\rm 1,2,3.4.6,8,12,16,24,48)\right\)$ را بیابید
حال بیایید مجموعه مقسوم‌کننده‌های $60$:$\ \left\((\rm 1,2,3,4,5,6,10,12,15,20,30,60)\right\)$ را پیدا کنیم
بیایید محل تلاقی این مجموعه ها را پیدا کنیم: $\left\((\rm 1,2,3,4,6,12)\right\)$ - این مجموعه مجموعه مقسوم علیه های مشترک اعداد $48$ و $60 را تعیین می کند. $. بزرگترین عنصر در این مجموعه عدد 12$ خواهد بود. بنابراین بزرگترین مقسوم علیه 48 دلار و 60 دلار 12 دلار است.
تعریف NOC
تعریف 3
مضرب مشترک اعداد طبیعی$a$ و $b$ یک عدد طبیعی است که مضربی از $a$ و $b$ است.
مضرب مشترک اعداد اعدادی هستند که بدون باقیمانده بر اعداد اصلی تقسیم می شوند مثلاً برای اعداد $25$ و $50$ مضرب مشترک اعداد $50,100,150,200$ و غیره خواهد بود.
کمترین مضرب مشترک حداقل مضرب مشترک نامیده می شود و با LCM$(a;b)$ یا K$(a;b)$ نشان داده می شود.
برای پیدا کردن LCM دو عدد، شما نیاز دارید:
- اعداد را به عوامل اول تجزیه کنید
- عواملی که جزء عدد اول هستند را بنویسید و فاکتورهایی را که جزء عدد دوم هستند و به عدد اولی نمی روند به آنها اضافه کنید.
مثال 4
LCM اعداد 99 دلار و 77 دلار را پیدا کنید.
با توجه به الگوریتم ارائه شده پیدا خواهیم کرد. برای این
اعداد را به عوامل اول تجزیه کنید
$99=3\cdot 3\cdot 11$
فاکتورهای موجود در اول را بنویسید
به آنها عواملی را اضافه کنید که جزء دومی هستند و به اولی نمی روند
حاصل ضرب اعداد یافت شده در مرحله 2 را بیابید. عدد حاصل حداقل مضرب مشترک مورد نظر خواهد بود
$LCC=3\cdot 3\cdot 11\cdot 7=693$
تهیه فهرستی از مقسوم‌کننده‌های اعداد اغلب زمان‌بر است. راهی برای یافتن GCD به نام الگوریتم اقلیدس وجود دارد.
عباراتی که الگوریتم اقلیدس بر اساس آنها است:
اگر $a$ و $b$ اعداد طبیعی هستند و $a\vdots b$، آنگاه $D(a;b)=b$
اگر $a$ و $b$ اعداد طبیعی باشند به طوری که $b
با استفاده از $D(a;b)=D(a-b;b)$، می توانیم اعداد مورد نظر را به صورت متوالی کاهش دهیم تا زمانی که به یک جفت عدد برسیم به طوری که یکی از آنها بر دیگری بخش پذیر باشد. سپس کوچکتر از این اعداد، بزرگترین مقسوم علیه مشترک مورد نظر برای اعداد $a$ و $b$ خواهد بود.
ویژگی های GCD و LCM
- هر مضرب مشترک $a$ و $b$ بر K$(a;b)$ بخش پذیر است
- اگر $a\vdots b$، آنگاه K$(a;b)=a$
اگر K$(a;b)=k$ و $m$-عدد طبیعی، K$(am;bm)=km$
اگر $d$ یک مقسوم علیه مشترک برای $a$ و $b$ باشد، آنگاه K($\frac(a)(d);\frac(b)(d)$)=$\ \frac(k)(d ) دلار
اگر $a\vdots c$ و $b\vdots c$ ، آنگاه $\frac(ab)(c)$ مضرب مشترک $a$ و $b$ است.
برای هر اعداد طبیعی $a$ و $b$ برابری
$D(a;b)\cdot K(a;b)=ab$
هر مقسوم علیه مشترک $a$ و $b$ مقسوم علیه $D(a;b)$ است.
الگوریتم اقلیدسراهی برای یافتن بزرگترین مقسوم علیه مشترک (gcd) دو عدد صحیح است. نسخه اصلی الگوریتم، زمانی که GCD با تفریق یافت می شود، توسط اقلیدس (قرن 3 قبل از میلاد) کشف شد. در حال حاضر، تقسیم بیشتر هنگام محاسبه GCD توسط الگوریتم اقلیدس استفاده می شود، زیرا این روش کارآمدتر است.
محاسبه gcd با تقسیم
بزرگترین مقسوم علیه مشترک یک جفت اعداد، بزرگترین عددی است که هر دو عدد جفت را تقسیم می کند. اجازه دهید محاسبه GCD برای اعداد 108 و 72 لازم باشد. الگوریتم محاسبه تقسیم به صورت زیر خواهد بود:
- عدد بزرگتر (تقسیم) را بر عدد کوچکتر (مقسوم کننده) تقسیم کنید: 108 / 72 = 1، باقیمانده 36.
- از آنجایی که باقیمانده برابر با صفر نبود، مقسوم‌کننده را بخش‌پذیر می‌کنیم و باقیمانده را مقسوم‌کننده می‌کنیم: 72 / 36 = 2، باقیمانده 0 است.
- وقتی باقیمانده صفر باشد، مقسوم‌کننده gcd مورد نظر برای جفت اعداد داده شده است. یعنی gcd(108, 72) = 36. در واقع، 108/36 = 3 و 72/36 = 2.
در این الگوریتم تقسیم تا زمانی که باقیمانده صفر شود تکرار می شود. وقتی او می شود GCD مقسوم علیه آخرین تقسیم است. به عنوان مثال، شما می خواهید GCD (106, 16) را پیدا کنید:
- 106 / 16 = 6، باقیمانده 10
- 16/10 = 1، باقیمانده 6
- 10/6 = 1، باقیمانده 4
- 6/4 = 1، باقیمانده 2
- 4/2 = 2، باقیمانده 0
- gcd(106، 16) = 2
محاسبه GCD با تفریق
هنگام یافتن GCD با تفریق، باید به صفر نیز برسد. الگوریتم مشابه روش تقسیم است، فقط در اینجا، در هر مرحله بعدی، زیرآب و تفاوت از مرحله قبل کم و کاهش می یابد. عدد کوچکتر همیشه از عدد بزرگتر کم می شود. این نوع الگوریتم فقط برای اعداد صحیح مثبت مناسب است.
اجازه دهید برای یافتن GCD (108، 72) مورد نیاز باشد:
- 108 - 72 = 36
- 72 - 36 = 36
- 36 - 36 = 0
- gcd(108، 72) = 36
gcd (44، 60) را پیدا کنید:
- 60 - 44 = 16
- 44 - 16 = 28
- 28 - 16 = 12
- 16 - 12 = 4
- 12 - 4 = 8
- 8 - 4 = 4
- 4 - 4 = 0
- gcd(44، 60) = 4
این الگوریتم گاهی اوقات به طور متفاوت توصیف می شود. تفریق زودتر به پایان می رسد، در مرحله ای که یک عدد عدد دیگر را تقسیم می کند. یعنی تفریق را با تست بخش پذیری ترکیب می کنند. سپس پیدا کردن GCD برای 44 و 60 به شکل زیر خواهد بود:
- آیا 44 به طور مساوی 60 را تقسیم می کند؟ خیر 60 - 44 = 16.
- آیا 16 به طور مساوی 44 را تقسیم می کند؟ خیر 44 - 16 = 28.
- آیا 16 به طور مساوی 28 را تقسیم می کند؟ خیر 28 - 16 = 12.
- آیا 12 به طور مساوی 16 را تقسیم می کند؟ خیر 16 - 12 = 4.
- آیا 4 به طور مساوی 12 را تقسیم می کند؟ آره. بنابراین gcd(44، 60) = 4.
توجه داشته باشید، GCD یک ضریب نیست، بلکه یک مقسوم علیه است. اگر در مثال 12 را بر 4 تقسیم کنیم، ضریب 3 را می گیریم. اما این GCD نیست.
اثبات الگوریتم اقلیدس
بیایید این واقعیت را در نظر بگیریم که اگر یک عدد طبیعی از یک جفت، دیگری را تقسیم کند، آنگاه gcd آنها برابر با کوچکتر آنها خواهد بود. می توانید آن را اینگونه بنویسید:
اگر a/b عدد صحیح باشد، gcd(a, b) = b. به عنوان مثال، gcd(15، 5) = 5.
بنابراین، اگر در پایان به یک جفت عدد برسیم که یکی از آنها دیگری را تقسیم می کند، آنگاه عدد کوچکتر بزرگترین مقسوم علیه مشترک برای هر دو خواهد بود. این یک جفت اعداد است که توسط الگوریتم اقلیدس جستجو می شود: یک عدد دیگری را کاملاً تقسیم می کند.
واقعیت دوم لازم است ثابت شود که اگر یک عدد از دیگری بزرگتر باشد، بزرگترین مقسوم علیه مشترک آنها برابر است با بزرگترین مقسوم علیه مشترک برای عدد کوچکتر از جفت و تفاوت بین اعداد بزرگتر و کوچکتر. این را می توان اینگونه نوشت:
اگر یک< b, то НОД(a, b) = НОД(a, b - a).
به صورت زیر می توانیم ثابت کنیم که gcd(a, b) = gcd(a, b - a). بگذارید b - a = c. اگر هر عدد x a و b را تقسیم کند، c را نیز تقسیم خواهد کرد. از این گذشته ، اگر a و b متفاوت باشند ، مقسوم علیه یک عدد صحیح ، اما تعداد دفعات متفاوتی در آنها قرار می گیرد. و اگر یکی را از دیگری کم کنید، مقسوم‌کننده نیز باید یک عدد صحیح را در اختلاف حاصل قرار دهد.
اگر a و b را به طور متوالی کاهش دهیم، دیر یا زود به چنین مقدار کوچکتر از آنها خواهیم رسید که مقدار بزرگتر را کاملاً تقسیم می کند. کوچکتر از چنین جفتی بزرگترین مقسوم علیه مشترک برای جفت اصلی اعداد طبیعی خواهد بود. این همان چیزی است که الگوریتم اقلیدس در مورد آن است.
بیایید دو روش اصلی برای یافتن GCD به دو روش اصلی در نظر بگیریم: با استفاده از الگوریتم اقلیدس و فاکتورگیری. بیایید هر دو روش را برای اعداد دو، سه و بیشتر اعمال کنیم.
الگوریتم اقلیدس برای یافتن GCD
الگوریتم اقلیدس محاسبه بزرگترین مقسوم علیه مشترک دو عدد مثبت را آسان می کند. ما فرمول‌بندی‌ها و اثبات الگوریتم اقلیدس را در بخش Greatest Common Divisor: Determinant, Examples آورده‌ایم.
ماهیت الگوریتم این است که به طور مداوم تقسیم را با باقیمانده انجام دهد، که طی آن یک سری برابری های شکل به دست می آید:
a = b q 1 + r 1 , 0< r 1 < b b = r 1 · q 2 + r 2 , 0 < r 2 < r 1 r 1 = r 2 · q 3 + r 3 , 0 < r 3 < r 2 r 2 = r 3 · q 4 + r 4 , 0 < r 4 < r 3 ⋮ r k - 2 = r k - 1 · q k + r k , 0 < r k < r k - 1 r k - 1 = r k · q k + 1
ما می توانیم تقسیم را در زمانی به پایان برسانیم rk + 1 = 0، که در آن r k = gcd (a، b).
مثال 1
64 و 48 .
راه حل
بیایید نماد را معرفی کنیم: a = 64 , b = 48.
بر اساس الگوریتم اقلیدس، تقسیم را انجام خواهیم داد 64 بر 48 .
ما 1 و بقیه 16 می گیریم. معلوم می شود که q 1 = 1، r 1 = 16.
مرحله دوم تقسیم است 48 در 16، ما 3 را دریافت می کنیم. به این معنا که q2 = 3، آ r 2 = 0.بنابراین، عدد 16 بزرگترین مقسوم علیه مشترک برای اعداد از شرط است.
پاسخ: gcd(64، 48) = 16.
مثال 2
GCD اعداد چیست؟ 111 و 432 ?
راه حل
تقسیم کنید 432 بر 111 . طبق الگوریتم اقلیدس، ما زنجیره برابری های 432 = 111 3 + 99، 111 = 99 1 + 12، 99 = 12 8 + 3، 12 = 3 4 را به دست می آوریم.
بنابراین، بزرگترین مقسوم علیه مشترک اعداد 111 و 432 3 است.
پاسخ: gcd (111، 432) = 3.
مثال 3
بزرگترین مقسوم علیه 661 و 113 را پیدا کنید.
راه حل
ما به ترتیب اعداد را تقسیم می کنیم و GCD را دریافت می کنیم (661 , 113) = 1 . این بدان معناست که 661 و 113 اعداد نسبتا اول هستند. اگر به جدول اعداد اول نگاه کنیم، می‌توانیم این را قبل از شروع محاسبات بفهمیم.
پاسخ: gcd(661، 113) = 1.
یافتن GCD با فاکتورگیری اعداد به فاکتورهای اولیه
برای یافتن بزرگ ترین مقسوم علیه مشترک دو عدد با فاکتورگیری، لازم است تمامی ضرایب اولی که از تجزیه این دو عدد به دست می آیند و با آنها مشترک هستند، ضرب شوند.
مثال 4
اگر اعداد 220 و 600 را به ضرایب اول تجزیه کنیم، دو محصول بدست می آوریم: 220 = 2 2 5 11و 600 = 2 2 2 3 5 5. فاکتورهای مشترک در این دو محصول 2 , 2 و 5 خواهد بود . این به این معنی است که NOD (220، 600) = 2 2 5 = 20.
مثال 5
بزرگترین مقسوم علیه مشترک اعداد را پیدا کنید 72 و 96 .
راه حل
همه عوامل اول اعداد را بیابید 72 و 96 :
72 36 18 9 3 1 2 2 2 3 3
96 48 24 12 6 3 1 2 2 2 2 2 3
فاکتورهای اول رایج برای دو عدد: 2، 2، 2 و 3. این به این معنی است که NOD (72، 96) = 2 2 2 3 = 24.
پاسخ: gcd(72، 96) = 24.
قاعده یافتن بزرگترین مقسوم علیه مشترک دو عدد بر اساس ویژگی های بزرگترین مقسوم علیه مشترک است که طبق آن gcd (m a 1 , m b 1) = m gcd (a 1 , b 1) که m هر عدد صحیح مثبت است. .
یافتن GCD از سه عدد یا بیشتر
صرف نظر از تعداد اعدادی که برای آنها باید GCD را پیدا کنیم، از الگوریتم مشابهی پیروی می کنیم که شامل یافتن GCD دو عدد متوالی است. این الگوریتم مبتنی بر کاربرد قضیه زیر است: GCD چند اعداد a 1 , a 2 , … , a kبرابر عدد است dk، که در محاسبه متوالی gcd یافت می شود (a 1, a 2) = d 2, GCD (d 2 , a 3) = d 3 , GCD (d 3 , a 4) = d 4 , … , GCD (d k - 1 , a k) = d k .
مثال 6
بزرگترین مقسوم علیه چهار عدد 78، 294، 570 و 36 .
راه حل
بیایید نماد را معرفی کنیم: a 1 = 78، a 2 = 294، a 3 = 570، a 4 = 36.
بیایید با پیدا کردن GCD اعداد 78 و 294 شروع کنیم: d2= GCD (78 , 294) = 6 .
اکنون بیایید شروع به یافتن d 3 \u003d GCD (d 2, a 3) \u003d GCD (6, 570) کنیم. طبق الگوریتم اقلیدس 570 = 6 95 .این به آن معنا است d 3 = GCD (6 , 570) = 6 .
d 4 \u003d GCD (d 3, a 4) \u003d GCD (6, 36) را پیدا کنید. 36 بدون باقی مانده بر 6 بخش پذیر است. این به ما اجازه می دهد که به دست آوریم d4= GCD (6 , 36) = 6 .
d4 = 6، یعنی GCD (78 , 294 , 570 , 36) = 6 .
پاسخ:
و اکنون بیایید به روش دیگری برای محاسبه GCD برای آن و تعداد بیشتر نگاه کنیم. ما می‌توانیم gcd را با ضرب همه ضرایب اول مشترک اعداد پیدا کنیم.
مثال 7
gcd اعداد 78، 294، 570 و را محاسبه کنید 36 .
راه حل
بیایید این اعداد را به عوامل اول تجزیه کنیم: 78 = 2 3 13 , 294 = 2 3 7 7 , 570 = 2 3 5 19 , 36 = 2 2 3 3 .
برای هر چهار عدد، ضرایب اول مشترک اعداد 2 و 3 خواهند بود.
معلوم می شود که NOD (78، 294، 570، 36) = 2 3 = 6.
پاسخ: gcd(78، 294، 570، 36) = 6.
پیدا کردن gcd اعداد منفی
اگر باید با اعداد منفی سر و کار داشته باشیم، می توانیم از ماژول های این اعداد برای یافتن بزرگترین مقسوم علیه مشترک استفاده کنیم. ما می توانیم این کار را با دانستن خاصیت اعداد با علائم متضاد انجام دهیم: اعداد nو -nتقسیم کننده های یکسانی دارند
مثال 8
gcd اعداد صحیح منفی را پیدا کنید − 231 و − 140 .
راه حل
برای انجام محاسبات، اجازه دهید ماژول هایی از اعداد داده شده در شرط را در نظر بگیریم. اینها اعداد 231 و 140 خواهند بود. بگذارید به طور خلاصه بگوییم: GCD (− 231 , − 140) = GCD (231، 140). حالا بیایید الگوریتم اقلیدس را برای یافتن ضرایب اول دو عدد اعمال کنیم: 231 = 140 1 + 91 ; 140 = 91 1 + 49; 91 = 49 1 + 42; 49 = 42 1 + 7 و 42 = 7 6. ما دریافت می کنیم که gcd (231، 140) = 7 .
و از آنجایی که NOD (− 231 , − 140) = GCD (231 , 140) ، سپس gcd اعداد − 231 و − 140 برابر است 7 .
پاسخ: gcd (- 231، 140-) = 7.
مثال 9
gcd سه عدد - 585، 81 و را تعیین کنید − 189 .
راه حل
بیایید اعداد منفی در لیست بالا را با مقادیر مطلق آنها جایگزین کنیم، GCD دریافت می کنیم (− 585 , 81 , − 189) = GCD (585 , 81 , 189) . سپس همه اعداد داده شده را به عوامل اول تجزیه می کنیم: 585 = 3 3 5 13، 81 = 3 3 3 3 و 189 = 3 3 3 7. فاکتورهای اول 3 و 3 در سه عدد مشترک هستند. معلوم می شود که gcd (585، 81، 189) = gcd (- 585، 81، - 189) = 9.
پاسخ: GCD (- 585، 81، 189-) = 9.
اگر متوجه اشتباهی در متن شدید، لطفاً آن را برجسته کرده و Ctrl+Enter را فشار دهید
الگوریتم اقلیدس
بزرگترین مقسوم علیه مشترک
مشکل زیر را در نظر بگیرید: نوشتن برنامه ای برای تعیین بزرگترین مقسوم علیه مشترک (GCD) دو عدد طبیعی الزامی است.
بیایید ریاضیات را به یاد بیاوریم. بزرگترین مقسوم علیه مشترک دو عدد طبیعی بزرگترین عدد طبیعی است که بر آن به طور مساوی بخش پذیر هستند. به عنوان مثال اعداد 12 و 18 مقسوم علیه مشترک دارند: 2، 3، 6. بزرگترین مقسوم علیه مشترک 6 است. به این صورت نوشته می شود:
gcd(12، 18) = 6.
داده های اولیه را به صورت M u N نشان دهید. بیان مسئله به صورت زیر است:
داده شده:م، ن
پیدا کردن: GCD (M، N).
در این مورد، هیچ رسمی سازی ریاضی اضافی مورد نیاز نیست. بیان مسئله خود ماهیت ریاضی صوری دارد. هیچ فرمولی برای محاسبه GCD(M, N) از مقادیر M و N وجود ندارد. اما از طرف دیگر، مدتها پیش، بسیار قبل از ظهور رایانه ها، یک روش الگوریتمی برای حل این مشکل شناخته شده بود. . نامیده می شود الگوریتم اقلیدس .
ایده الگوریتم اقلیدس
ایده این الگوریتم بر اساس این ویژگی است که اگر M>N، پس
GCD (M، N) = GCD (M - N، N).
به عبارت دیگر gcd دو عدد طبیعی برابر gcd اختلاف مثبت آنها (مدول اختلاف آنها) و عدد کوچکتر است.
اثبات این ویژگی آسان است. فرض کنید K یک مقسوم علیه مشترک M u N باشد (M > N). این بدان معنی است که M \u003d mK، N \u003d nK، که در آن m، n اعداد طبیعی هستند و m > n. سپس M - N \u003d K (m - n)، که به این معنی است که K مقسوم علیه عدد M - N است. از این رو، همه مقسوم علیه های مشترک اعداد M و N مقسوم علیه تفاوت آنها M - N هستند، از جمله بزرگترین. مقسوم علیه مشترک
خاصیت آشکار دوم:
GCD(M، M) = M.
برای شمارش دستی، الگوریتم اقلیدس به این صورت است:
1) اگر اعداد مساوی هستند، هر یک از آنها را به عنوان پاسخ در نظر بگیرید، در غیر این صورت الگوریتم را ادامه دهید.
2) عدد بزرگتر را با تفاوت بین اعداد بزرگتر و کوچکتر جایگزین کنید.
3) بازگشت به اجرای بند 1.
این الگوریتم را در مثال M=32، N=24 در نظر بگیرید:
ساختار الگوریتم یک حلقه while با انشعاب تو در تو است. چرخه تا زمانی تکرار می شود که مقادیر M و N با یکدیگر برابر شوند. در انشعاب، بزرگتر از دو مقدار با تفاوت آنها جایگزین می شود.
اکنون به جدول ردیابی الگوریتم برای مقادیر اولیه M = 32، N = 24 نگاه کنید.
| گام | عمل | م | ن | وضعیت |
| 1 | ورودی M | 32 | ||
| 2 | ورودی N | 24 | ||
| 3 | M ¹ N | 32 ¹ 24، بله | ||
| 4 | M>N | 32> 24، بله | ||
| 5 | M:=M-N | 8 | ||
| 6 | M ¹ N | 8 ¹ 24، بله | ||
| 7 | M>N | 8> 24، شماره | ||
| 8 | N:=N-M | 16 | ||
| 9 | M ¹ N | 8 ¹ 16، بله | ||
| 10 | M>N | 8> 16، شماره | ||
| 11 | N:=N-M | 8 | ||
| 12 | M ¹ N | 8 ¹ 8، شماره | ||
| 13 | ترمینال M | 8 | ||
| 14 | پایان |
نتیجه نهایی نتیجه صحیح است.
برنامه در AZ و پاسکال
الگوریتم را با هوش مصنوعی و برنامه را با پاسکال می نویسیم.
سوالات و وظایف
1. برنامه Evklid را بر روی کامپیوتر خود اجرا کنید. آن را روی M=32، N=24 تست کنید. M = 696، N = 234.
2. برنامه ای بنویسید تا بزرگترین مقسوم علیه مشترک سه عدد را با استفاده از فرمول زیر پیدا کنید:
gcd(A, B, C) = gcd(gcd(A, B, C).
3. برنامه ای بنویسید تا کمترین مضرب مشترک (LCM) دو عدد را با استفاده از فرمول پیدا کند:
A × B = GCD (A, B) × LCM (A, B).
بارگذاری...
