اما بسیاری از اعداد طبیعی بر سایر اعداد طبیعی نیز بخش پذیر هستند.
مثلا:
عدد 12 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12 بخش پذیر است.
عدد 36 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12، بر 18، بر 36 بخش پذیر است.
اعدادی که عدد به آنها بر یک کل بخش پذیر است (برای 12 اینها 1، 2، 3، 4، 6 و 12 هستند) نامیده می شوند. مقسوم علیه اعداد. مقسوم علیه یک عدد طبیعی آ- یک عدد طبیعی است که یک عدد معین را تقسیم می کند آبدون هیچ ردی. عدد طبیعی که بیش از دو مقسوم علیه داشته باشد نامیده می شود کامپوزیت. لطفا توجه داشته باشید که اعداد 12 و 36 دارای فاکتورهای مشترک هستند. این اعداد عبارتند از: 1، 2، 3، 4، 6، 12. بزرگترین مقسوم علیه این اعداد 12 است.
مقسوم علیه مشترک دو عدد داده شده آو ب- این عددی است که هر دو عدد داده شده بدون باقیمانده بر آن تقسیم می شوند آو ب. مقسوم علیه مشترک چند اعداد (GCD)عددی است که به عنوان مقسوم علیه هر یک از آنها عمل می کند.
به طور خلاصه بزرگترین مقسوم علیه مشترک اعداد آو باینجوری بنویس:
مثال: GCD (12؛ 36) = 12.
مقسوم علیه اعداد در رکورد حل با حرف بزرگ "D" نشان داده می شود.
مثال:
GCD (7؛ 9) = 1
اعداد 7 و 9 فقط یک مقسوم علیه مشترک دارند - عدد 1. چنین اعدادی نامیده می شوند دوطرفه نخستچی اسلمی.
اعداد همزمان اول- اینها اعداد طبیعی هستند که فقط یک مقسوم علیه مشترک دارند - عدد 1. gcd آنها 1 است.
بزرگترین مقسوم علیه مشترک (GCD)، خواص.
- ویژگی اصلی: بزرگترین مقسوم علیه مشترک مترو nبر هر مقسوم علیه مشترک این اعداد بخش پذیر است. مثال: برای اعداد 12 و 18، بزرگترین مقسوم علیه مشترک 6 است. بر تمام مقسوم علیه های مشترک این اعداد تقسیم می شود: 1، 2، 3، 6.
- نتیجه 1: مجموعه ای از مقسوم علیه های مشترک مترو nمنطبق با مجموعه مقسوم‌کننده‌های GCD ( متر, n).
- نتیجه 2: مجموعه مضرب مشترک مترو nمنطبق با مجموعه چندین LCM ( متر, n).
این به ویژه به این معنی است که برای کاهش یک کسری به شکل غیر قابل تقلیل، باید صورت و مخرج آن را بر gcd تقسیم کنید.
- بزرگترین مقسوم علیه مشترک اعداد مترو nرا می توان به عنوان کوچکترین عنصر مثبت مجموعه از تمام ترکیبات خطی آنها تعریف کرد:
و بنابراین آن را به صورت ترکیبی خطی از اعداد نشان می دهد مترو n:
این نسبت نامیده می شود رابطه بزوتو ضرایب توو v — ضرایب Bezout. ضرایب Bezout به طور موثر توسط الگوریتم اقلیدسی توسعه یافته محاسبه می شود. این عبارت به مجموعه‌ای از اعداد طبیعی تعمیم می‌یابد - معنای آن این است که زیر گروه گروه تولید شده توسط مجموعه چرخه‌ای است و توسط یک عنصر تولید می‌شود: GCD ( آ 1 , آ 2 , … , a n).
بزرگترین مقسوم علیه مشترک (GCD) را محاسبه کنید.
روش های کارآمد برای محاسبه gcd دو عدد می باشد الگوریتم اقلیدسیو دودوییالگوریتم. علاوه بر این، مقدار gcd ( متر,n) را می توان به راحتی محاسبه کرد اگر بسط متعارف اعداد مشخص باشد مترو nبه عوامل اصلی:
که در آن اعداد اول متمایز هستند، و و اعداد صحیح غیر منفی هستند (اگر اعداد اول مربوطه در بسط نباشد، می توانند صفر باشند). سپس GCD ( متر,n) و NOC ( متر,n) با فرمول های زیر بیان می شوند:
اگر بیش از دو عدد وجود داشته باشد: ، gcd آنها با استفاده از الگوریتم زیر پیدا می شود:
- این GCD مورد نظر است.
همچنین برای یافتن بزرگترین مقسوم علیه مشترک، می توانید هر یک از اعداد داده شده را به فاکتورهای اول تبدیل کنید. سپس فقط فاکتورهایی را که در همه اعداد داده شده گنجانده شده است را جداگانه یادداشت کنید. سپس اعداد نوشته شده را با هم ضرب می کنیم - حاصل ضرب بزرگترین مقسوم علیه مشترک است .
بیایید گام به گام به محاسبه بزرگترین مقسوم علیه مشترک نگاه کنیم:
1. مقسوم علیه اعداد را به ضرایب اول تقسیم کنید:
نوشتن محاسبات با استفاده از نوار عمودی راحت است. در سمت چپ خط ابتدا سود سهام را می نویسیم، در سمت راست - تقسیم کننده. سپس در ستون سمت چپ مقادیر ضرایب را یادداشت می کنیم. بیایید بلافاصله با یک مثال توضیح دهیم. بیایید اعداد 28 و 64 را در فاکتورهای اول قرار دهیم.
2. ما در هر دو عدد بر عوامل اول یکسان تأکید می کنیم:
28 = 2 . 2 . 7
64 = 2 . 2 . 2 . 2 . 2 . 2
3. حاصل ضرب ضرایب اول یکسان را پیدا کنید و جواب را بنویسید:
gcd (28؛ 64) = 2. 2 = 4
پاسخ: GCD (28؛ 64) = 4
می توانید مکان GCD را به دو روش رسمی کنید: در یک ستون (همانطور که در بالا انجام شد) یا "در یک ردیف".
اولین راه برای نوشتن GCD:
gcd 48 و 36 را پیدا کنید.
GCD (48؛ 36) = 2. 2. 3 = 12
روش دوم برای نوشتن GCD:
حالا بیایید راه حل جستجوی GCD را در یک خط بنویسیم. gcd 10 و 15 را پیدا کنید.
D (10) = (1، 2، 5، 10)
D (15) = (1، 3، 5، 15)
D (10، 15) = (1، 5)
حال و در ادامه مطلب فرض می کنیم که حداقل یکی از این اعداد غیر صفر است. اگر همه اعداد داده شده برابر با صفر باشند، مقسوم علیه مشترک آنها هر عدد صحیحی است و از آنجایی که تعداد بی نهایت اعداد صحیح وجود دارد، نمی توانیم در مورد بزرگترین آنها صحبت کنیم. بنابراین نمی توان در مورد بزرگترین مقسوم علیه مشترک اعداد که هر کدام برابر با صفر است صحبت کرد.
حالا می توانیم بدهیم تعیین بزرگترین مقسوم علیه مشترکدو عدد
تعریف.
بزرگترین مقسوم علیه مشترکدو عدد صحیح بزرگترین عدد صحیحی است که دو عدد صحیح داده شده را تقسیم می کند.
برای نوشتن مختصر بزرگترین مقسوم علیه مشترک، معمولاً از مخفف GCD استفاده می شود - Greatest Common Divisor. همچنین، بزرگترین مقسوم علیه مشترک دو عدد a و b اغلب با GCD(a,b) نشان داده می شود.
بدهیم مثال بزرگترین مقسوم علیه مشترک (GCD)دو عدد صحیح بزرگترین مقسوم علیه اعداد 6 و -15 3 است. بیایید این را توجیه کنیم. بیایید تمام مقسوم علیه های عدد شش را بنویسیم: ± 6، ± 3، ± 1، و مقسوم علیه های عدد −15 اعداد 15±، 5±، 3± و 1± هستند. اکنون می توانید تمام مقسوم علیه های مشترک اعداد 6 و −15 را پیدا کنید، این اعداد −3، −1، 1 و 3 هستند. از 3-<−1<1<3 , то 3 – это наибольший общий делитель чисел 6 и −15 . То есть, НОД(6, −15)=3 .
تعیین بزرگترین مقسوم علیه مشترک سه یا چند اعداد صحیح شبیه به تعیین gcd دو عدد است.
تعریف.
بزرگترین مقسوم علیه مشترکسه یا چند عدد صحیح بزرگترین عدد صحیحی است که همه اعداد داده شده را همزمان تقسیم می کند.
بزرگترین مقسوم علیه مشترک n عدد صحیح a 1 , a 2 , …, a n را با GCD (a 1 , a 2 , …, a n) نشان خواهیم داد. اگر مقدار b بزرگترین مقسوم علیه مشترک این اعداد پیدا شود، می توانیم بنویسیم GCD(a 1 , a 2 , …, a n)=b.
به عنوان مثال، اجازه دهید gcd چهار عدد صحیح -8، 52، 16 و -12 را بدهیم، برابر با 4 است، یعنی gcd(-8, 52, 16, -12)=4. این را می توان با نوشتن تمام مقسوم علیه اعداد داده شده، انتخاب مشترک از آنها و تعیین بزرگترین مقسوم علیه مشترک بررسی کرد.
توجه داشته باشید که بزرگترین مقسوم علیه مشترک اعداد صحیح می تواند برابر با یکی از این اعداد باشد. اگر همه اعداد داده شده بر یکی از آنها بخش پذیر باشند، این جمله درست است (اثبات در پاراگراف بعدی این مقاله آورده شده است). برای مثال، GCD(15، 60، -45)=15. این درست است، زیرا 15 هم عدد 15 و هم عدد 60 و هم عدد -45 را تقسیم می کند و هیچ مقسوم علیه مشترک اعداد 15، 60 و 45 وجود ندارد که بیشتر از 15 باشد.
اعداد نسبتاً اول - آن دسته از اعداد صحیح که بزرگترین مقسوم علیه مشترک آنها برابر با یک است، جالب توجه هستند.
ویژگی های بزرگترین مقسوم علیه مشترک، الگوریتم اقلیدسی
بزرگترین مقسوم علیه مشترک دارای تعدادی نتایج مشخصه، به عبارت دیگر، تعدادی ویژگی است. اکنون موارد اصلی را لیست می کنیم ویژگی های بزرگترین مقسوم علیه مشترک (GCD)، آنها را در قالب قضایا تنظیم می کنیم و بلافاصله برهان را ارائه می کنیم.
ما تمام خصوصیات بزرگترین مقسوم علیه مشترک را برای اعداد صحیح مثبت فرمول بندی می کنیم و فقط مقسوم علیه های مثبت این اعداد را در نظر می گیریم.
بزرگترین مقسوم علیه مشترک اعداد a و b برابر است با بزرگترین مقسوم علیه مشترک اعداد b و a یعنی gcd(a, b) = gcd(a, b).
این خاصیت GCD مستقیماً از تعریف بزرگترین مقسوم علیه مشترک ناشی می شود.
اگر a بر b بخش پذیر باشد، مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های عدد b به ویژه gcd(a, b)=b منطبق است.
اثبات
هر مقسوم علیه مشترک اعداد a و b مقسوم علیه هر یک از این اعداد از جمله عدد b است. از طرف دیگر، از آنجایی که a مضرب b است، پس هر مقسوم علیه عدد b، مقسوم علیه عدد a است، زیرا بخش پذیری دارای خاصیت گذر است، بنابراین، هر مقسوم علیه عدد b مشترک است. مقسوم‌کننده اعداد a و b این ثابت می کند که اگر a بر b بخش پذیر باشد، مجموعه مقسوم علیه های اعداد a و b با مجموعه مقسوم علیه های یک عدد b منطبق است. و چون بزرگترین مقسوم علیه عدد b خود عدد b است پس بزرگترین مقسوم علیه مشترک اعداد a و b نیز برابر b یعنی gcd(a, b)=b است.
به طور خاص، اگر اعداد a و b مساوی باشند، پس gcd(a, b)=gcd(a, a)=gcd(b, b)=a=b. برای مثال، GCD(132, 132)=132.
خاصیت اثبات شده بزرگترین مقسوم علیه به ما اجازه می دهد که gcd دو عدد را زمانی که یکی از آنها بر دیگری تقسیم می شود، پیدا کنیم. در این حالت GCD برابر با یکی از این اعداد است که بر عدد دیگری تقسیم می شود. به عنوان مثال، GCD(8, 24)=8، زیرا 24 مضرب هشت است.
اگر a=b·q+c، که در آن a، b، c و q اعداد صحیح هستند، مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های مشترک اعداد b و c به ویژه gcd منطبق است. (a, b)=gcd (b, c) .
اجازه دهید این ویژگی GCD را توجیه کنیم.
از آنجایی که تساوی a=b·q+c برقرار است، پس هر مقسوم علیه مشترک اعداد a و b نیز c را تقسیم می‌کند (این از ویژگی‌های بخش‌پذیری ناشی می‌شود). به همین دلیل، هر مقسوم علیه مشترک b و c، a را تقسیم می کند. بنابراین مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های مشترک اعداد b و c منطبق است. به طور خاص، بزرگترین این مقسوم‌کننده‌های مشترک نیز باید منطبق باشد، یعنی برابری زیر GCD(a, b) = GCD(b, c) باید درست باشد.
حال به فرمول بندی و اثبات قضیه می پردازیم که این است الگوریتم اقلیدسی. الگوریتم اقلید به شما امکان می دهد GCD دو عدد را پیدا کنید (به یافتن GCD با استفاده از الگوریتم اقلیدس مراجعه کنید). علاوه بر این، الگوریتم اقلیدس به ما اجازه می‌دهد تا ویژگی‌های زیر را از بزرگترین مقسوم‌گیرنده مشترک اثبات کنیم.
قبل از ارائه فرمول قضیه، توصیه می کنیم حافظه خود را از قضیه از بخش تئوری تجدید کنید، که بیان می کند که سود تقسیمی a را می توان به صورت b q + r نشان داد، جایی که b یک مقسوم علیه است، q عددی صحیح است که ضریب ناقص نامیده می شود. و r یک عدد صحیح است که شرط را برآورده می کند که باقیمانده نامیده می شود.
بنابراین، بگذارید یک سری تساوی برای دو عدد صحیح مثبت غیر صفر a و b صادق باشد 
به پایان می رسد که rk+1 =0 (که اجتناب ناپذیر است، زیرا b>r 1 >r 2 >r 3، ... مجموعه ای از اعداد صحیح کاهشی است، و این سری نمی تواند بیش از تعداد متناهی اعداد مثبت داشته باشد)، سپس r k – این بزرگترین مقسوم علیه مشترک اعداد a و b است، یعنی r k = gcd(a, b) .
اثبات
اجازه دهید ابتدا ثابت کنیم r k مقسوم علیه مشترک اعداد a و b است، پس از آن نشان خواهیم داد که r k فقط یک مقسوم علیه نیست، بلکه بزرگترین مقسوم علیه مشترک اعداد a و b است.
در امتداد برابری های نوشته شده از پایین به بالا حرکت می کنیم. از آخرین برابری می توان گفت که rk-1 بر r k بخش پذیر است. با در نظر گرفتن این واقعیت، و همچنین ویژگی قبلی GCD، تساوی ماقبل آخر rk-2 =r k-1 ·q k +r k به ما امکان می دهد بگوییم که rk-2 بر rk بخش پذیر است، زیرا rk-1 بر r k بخش پذیر است. و r k بر r k بخش پذیر است. بر اساس قیاس، از تساوی سوم از زیر نتیجه می گیریم که rk-3 بر r k بخش پذیر است. و غیره. از تساوی دوم بدست می آوریم که b بر r k بخش پذیر است و از تساوی اول به این نتیجه می رسیم که a بر r k بخش پذیر است. بنابراین r k مقسوم علیه مشترک اعداد a و b است.
باقی مانده است که ثابت کنیم r k = GCD(a, b). برای نشان دادن اینکه هر مقسوم علیه مشترک اعداد a و b کافی است (بگذارید r 0 را نشان دهیم) r k را تقسیم می کند.
ما در امتداد برابری های اصلی از بالا به پایین حرکت خواهیم کرد. با توجه به ویژگی قبلی، از تساوی اول نتیجه می شود که r 1 بر r 0 بخش پذیر است. سپس از تساوی دوم بدست می آوریم که r 2 بر r 0 بخش پذیر است. و غیره. از آخرین تساوی بدست می آوریم که r k بر r 0 بخش پذیر است. بنابراین، r k = GCD(a, b).
از ویژگی در نظر گرفته شده بزرگترین مقسوم علیه مشترک چنین بر می آید که مجموعه مقسوم علیه های مشترک اعداد a و b با مجموعه مقسوم علیه های بزرگترین مقسوم علیه مشترک این اعداد منطبق است. این نتیجه از الگوریتم اقلیدس به ما اجازه می دهد تا همه مقسوم علیه های مشترک دو عدد را به عنوان مقسوم علیه gcd این اعداد پیدا کنیم.
فرض کنید a و b اعداد صحیحی باشند که همزمان با صفر برابر نیستند، سپس اعداد صحیح u 0 و v 0 وجود دارد، پس برابری GCD(a, b)=a·u 0 +b·v 0 درست است. آخرین تساوی یک نمایش خطی از بزرگترین مقسوم علیه مشترک اعداد a و b است، این تساوی را رابطه Bezout و اعداد u 0 و v 0 را ضرایب Bezout می نامند.
اثبات
با استفاده از الگوریتم اقلیدسی می توانیم برابری های زیر را بنویسیم
از تساوی اول، r 1 =a−b·q 1 داریم، و با نشان دادن 1=s 1 و −q 1 =t 1، این تساوی به شکل r 1 =s 1 ·a+t 1 ·b و اعداد s 1 و t 1 اعداد صحیح هستند. سپس از برابری دوم r 2 =b−r 1 ·q 2 = به دست می آوریم b−(s 1 ·a+t 1 ·b)·q 2 =−s 1 ·q 2 ·a+(1−t 1 ·q 2)·b. با نشان دادن −s 1 ·q 2 =s 2 و 1−t 1 ·q 2 =t 2، آخرین تساوی را می توان به صورت r 2 =s 2 ·a+t 2 ·b نوشت و s 2 و t 2 اعداد صحیح هستند. (چون مجموع، تفاوت و حاصلضرب اعداد صحیح یک عدد صحیح است). به همین ترتیب، از تساوی سوم r 3 =s 3 ·a+t 3 ·b، از تساوی چهارم r 4 =s 4 ·a+t 4 ·b و غیره به دست می آوریم. در نهایت، r k =s k ·a+t k ·b، که در آن s k و t k اعداد صحیح هستند. از آنجایی که r k =GCD(a,b) و نشان دهنده s k =u 0 و t k =v 0 است، یک نمایش خطی از GCD به شکل مورد نیاز بدست می آوریم: GCD(a, b)=a·u 0 +b·v 0 .
اگر m هر عدد طبیعی باشد، پس GCD(m a, m b)=m GCD(a, b).
دلیل این خاصیت بزرگترین مقسوم علیه مشترک به شرح زیر است. اگر دو طرف هر یک از تساوی های الگوریتم اقلیدسی را در m ضرب کنیم، به دست می آوریم که GCD(m·a, m·b)=m·r k و r k GCD(a, b) است. از این رو، GCD(m a, m b)=m GCD(a, b).
روش یافتن GCD با استفاده از فاکتورسازی اول بر اساس این ویژگی بزرگترین مقسوم علیه مشترک است.
فرض کنید p هر مقسوم علیه مشترک اعداد a و b باشد، پس gcd(a:p، b:p)=gcd(a، b):p، به ویژه، اگر p=GCD(a, b) داشته باشیم gcd(a:gcd(a, b), b:gcd(a, b))=1یعنی اعداد a:GCD(a,b) و b:GCD(a,b) نسبتا اول هستند.
از آنجایی که a=p·(a:p) و b=p·(b:p) و با توجه به خاصیت قبلی، می توانیم زنجیره ای از برابری های شکل را بنویسیم. GCD(a, b)=GCD(p (a:p)، p (b:p))= p·GCD(a:p، b:p)، که از آن برابری اثبات شده به دست می آید.
خاصیت بزرگترین مقسوم علیه مشترک که ما به تازگی ثابت کردیم اساس .
حال بیایید در مورد ویژگی GCD صحبت کنیم، که مشکل پیدا کردن بزرگترین مقسوم‌عام مشترک سه یا چند عدد را به یافتن متوالی GCD دو عدد کاهش می‌دهد.
بزرگترین مقسوم علیه مشترک اعداد a 1 , a 2 , ... a k برابر است با عدد d k که با محاسبه متوالی 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.
این اثبات بر اساس نتیجه ای از الگوریتم اقلیدسی است. مقسوم علیه های مشترک اعداد a 1 و a 2 با مقسوم علیه های d 2 منطبق است. سپس مقسوم علیه های مشترک اعداد a 1، a 2 و a 3 با مقسوم علیه های مشترک اعداد d 2 و a 3 منطبق می شوند، بنابراین با مقسوم علیه های d 3 منطبق می شوند. مقسوم علیه های مشترک اعداد a 1، a 2، a 3 و a 4 با مقسوم علیه های مشترک d 3 و a 4 منطبق است، بنابراین با مقسوم علیه های d 4 منطبق هستند. و غیره. در نهایت، مقسوم علیه های مشترک اعداد a 1، a 2، ...، a k با مقسوم علیه های d k منطبق می شوند. و چون بزرگترین مقسوم علیه عدد d k خود عدد d k است، پس GCD(a 1 , a 2 , …, a k)=d k.
این بررسی ما را در مورد ویژگی های اصلی بزرگترین مقسوم علیه مشترک به پایان می رساند.
کتابشناسی - فهرست کتب.
- ویلنکین N.Ya. و دیگران. ریاضیات. پایه ششم: کتاب درسی موسسات آموزش عمومی.
- وینوگرادوف I.M. مبانی نظریه اعداد.
- میخلوویچ ش.ح. نظریه اعداد
- کولیکوف ال.یا. و دیگران مجموعه مسائل جبر و نظریه اعداد: کتاب درسی برای دانشجویان فیزیک و ریاضی. تخصص های موسسات آموزشی.
این مقاله در مورد پیدا کردن بزرگترین مقسوم علیه مشترک (GCD)دو یا چند عدد ابتدا، بیایید به الگوریتم اقلیدس نگاهی بیندازیم؛ این الگوریتم به شما امکان می دهد gcd دو عدد را پیدا کنید. پس از این، ما بر روی روشی تمرکز خواهیم کرد که به ما امکان می دهد gcd اعداد را به عنوان حاصل ضرب ضرایب اول مشترک آنها محاسبه کنیم. در مرحله بعد، ما به یافتن بزرگترین مقسوم علیه مشترک سه یا چند اعداد می پردازیم و همچنین مثال هایی از محاسبه gcd اعداد منفی ارائه می دهیم.
پیمایش صفحه.
الگوریتم اقلیدسی برای یافتن GCD
توجه داشته باشید که اگر از همان ابتدا به جدول اعداد اول رجوع می کردیم، متوجه می شدیم که اعداد 661 و 113 اعداد اول هستند که بلافاصله می توان گفت بزرگترین مقسوم علیه مشترک آنها 1 است.
پاسخ:
GCD(661, 113)=1.
یافتن GCD با فاکتورسازی اعداد به عوامل اول
بیایید راه دیگری را برای یافتن GCD در نظر بگیریم. بزرگترین مقسوم علیه مشترک را می توان با فاکتورگیری اعداد به ضرایب اول پیدا کرد. بیایید یک قانون تنظیم کنیم: gcd دو عدد صحیح مثبت a و b برابر است با حاصلضرب همه ضرایب اول مشترک موجود در فاکتورسازی اول اعداد a و b..
بیایید برای توضیح قانون یافتن GCD مثالی بزنیم. تجزیه اعداد 220 و 600 را به ضرایب اول بدانیم، آنها به شکل 220=2·2·5·11 و 600=2·2·2·3·5·5 هستند. فاکتورهای اول متداول در فاکتورگیری اعداد 220 و 600 عبارتند از 2، 2 و 5. بنابراین، GCD(220، 600)=2·2·5=20.
بنابراین، اگر اعداد a و b را در ضرایب اول قرار دهیم و حاصلضرب همه عوامل مشترک آنها را پیدا کنیم، آنگاه بزرگترین مقسوم علیه مشترک اعداد a و b را پیدا می کنیم.
بیایید نمونه ای از یافتن GCD را طبق قانون بیان شده در نظر بگیریم.
مثال.
بزرگترین مقسوم علیه مشترک اعداد 72 و 96 را پیدا کنید.
راه حل.
بیایید اعداد 72 و 96 را در فاکتورهای اول فاکتور کنیم: 
یعنی 72=2·2·2·3·3 و 96=2·2·2·2·2·2·3. فاکتورهای اول رایج 2، 2، 2 و 3 هستند. بنابراین، GCD(72، 96)=2·2·2·3=24.
پاسخ:
GCD(72، 96)=24.
در پایان این پاراگراف، متذکر می شویم که اعتبار قانون فوق برای یافتن GCD از خاصیت بزرگترین مقسوم علیه مشترک ناشی می شود که بیان می کند که GCD(m a 1 , m b 1) = m GCD (a 1 , b 1)، جایی که m هر عدد صحیح مثبت است.
یافتن gcd سه یا چند عدد
یافتن بزرگترین مقسوم علیه مشترک سه یا چند عدد را می توان به یافتن متوالی gcd دو عدد تقلیل داد. ما در هنگام مطالعه خواص GCD به این موضوع اشاره کردیم. در آنجا این قضیه را فرموله و ثابت کردیم: بزرگترین مقسوم علیه مشترک چند عدد a 1, a 2, ..., a k برابر است با عدد d k که با محاسبه متوالی 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.
بیایید ببینیم که فرآیند یافتن gcd چند عدد با نگاه کردن به حل مثال چگونه است.
مثال.
بزرگترین عامل مشترک چهار عدد 78، 294، 570 و 36 را بیابید.
راه حل.
در این مثال، 1 = 78، 2 = 294، 3 = 570، 4 = 36.
ابتدا با استفاده از الگوریتم اقلیدسی بزرگترین مقسوم علیه مشترک d 2 از دو عدد اول 78 و 294 را تعیین می کنیم. هنگام تقسیم، برابری های 294 = 78 3 + 60 را بدست می آوریم. 78=60·1+18 ; 60=18·3+6 و 18=6·3. بنابراین، d 2 = GCD (78، 294) = 6.
حالا بیایید محاسبه کنیم d 3 =GCD(d 2, a 3)=GCD(6, 570). بیایید دوباره الگوریتم اقلیدسی را اعمال کنیم: 570=6·95، بنابراین، d 3 = GCD(6, 570)=6.
باقی مانده است که محاسبه شود d 4 =GCD(d 3, a 4)=GCD(6, 36). از آنجایی که 36 بر 6 بخش پذیر است، پس d 4 = GCD(6, 36) = 6.
بنابراین، بزرگترین مقسوم علیه مشترک چهار عدد داده شده d 4 = 6 است، یعنی gcd(78, 294, 570, 36)=6.
پاسخ:
GCD(78، 294، 570، 36)=6.
فاکتورگیری اعداد به فاکتورهای اول به شما امکان می دهد gcd سه یا چند عدد را محاسبه کنید. در این حالت، بزرگترین مقسوم علیه مشترک حاصلضرب همه ضرایب اول مشترک اعداد داده شده است.
مثال.
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 هستند. از این رو، GCD(78، 294، 570، 36)=2·3=6.
ماشین حساب آنلاین به شما امکان می دهد تا به سرعت بزرگترین مقسوم علیه مشترک و کمترین مضرب مشترک را برای دو یا هر تعداد دیگری از اعداد پیدا کنید.
ماشین حساب برای پیدا کردن GCD و LCM
GCD و LOC را پیدا کنید
GCD و LOC پیدا شد: 5806
نحوه استفاده از ماشین حساب
- اعداد را در قسمت ورودی وارد کنید
- اگر کاراکترهای نادرست وارد کنید، قسمت ورودی با رنگ قرمز برجسته می شود
- روی دکمه "یافتن GCD and LOC" کلیک کنید
نحوه وارد کردن اعداد
- اعداد با فاصله، نقطه یا کاما وارد می شوند
- طول اعداد وارد شده محدود نیستبنابراین یافتن GCD و LCM اعداد طولانی دشوار نیست
GCD و NOC چیست؟
بزرگترین مقسوم علیه مشترکچند عدد بزرگترین عدد صحیح طبیعی است که تمام اعداد اصلی بدون باقی مانده بر آن بخش پذیرند. بزرگترین مقسوم علیه مشترک به اختصار به عنوان GCD.
کمترین مضرب مشترکچند عدد کوچکترین عددی است که بر هر یک از اعداد اصلی بدون باقیمانده بخش پذیر است. کمترین مضرب مشترک به اختصار به صورت اختصاری بیان می شود NOC.
چگونه می توان بررسی کرد که یک عدد بدون باقی مانده بر عدد دیگری بخش پذیر است؟
برای اینکه بفهمید آیا یک عدد بدون باقیمانده بر عدد دیگر بخش پذیر است یا خیر، می توانید از ویژگی های بخش پذیری اعداد استفاده کنید. سپس با ترکیب آنها می توانید تقسیم پذیری برخی از آنها و ترکیب آنها را بررسی کنید.
برخی از نشانه های تقسیم پذیری اعداد
1. تست بخش پذیری عدد بر 2
برای تعیین اینکه آیا یک عدد بر دو بخش پذیر است (خواه زوج باشد)، کافی است به آخرین رقم این عدد نگاه کنیم: اگر برابر با 0، 2، 4، 6 یا 8 باشد، آنگاه عدد زوج است. یعنی بر 2 بخش پذیر است.
مثال:تعیین کنید که آیا عدد 34938 بر 2 بخش پذیر است یا خیر.
راه حل:ما به رقم آخر نگاه می کنیم: 8 - یعنی عدد بر دو بخش پذیر است.
2. تست بخش پذیری عدد بر 3
عددی بر 3 بخش پذیر است که مجموع ارقام آن بر سه بخش پذیر باشد. بنابراین، برای تعیین اینکه آیا یک عدد بر 3 بخش پذیر است یا خیر، باید مجموع ارقام را محاسبه کنید و بررسی کنید که آیا بر 3 بخش پذیر است یا خیر.
مثال:تعیین کنید که آیا عدد 34938 بر 3 بخش پذیر است یا خیر.
راه حل:مجموع اعداد را می شماریم: 3+4+9+3+8 = 27. 27 بر 3 بخش پذیر است، یعنی عدد بر سه بخش پذیر است.
3. تست بخش پذیری عدد بر 5
یک عدد زمانی بر 5 بخش پذیر است که آخرین رقم آن صفر یا پنج باشد.
مثال:تعیین کنید که آیا عدد 34938 بر 5 بخش پذیر است یا خیر.
راه حل:به رقم آخر نگاه کنید: 8 یعنی عدد بر پنج بخش پذیر نیست.
4. تست بخش پذیری عدد بر 9
این علامت بسیار شبیه به علامت بخش پذیری بر سه است: عددی بر 9 بخش پذیر است که مجموع ارقام آن بر 9 بخش پذیر باشد.
مثال:تعیین کنید که آیا عدد 34938 بر 9 بخش پذیر است یا خیر.
راه حل:مجموع اعداد را می شماریم: 3+4+9+3+8 = 27. 27 بر 9 بخش پذیر است، یعنی عدد بر 9 بخش پذیر است.
چگونه GCD و LCM دو عدد را پیدا کنیم
چگونه gcd دو عدد را پیدا کنیم
ساده ترین راه برای محاسبه بزرگ ترین مقسوم علیه مشترک دو عدد این است که تمام مقسوم علیه های ممکن آن اعداد را پیدا کنید و بزرگ ترین آنها را انتخاب کنید.
بیایید این روش را با استفاده از مثال یافتن GCD (28, 36) در نظر بگیریم:
- هر دو عدد را فاکتور می کنیم: 28 = 1·2·2·7, 36 = 1·2·2·2·3·3
- ما عوامل مشترکی را پیدا می کنیم، یعنی آنهایی که هر دو عدد دارند: 1، 2 و 2.
- ما حاصل ضرب این عوامل را محاسبه می کنیم: 1 2 2 = 4 - این بزرگترین مقسوم علیه مشترک اعداد 28 و 36 است.
چگونه LCM دو عدد را پیدا کنیم
دو روش متداول برای یافتن مضرب حداقل دو عدد وجود دارد. روش اول این است که می توانید مضرب های اول دو عدد را یادداشت کنید و سپس از بین آنها عددی را انتخاب کنید که برای هر دو عدد مشترک و در عین حال کوچکترین باشد. و دوم پیدا کردن gcd این اعداد. بیایید فقط آن را در نظر بگیریم.
برای محاسبه LCM، باید حاصل ضرب اعداد اصلی را محاسبه کنید و سپس آن را بر GCD که قبلا پیدا شده بود تقسیم کنید. بیایید LCM را برای همان اعداد 28 و 36 پیدا کنیم:
- حاصل ضرب اعداد 28 و 36 را بیابید: 28·36 = 1008
- GCD(28, 36)، همانطور که قبلاً شناخته شده است، برابر با 4 است
- LCM(28، 36) = 1008 / 4 = 252.
یافتن GCD و LCM برای چندین اعداد
بزرگترین مقسوم علیه مشترک را می توان برای چندین اعداد یافت، نه فقط دو. برای انجام این کار، اعدادی که برای بزرگترین مقسوم علیه مشترک پیدا می شوند به ضرایب اول تجزیه می شوند، سپس حاصل ضرب ضرایب اول مشترک این اعداد پیدا می شود. همچنین می توانید از رابطه زیر برای یافتن gcd چندین عدد استفاده کنید: GCD(a, b, c) = GCD(GCD(a, b, c).
یک رابطه مشابه برای کمترین مضرب مشترک اعمال می شود: LCM(a, b, c) = LCM(LCM(a, b, c)
مثال: GCD و LCM را برای اعداد 12، 32 و 36 پیدا کنید.
- ابتدا بیایید اعداد را فاکتورسازی کنیم: 12 = 1·2·2·3, 32 = 1·2·2·2·2·2, 36 = 1·2·2·2·3·3.
- بیایید عوامل مشترک را پیدا کنیم: 1، 2 و 2.
- محصول آنها GCD می دهد: 1·2·2 = 4
- حالا بیایید LCM را پیدا کنیم: برای انجام این کار، ابتدا LCM (12, 32) را پیدا می کنیم: 12·32 / 4 = 96.
- برای پیدا کردن LCM هر سه عدد، باید GCD(96, 36) را پیدا کنید: 96 = 1·2·2·2·2·2·3 , 36 = 1·2·2·3·3 , GCD = 1·2· 2 3 = 12.
- LCM(12، 32، 36) = 96·36 / 12 = 288.
بسیاری از مقسم
بیایید مشکل زیر را در نظر بگیریم: مقسوم علیه عدد 140 را پیدا کنید. بدیهی است که عدد 140 یک مقسوم علیه ندارد، بلکه چندین مقسوم علیه دارد. در چنین مواردی گفته می شود که مشکل وجود دارد یک دسته ازتصمیمات بیایید همه آنها را پیدا کنیم. اول از همه، بیایید این عدد را به عوامل ساده تبدیل کنیم:
140 = 2 ∙ 2 ∙ 5 ∙ 7.
حالا به راحتی می توانیم تمام مقسوم علیه ها را بنویسیم. بیایید با عوامل اول شروع کنیم، یعنی عواملی که در بسط داده شده در بالا وجود دارند:
سپس آنهایی را که از ضرب جفتی مقسوم علیه های اول به دست می آیند را یادداشت می کنیم:
2∙2 = 4, 2∙5 = 10, 2∙7 = 14, 5∙7 = 35.
سپس - آنهایی که شامل سه مقسوم علیه اول هستند:
2∙2∙5 = 20, 2∙2∙7 = 28, 2∙5∙7 = 70.
در نهایت، بیایید واحد و خود عدد تجزیه شده را فراموش نکنیم:
همه مقسوم‌کننده‌هایی که پیدا کردیم شکل می‌گیرند یک دسته ازمقسوم‌کننده‌های عدد 140 که با استفاده از پرانتز نوشته می‌شود:
مجموعه مقسوم علیه های عدد 140 =
{1, 2, 4, 5, 7, 10, 14, 20, 28, 35, 70, 140}.
برای سهولت درک، مقسوم‌کننده‌ها را در اینجا یادداشت کرده‌ایم ( عناصر مجموعه) به ترتیب صعودی، اما، به طور کلی، این ضروری نیست. علاوه بر این، ما یک علامت اختصاری را معرفی می کنیم. به جای «مجموعه مقسوم‌کننده‌های عدد 140» می‌نویسیم «D(140)». بدین ترتیب،
به همین ترتیب، می توانید مجموعه مقسوم علیه هر عدد طبیعی دیگری را پیدا کنید. به عنوان مثال، از تجزیه
105 = 3 ∙ 5 ∙ 7
ما گرفتیم:
D(105) = (1، 3، 5، 7، 15، 21، 35، 105).
از مجموعه همه مقسوم علیه ها باید مجموعه مقسوم علیه های ساده را تشخیص داد که برای اعداد 140 و 105 به ترتیب برابر هستند:
PD(140) = (2، 5، 7).
PD(105) = (3، 5، 7).
به ویژه باید تأکید کرد که در تجزیه عدد 140 به عوامل اول، این دو دو بار ظاهر می شوند، در حالی که در مجموعه PD(140) تنها یک وجود دارد. مجموعه PD(140) در اصل، تمام پاسخ های مسئله است: "ضریب اول عدد 140 را بیابید." واضح است که همان پاسخ را نباید بیش از یک بار تکرار کرد.
کسر کسرها. بزرگترین مقسوم علیه مشترک
کسری را در نظر بگیرید
می دانیم که این کسر را می توان با عددی کاهش داد که هم مقسوم کننده صورت (105) و هم مقسوم علیه مخرج (140) باشد. بیایید نگاهی به مجموعه های D(105) و D(140) بیندازیم و عناصر مشترک آنها را یادداشت کنیم.
D(105) = (1، 3، 5، 7، 15، 21، 35، 105)؛
D(140) = (1، 2، 4، 5، 7، 10، 14، 20، 28، 35، 70، 140).
عناصر مشترک مجموعه های D(105) و D(140) =
آخرین برابری را می توان به طور خلاصه تر نوشت، یعنی:
D(105) ∩ D(140) = (1، 5، 7، 35).
در اینجا نماد ویژه "∩" ("کیف با سوراخ پایین") نشان می دهد که از بین دو مجموعه ای که در طرف مقابل آن نوشته شده است، فقط عناصر مشترک باید انتخاب شوند. مدخل "D(105) ∩ D(140)" می‌خواند: تقاطعمجموعه De از 105 و De از 140.
[در طول مسیر توجه داشته باشید که می توانید عملیات باینری مختلف را با مجموعه ها انجام دهید، تقریباً مانند اعداد. یکی دیگر از عملیات دودویی رایج این است اتحاد. اتصال، که با نماد "∪" ("کیف با سوراخ رو به بالا") نشان داده می شود. اتحاد دو مجموعه شامل تمام عناصر هر دو مجموعه است:
PD(105) = (3، 5، 7);
PD(140) = (2، 5، 7);
PD(105) ∪ PD(140) = (2، 3، 5، 7). ]
بنابراین، ما متوجه شدیم که کسری
را می توان با هر یک از اعداد متعلق به مجموعه کاهش داد
D(105) ∩ D(140) = (1، 5، 7، 35)
و با هیچ عدد طبیعی دیگری قابل کاهش نیست. در اینجا همه میانبرهای ممکن وجود دارد (به جز کوتاه کردن جالب یک مورد):
بدیهی است که کاهش کسری به عددی که تا حد امکان بزرگتر باشد بسیار کاربردی است. در این مورد، این عدد 35 است که گفته می شود بزرگترین مقسوم علیه مشترک (GCD) اعداد 105 و 140. این به صورت نوشته می شود
GCD(105، 140) = 35.
با این حال، در عمل، اگر دو عدد به ما داده شود و باید بزرگترین مقسوم علیه مشترک آنها را پیدا کنیم، اصلاً نباید مجموعه ای بسازیم. کافی است به سادگی هر دو عدد را به عوامل اول تجزیه کنیم و عواملی از این عوامل را که در هر دو تجزیه مشترک هستند برجسته کنیم، برای مثال:
105 = 3 ∙ 5 ∙ 7 ;
140 = 2 ∙ 2 ∙ 5 ∙ 7 .
با ضرب اعداد زیر خط کشیده شده (در هر یک از بسط ها)، به دست می آید:
gcd(105، 140) = 5 ∙ 7 = 35.
البته این امکان وجود دارد که بیش از دو عامل برجسته وجود داشته باشد:
168 = 2 ∙ 2 ∙ 2 ∙ 3 ∙ 7;
396 = 2 ∙ 2 ∙ 3 ∙ 3 ∙ 11.
از اینجا معلوم است که
gcd(168, 396) = 2 ∙ 2 ∙ 3 = 12.
زمانی که هیچ عامل مشترکی وجود نداشته باشد و چیزی برای تأکید وجود نداشته باشد، شایسته ذکر ویژه است، به عنوان مثال:
42 = 2 ∙ 3 ∙ 7;
در این مورد،
GCD(42، 55) = 1.
دو عدد طبیعی که GCD برابر یک است نامیده می شوند دوطرفه نخست. مثلاً اگر از این اعداد کسری بسازید،
پس چنین کسری است غیر قابل کاهش.
به طور کلی، قانون کاهش کسر را می توان به صورت زیر نوشت:
|
آ/ gcd( آ, ب) |
|||
|
ب/ gcd( آ, ب) |
در اینجا فرض شده است که آو باعداد طبیعی هستند و کل کسر مثبت است. اگر اکنون یک علامت منفی به دو طرف این تساوی اضافه کنیم، قانون مربوطه را برای کسرهای منفی به دست می آوریم.
جمع و تفریق کسرها. کمترین مضرب مشترک
فرض کنید باید مجموع دو کسر را محاسبه کنید:
ما قبلاً می دانیم که چگونه مخرج ها در عوامل اول فاکتور می شوند:
105 = 3 ∙ 5 ∙ 7 ;
140 = 2 ∙ 2 ∙ 5 ∙ 7 .
از این تجزیه بلافاصله نتیجه می شود که برای آوردن کسرها به یک مخرج مشترک کافی است که صورت و مخرج کسر اول را در 2 ∙ 2 ضرب کنیم ( حاصل ضرب ضرایب اول بدون تاکید مخرج دوم) و صورت و مخرج کسر دوم بر 3 («محصول» ضرایب اول بدون تنش مخرج اول). در نتیجه، مخرج هر دو کسر برابر با عدد می شود که می توان آن را به صورت زیر نشان داد:
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 = 105 ∙ 2 ∙ 2 = 140 ∙ 3 = 420.
به راحتی می توان فهمید که هر دو مخرج اصلی (هم 105 و هم 140) مقسوم علیه عدد 420 هستند و عدد 420 به نوبه خود مضربی از هر دو مخرج است - و نه فقط مضربی، بلکه حداقل مضرب مشترک (NOC) اعداد 105 و 140 به این صورت نوشته شده است:
LCM(105، 140) = 420.
با نگاهی دقیق تر به تجزیه اعداد 105 و 140 می بینیم که
105 ∙ 140 = GCD (105، 140) ∙ GCD (105، 140).
به طور مشابه، برای اعداد طبیعی دلخواه بو د:
ب ∙ د= LOC( ب, د) ∙ GCD( ب, د).
حالا بیایید جمع کسرهایمان را کامل کنیم:
|
3 ∙ 5 ∙ 7 |
2 ∙ 2 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 ∙ 7 |
|
2 ∙ 2 ∙ 3 ∙ 5 |
|
توجه داشته باشید.برای حل برخی از مسائل باید بدانید که مربع یک عدد چقدر است. مربع عدد آشماره تماس گرفت آضرب در خودش یعنی آ∙آ. (همانطور که به راحتی قابل مشاهده است، برابر است با مساحت یک مربع با ضلع آ). |