پیدا کردن قانون نوک و سر زدن. یافتن گره های سه یا چند عددی

این مقاله در مورد پیدا کردن بزرگترین مقسوم علیه مشترک (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 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، a 2 =294، a 3 =570، a 4 =36.

ابتدا با استفاده از الگوریتم اقلیدس، بزرگترین مقسوم علیه مشترک d 2 از دو عدد اول 78 و 294 را تعیین می کنیم. هنگام تقسیم، برابری های 294=78 3+60 را بدست می آوریم. 78=60 1+18 ; 60=18 3+6 و 18=6 3 . بنابراین، 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 بخش پذیر است ، d 4 \u003d GCD (6, 36) \u003d 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.

بسیاری از مقسم

مسئله زیر را در نظر بگیرید: مقسوم علیه عدد 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» می‌نویسیم «د (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)" می گوید " تقاطعمجموعه Te از 105 و Te از 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 برابر یک است نامیده می شوند coprime. مثلاً اگر از این اعداد کسری بسازید،

پس چنین کسری است غیر قابل کاهش.

به طور کلی، قانون کاهش کسر را می توان به صورت زیر نوشت:

		آ/ 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 = LCM (105، 140) ∙ GCD (105، 140).

به طور مشابه، برای اعداد طبیعی دلخواه بو د:

ب ∙ د= LCM( ب, د) ∙ 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

توجه داشته باشید.برای حل برخی از مسائل، باید بدانید که مربع یک عدد چقدر است. مربع عدد آبه شماره ای زنگ زد آضرب در خودش، یعنی آ∙آ. (همانطور که می بینید برابر است با مساحت مربع با ضلع آ).

شماره دوم: b=

جداکننده رقمبدون جداکننده فضا "'

نتیجه:

بزرگترین مقسوم علیه gcd( آ,ب)=6

کمترین مضرب مشترک LCM( آ,ب)=468

بزرگترین عدد طبیعی که اعداد a و b بدون باقیمانده بر آن بخش پذیرند نامیده می شود بزرگترین مقسوم علیه مشترک(gcd) از این اعداد. به gcd(a,b), (a,b), gcd(a,b) یا hcf(a,b) نشان داده شده است.

کمترین مضرب مشترک(LCM) از دو عدد صحیح a و b کوچکترین عدد طبیعی است که بدون باقیمانده بر a و b بخش پذیر است. LCM(a,b) یا lcm(a,b) نشان داده می شود.

اعداد صحیح a و b نامیده می شوند coprimeاگر هیچ مقسوم علیه مشترک دیگری به جز +1 و -1 نداشته باشند.

بزرگترین مقسوم علیه مشترک

بگذارید دو عدد مثبت داده شود آ 1 و آ 2 1). لازم است یک مقسوم علیه مشترک این اعداد پیدا شود، یعنی. چنین عددی را پیدا کنید λ ، که اعداد را تقسیم می کند آ 1 و آ 2 به طور همزمان. بیایید الگوریتم را شرح دهیم.

1) در این مقاله کلمه عدد به معنای یک عدد صحیح خواهد بود.

اجازه دهید آ 1 ≥ آ 2 و اجازه دهید

جایی که متر 1 , آ 3 تعدادی اعداد صحیح هستند، آ 3 <آ 2 (باقی مانده از تقسیم آ 1 در آ 2 باید کمتر باشد آ 2).

بیایید وانمود کنیم که λ تقسیم می کند آ 1 و آ 2، سپس λ تقسیم می کند متر 1 آ 2 و λ تقسیم می کند آ 1 −متر 1 آ 2 =آ 3 (اظهار 2 از مقاله «تقسیم پذیری اعداد. علامت تقسیم پذیری»). نتیجه می شود که هر مقسوم علیه مشترک آ 1 و آ 2 یک مقسوم علیه مشترک است آ 2 و آ 3 . عکس آن نیز صادق است اگر λ مقسوم علیه مشترک آ 2 و آ 3، سپس متر 1 آ 2 و آ 1 =متر 1 آ 2 +آ 3 نیز به تقسیم می شوند λ . از این رو مقسوم علیه مشترک است آ 2 و آ 3 نیز یک مقسوم علیه مشترک است آ 1 و آ 2. زیرا آ 3 <آ 2 ≤آ 1، پس می توان گفت که حل مسئله یافتن مقسوم علیه مشترک اعداد است آ 1 و آ 2 به یک مسئله ساده تر یعنی یافتن مقسوم علیه مشترک اعداد کاهش می یابد آ 2 و آ 3 .

اگر یک آ 3 ≠0، سپس می توانیم تقسیم کنیم آ 2 در آ 3 . سپس

,

جایی که متر 1 و آ 4 تعدادی اعداد صحیح هستند، ( آ 4 باقی مانده از تقسیم آ 2 در آ 3 (آ 4 <آ 3)). با استدلال مشابه به این نتیجه می رسیم که مقسوم علیه های مشترک اعداد آ 3 و آ 4 همان مقسوم علیه مشترک اعداد است آ 2 و آ 3 و همچنین با مقسوم علیه های مشترک آ 1 و آ 2. زیرا آ 1 , آ 2 , آ 3 , آ 4، ... اعدادی که دائما در حال کاهش هستند و از آنجایی که تعداد محدودی از اعداد صحیح بین آنها وجود دارد. آ 2 و 0، سپس در مرحله ای n، باقی مانده تقسیم آغیر آ n+1 برابر با صفر خواهد بود ( آ n+2=0).

.

هر مقسوم علیه مشترک λ شماره آ 1 و آ 2 نیز مقسوم علیه اعداد است آ 2 و آ 3 , آ 3 و آ 4 , .... آ n و آ n+1 . برعکس نیز درست است، مقسوم علیه مشترک اعداد آ n و آ n+1 نیز مقسوم علیه اعداد هستند آ n-1 و آ n، ....، آ 2 و آ 3 , آ 1 و آ 2. اما مقسوم علیه مشترک آ n و آ n+1 یک عدد است آ n+1، زیرا آ n و آ n+1 بر بخش پذیر هستند آ n+1 (به یاد بیاورید آ n+2=0). در نتیجه آ n+1 نیز مقسوم علیه اعداد است آ 1 و آ 2 .

توجه داشته باشید که شماره آ n+1 بزرگترین مقسوم علیه اعداد است آ n و آ n+1 از بزرگترین مقسوم علیه آ n+1 خودش است آ n+1 . اگر یک آ n + 1 را می توان به عنوان حاصلضرب اعداد صحیح نشان داد، سپس این اعداد نیز مقسوم علیه مشترک اعداد هستند. آ 1 و آ 2. عدد آ n+1 نامیده می شوند بزرگترین مقسوم علیه مشترکشماره آ 1 و آ 2 .

شماره آ 1 و آ 2 می تواند اعداد مثبت و منفی باشد. اگر یکی از اعداد برابر با صفر باشد، بزرگترین مقسوم علیه مشترک این اعداد برابر با قدر مطلق عدد دیگر خواهد بود. بزرگترین مقسوم علیه مشترک اعداد صفر تعریف نشده است.

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

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

بزرگترین مقسوم علیه مشترک دو عدد 630 و 434 را پیدا کنید.

• مرحله 1. عدد 630 را بر 434 تقسیم کنید. باقیمانده 196 است.
• مرحله 2. عدد 434 را بر 196 تقسیم کنید. باقیمانده 42 است.
• مرحله 3. عدد 196 را بر 42 تقسیم کنید. باقیمانده 28 است.
• مرحله 4. عدد 42 را بر 28 تقسیم کنید باقیمانده 14 است.
• مرحله 5. عدد 28 را بر 14 تقسیم کنید، باقیمانده 0 است.

در مرحله 5 باقیمانده تقسیم 0 است بنابراین بزرگترین مقسوم علیه اعداد 630 و 434 14 است. توجه داشته باشید که اعداد 2 و 7 نیز مقسوم علیه اعداد 630 و 434 هستند.

اعداد همزمان اول

تعریف 1. بزرگترین مقسوم علیه مشترک اعداد را بگذارید آ 1 و آ 2 برابر با یک است. سپس این اعداد فراخوانی می شوند اعداد همزمان اولکه مقسوم علیه مشترک ندارند.

قضیه 1. اگر یک آ 1 و آ 2 عدد نسبتا اول و λ یک عدد، سپس هر مقسوم علیه مشترک اعداد λa 1 و آ 2 نیز مقسوم علیه مشترک اعداد است λ و آ 2 .

اثبات الگوریتم اقلیدس را برای یافتن بزرگترین مقسوم علیه مشترک اعداد در نظر بگیرید آ 1 و آ 2 (به بالا مراجعه کنید).

.

از شرایط قضیه برمی آید که بزرگترین مقسوم علیه مشترک اعداد آ 1 و آ 2، و بنابراین آ n و آ n+1 برابر با 1 است. آ n+1=1.

بیایید همه این برابری ها را در ضرب کنیم λ ، سپس

.

اجازه دهید مقسوم علیه مشترک آ 1 λ و آ 2 است δ . سپس δ به عنوان یک عامل وارد می شود آ 1 λ , متر 1 آ 2 λ و در آ 1 λ -متر 1 آ 2 λ =آ 3 λ (به "تقسیم پذیری اعداد"، بیانیه 2 مراجعه کنید). به علاوه δ به عنوان یک عامل وارد می شود آ 2 λ و متر 2 آ 3 λ ، و از این رو به عنوان یک عامل وارد می شود آ 2 λ -متر 2 آ 3 λ =آ 4 λ .

با استدلال به این روش، ما متقاعد می شویم که δ به عنوان یک عامل وارد می شود آ n-1 λ و متر n-1 آ n λ ، و بنابراین در آ n-1 λ −متر n-1 آ n λ =آ n+1 λ . زیرا آ n+1 =1، سپس δ به عنوان یک عامل وارد می شود λ . از این رو شماره δ مقسوم علیه مشترک اعداد است λ و آ 2 .

موارد خاص قضیه 1 را در نظر بگیرید.

نتیجه 1. اجازه دهید آو جاعداد اول نسبتا هستند ب. سپس محصول آنها acیک عدد اول نسبت به ب.

واقعا از قضیه 1 acو بدارای مقسوم علیه های مشترک مشابه هستند جو ب. اما اعداد جو ب coprime، یعنی دارای یک مقسوم علیه مشترک 1. سپس acو بهمچنین دارای یک مقسوم علیه مشترک 1. از این رو acو بمتقابل ساده

نتیجه 2. اجازه دهید آو باعداد coprime و let بتقسیم می کند ak. سپس بتقسیم می کند و ک.

واقعا از شرط ادعا akو بمقسوم علیه مشترک دارند ب. به موجب قضیه 1، بباید مقسوم علیه مشترک باشد بو ک. در نتیجه بتقسیم می کند ک.

نتیجه 1 را می توان تعمیم داد.

نتیجه 3. 1. اجازه دهید اعداد آ 1 , آ 2 , آ 3 , ..., آ m نسبت به عدد اول هستند ب. سپس آ 1 آ 2 , آ 1 آ 2 · آ 3 , ..., آ 1 آ 2 آ 3 ··· آ m، حاصل ضرب این اعداد نسبت به عدد اول است ب.

2. اجازه دهید دو ردیف اعداد داشته باشیم

به طوری که هر عدد در ردیف اول نسبت به هر عدد در ردیف دوم اول باشد. سپس محصول

یافتن چنین اعدادی که بر هر یک از این اعداد بخش پذیر باشند لازم است.

اگر عدد بر آن بخش پذیر باشد آ 1، سپس به نظر می رسد sa 1، کجا ستعدادی عدد اگر یک qبزرگترین مقسوم علیه مشترک اعداد است آ 1 و آ 2، سپس

جایی که س 1 مقداری عدد صحیح است. سپس

است حداقل مضرب مشترک اعداد آ 1 و آ 2 .

آ 1 و آ 2 هم اول، سپس کمترین مضرب مشترک اعداد آ 1 و آ 2:

کمترین مضرب مشترک این اعداد را پیدا کنید.

از موارد فوق نتیجه می گیرد که هر مضربی از اعداد آ 1 , آ 2 , آ 3 باید مضربی از اعداد باشد ε و آ 3 و بالعکس. حداقل مضرب مشترک اعداد را بگذارید ε و آ 3 است ε یکی . علاوه بر این، مضربی از اعداد آ 1 , آ 2 , آ 3 , آ 4 باید مضربی از اعداد باشد ε 1 و آچهار . حداقل مضرب مشترک اعداد را بگذارید ε 1 و آ 4 است ε 2. بنابراین، ما متوجه شدیم که همه مضرب اعداد آ 1 , آ 2 , آ 3 ,...,آ m منطبق بر مضرب یک عدد خاص است ε n که کمترین مضرب مشترک اعداد داده شده نامیده می شود.

در مورد خاص زمانی که اعداد آ 1 , آ 2 , آ 3 ,...,آ m coprime، سپس کمترین مضرب مشترک اعداد آ 1 , آ 2 همانطور که در بالا نشان داده شده است شکل (3) دارد. علاوه بر این، از آن زمان آ 3 عدد اول نسبت به اعداد آ 1 , آ 2، سپس آ 3 یک عدد نسبی اول است آیک · آ 2 (نتیجه 1). بنابراین کمترین مضرب مشترک اعداد آ 1 ,آ 2 ,آ 3 یک عدد است آیک · آ 2 · آ 3 . با استدلال به روشی مشابه، به ادعاهای زیر می رسیم.

بیانیه 1. حداقل چندگانه مشترک اعداد اول آ 1 , آ 2 , آ 3 ,...,آ m برابر حاصلضرب آنهاست آیک · آ 2 · آ 3 ··· آمتر

بیانیه 2. هر عددی که بر هر یک از اعداد همزمان اول بخش پذیر باشد آ 1 , آ 2 , آ 3 ,...,آ m نیز بر حاصلضرب آنها قابل تقسیم است آیک · آ 2 · آ 3 ··· آمتر

بزرگترین عدد طبیعی که اعداد a و b بدون باقیمانده بر آن بخش پذیرند نامیده می شود بزرگترین مقسوم علیه مشترکاین اعداد GCD (a, b) را نشان دهید.

پیدا کردن GCD را با استفاده از مثال دو عدد طبیعی 18 و 60 در نظر بگیرید:

1 بیایید اعداد را به عوامل اول تجزیه کنیم:
18 = 2×3×3
60 = 2×2×3×5

2 از بسط عدد اول تمام عواملی که در بسط عدد دوم گنجانده نشده اند را حذف می کنیم. 2×3×3 .

3 فاکتورهای اول باقیمانده را پس از خط زدن ضرب می کنیم و بزرگترین مقسوم علیه مشترک اعداد را بدست می آوریم: gcd ( 18 , 60 )=2×3= 6 .

4 توجه داشته باشید که از شماره اول یا دوم که فاکتورها را خط می زنیم مهم نیست، نتیجه یکسان خواهد بود:
18 = 2×3×3
60 = 2×2×3×5

324 , 111 و 432

بیایید اعداد را به عوامل اول تجزیه کنیم:

324 = 2×2×3×3×3×3

111 = 3×37

432 = 2×2×2×2×3×3×3

حذف از عدد اول که فاکتورهای آن در اعداد دوم و سوم نیست، به دست می آید:

2 x 2 x 2 x 3 x 3 x 3 = 3

در نتیجه GCD( 324 , 111 , 432 )=3

یافتن GCD با الگوریتم اقلیدس

راه دوم برای پیدا کردن بزرگترین مقسوم علیه مشترک با استفاده از الگوریتم اقلیدس. الگوریتم اقلیدس کارآمدترین راه برای یافتن است GCD، با استفاده از آن باید دائماً باقیمانده تقسیم اعداد را پیدا کنید و اعمال کنید فرمول مکرر.

فرمول مکرربرای GCD، gcd(a, b)=gcd(b, a mod b)، که در آن a mod b باقیمانده تقسیم a بر b است.

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

مثال بزرگترین مقسوم علیه اعداد را پیدا کنید 7920 و 594

بیایید GCD را پیدا کنیم( 7920 , 594 ) با استفاده از الگوریتم اقلیدس، باقیمانده تقسیم را با استفاده از ماشین حساب محاسبه می کنیم.

GCD( 7920 , 594 )

GCD( 594 , 7920 مد 594 ) = gcd( 594 , 198 )

GCD( 198 , 594 مد 198 ) = gcd( 198 , 0 )

GCD( 198 , 0 ) = 198

• 7920 mod 594 = 7920 - 13 × 594 = 198
• 594 mod 198 = 594 - 3 × 198 = 0

در نتیجه، GCD ( 7920 , 594 ) = 198

کمترین مضرب مشترک

برای پیدا کردن مخرج مشترک هنگام جمع و تفریق کسری با مخرج های مختلف، باید بدانید و بتوانید محاسبه کنید. حداقل مضرب مشترک(NOC).

مضرب عدد "الف" عددی است که خود بدون باقیمانده بر عدد "الف" بخش پذیر است.

اعداد مضرب 8 (یعنی این اعداد بدون باقیمانده بر 8 تقسیم می شوند): اینها اعداد 16، 24، 32 هستند ...

مضرب 9: 18، 27، 36، 45…

بی نهایت مضرب یک عدد معین a وجود دارد، برخلاف مقسوم علیه های همان عدد. مقسوم علیه - یک عدد محدود.

مضرب مشترک دو عدد طبیعی عددی است که به طور مساوی بر هر دوی این اعداد بخش پذیر باشد..

کمترین مضرب مشترک(LCM) دو یا چند عدد طبیعی کوچکترین عدد طبیعی است که خود بر هر یک از این اعداد بخش پذیر است.

نحوه پیدا کردن NOC

LCM را می توان به دو صورت یافت و نوشت.

اولین راه برای پیدا کردن LCM

این روش معمولا برای اعداد کم استفاده می شود.

1. مضرب هر یک از اعداد را در یک خط می نویسیم تا زمانی که مضربی برای هر دو عدد یکسان باشد.
2. مضرب عدد "a" با حرف بزرگ "K" نشان داده می شود.

مثال. LCM 6 و 8 را پیدا کنید.

راه دوم برای پیدا کردن LCM

استفاده از این روش برای یافتن LCM برای سه عدد یا بیشتر راحت است.

تعداد عوامل یکسان در بسط اعداد می تواند متفاوت باشد.

در بسط عدد کوچکتر (اعداد کوچکتر)، زیر عواملی که در بسط عدد بزرگتر لحاظ نشده اند (در مثال ما 2 است) خط بکشید و این عوامل را به بسط عدد بزرگتر اضافه کنید.
LCM (24، 60) = 2 2 3 5 2

کار حاصل را در پاسخ ثبت کنید.
پاسخ: LCM (24، 60) = 120

همچنین می توانید یافتن کمترین مضرب مشترک (LCM) را به صورت زیر رسمی کنید. بیایید LCM (12، 16، 24) را پیدا کنیم.

24 = 2 2 2 3

همانطور که از بسط اعداد می بینیم، همه عوامل 12 در بسط 24 (بزرگترین اعداد) گنجانده شده اند، بنابراین ما فقط یک 2 از بسط عدد 16 را به LCM اضافه می کنیم.

LCM (12، 16، 24) = 2 2 2 3 2 = 48

پاسخ: LCM (12، 16، 24) = 48

موارد خاص یافتن NOCs

اگر یکی از اعداد به طور مساوی بر اعداد دیگر بخش پذیر باشد، کمترین مضرب مشترک این اعداد برابر با این عدد است.

به عنوان مثال، LCM(60، 15) = 60
از آنجایی که اعداد همزمان اول دارای مقسوم علیه اول مشترک نیستند، کمترین مضرب مشترک آنها برابر حاصلضرب این اعداد است.

در سایت ما، می‌توانید از یک ماشین‌حساب مخصوص برای یافتن کمترین مضرب آنلاین برای بررسی محاسبات خود استفاده کنید.

اگر یک عدد طبیعی فقط بر 1 و خودش بخش پذیر باشد، آن را اول می گویند.

هر عدد طبیعی همیشه بر 1 و خودش بخش پذیر است.

عدد 2 کوچکترین عدد اول است. این تنها عدد اول زوج است، بقیه اعداد اول فرد هستند.

اعداد اول زیادی وجود دارد و اولین عدد در میان آنها عدد 2 است. با این حال، آخرین عدد اول وجود ندارد. در قسمت "برای مطالعه" می توانید جدول اعداد اول تا 997 را دانلود کنید.

اما بسیاری از اعداد طبیعی به طور مساوی بر سایر اعداد طبیعی بخش پذیرند.

• عدد 12 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12 بخش پذیر است.
• 36 بر 1، بر 2، بر 3، بر 4، بر 6، بر 12، بر 18، بر 36 بخش پذیر است.

اعدادی که عدد بر آنها به طور مساوی بخش پذیر است (برای 12 اینها 1، 2، 3، 4، 6 و 12 هستند) مقسوم علیه اعداد نامیده می شوند.

مقسوم علیه یک عدد طبیعی a عددی طبیعی است که عدد داده شده "a" را بدون باقیمانده تقسیم می کند.

عدد طبیعی که بیش از دو عامل داشته باشد، عدد مرکب نامیده می شود.

توجه داشته باشید که اعداد 12 و 36 مقسوم علیه مشترک دارند. اینها اعداد هستند: 1، 2، 3، 4، 6، 12. بزرگترین مقسوم علیه این اعداد 12 است.

مقسوم علیه مشترک دو عدد داده شده "الف" و "ب" عددی است که هر دو عدد "الف" و "ب" بدون باقی مانده بر آن تقسیم می شوند.

بزرگترین مقسوم علیه مشترک(GCD) از دو عدد داده شده "a" و "b" بزرگترین عددی است که هر دو عدد "a" و "b" بدون باقی مانده بر آن بخش پذیر هستند.

به طور خلاصه بزرگترین مقسوم علیه مشترک اعداد "الف" و "ب" به صورت زیر نوشته می شود:

مثال: gcd (12; 36) = 12.

مقسوم علیه اعداد در رکورد حل با حرف بزرگ "D" نشان داده می شود.

اعداد 7 و 9 فقط یک مقسوم علیه مشترک دارند - عدد 1. چنین اعدادی نامیده می شوند اعداد همزمان اول.

اعداد همزمان اولاعداد طبیعی هستند که فقط یک مقسوم علیه مشترک دارند - عدد 1. GCD آنها 1 است.

چگونه بزرگترین مقسوم علیه مشترک را پیدا کنیم

برای پیدا کردن gcd دو یا چند عدد طبیعی به موارد زیر نیاز دارید:

• تقسیم کننده های اعداد را به ضرایب اول تجزیه کنید.

محاسبات به راحتی با استفاده از یک نوار عمودی نوشته می شوند. در سمت چپ خط، ابتدا سود سهام را یادداشت کنید، در سمت راست - تقسیم کننده. در ادامه در ستون سمت چپ مقادیر private را یادداشت می کنیم.

بیایید بلافاصله با یک مثال توضیح دهیم. بیایید اعداد 28 و 64 را به فاکتورهای اول فاکتور کنیم.

زیر عوامل اول یکسان در هر دو عدد خط بکشید.
28 = 2 2 7

64 = 2 2 2 2 2 2
حاصل ضرب عوامل اول یکسان را پیدا کرده و پاسخ را یادداشت می کنیم.
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 را پیدا کنید.

در سایت اطلاعات ما، همچنین می توانید بزرگترین مقسوم علیه مشترک را به صورت آنلاین با استفاده از برنامه Helper برای بررسی محاسبات خود بیابید.

یافتن کمترین مضرب مشترک، روش ها، نمونه هایی از یافتن LCM.

مطالب ارائه شده در زیر ادامه منطقی نظریه از مقاله تحت عنوان LCM - حداقل چندگانه مشترک، تعریف، مثال ها، رابطه بین LCM و GCD است. در اینجا ما در مورد صحبت خواهیم کرد یافتن کمترین مضرب مشترک (LCM)، و به حل مثال ها توجه ویژه ای داشته باشید. اجازه دهید ابتدا نشان دهیم که چگونه LCM دو عدد بر حسب GCD این اعداد محاسبه می شود. در مرحله بعد، یافتن کمترین مضرب مشترک را با فاکتورگیری اعداد در ضرایب اول در نظر بگیرید. پس از آن بر روی یافتن LCM سه یا چند عدد تمرکز می کنیم و همچنین به محاسبه LCM اعداد منفی نیز توجه می کنیم.

پیمایش صفحه.

محاسبه کمترین مضرب مشترک (LCM) از طریق gcd

یکی از راه های یافتن کمترین مضرب مشترک بر اساس رابطه بین LCM و GCD است. رابطه موجود بین LCM و GCD به شما امکان می دهد حداقل مضرب مشترک دو عدد صحیح مثبت را از طریق بزرگترین مقسوم علیه مشترک شناخته شده محاسبه کنید. فرمول مربوطه دارای فرم است LCM(a, b)=a b: GCM(a, b). نمونه هایی از یافتن LCM را طبق فرمول بالا در نظر بگیرید.

کوچکترین مضرب مشترک دو عدد 126 و 70 را پیدا کنید.

در این مثال a=126، b=70. بیایید از پیوند LCM با GCD استفاده کنیم که با فرمول LCM(a, b)=a b: GCM(a, b) بیان می شود. یعنی ابتدا باید بزرگترین مقسوم علیه اعداد 70 و 126 را پیدا کنیم و بعد از آن می توانیم LCM این اعداد را طبق فرمول نوشته شده محاسبه کنیم.

gcd(126, 70) را با استفاده از الگوریتم اقلیدس پیدا کنید: 126=70 1+56 , 70=56 1+14 , 56=14 4 , از این رو gcd(126, 70)=14 .

اکنون حداقل مضرب مشترک مورد نیاز را پیدا می کنیم: LCM(126, 70)=126 70:GCD(126, 70)= 126 70:14=630.

LCM(68, 34) چیست؟

از آنجایی که 68 به طور مساوی بر 34 بخش پذیر است، پس gcd(68, 34)=34. اکنون حداقل مضرب مشترک را محاسبه می کنیم: LCM(68, 34)=68 34:GCD(68, 34)= 68 34:34=68.

توجه داشته باشید که مثال قبلی با قانون زیر برای یافتن LCM برای اعداد صحیح مثبت a و b مطابقت دارد: اگر عدد a بر b بخش پذیر باشد، کمترین مضرب مشترک این اعداد a است.

یافتن LCM با فاکتورگیری اعداد به فاکتورهای اولیه

راه دیگر برای یافتن کمترین مضرب مشترک بر اساس فاکتورسازی اعداد به ضرایب اول است. اگر از تمام ضرایب اول این اعداد حاصل ضربی بسازیم و پس از آن همه ضرایب اول مشترکی را که در بسط این اعداد وجود دارند از این حاصلضرب حذف کنیم، حاصل ضرب حاصل برابر با کمترین مضرب مشترک این اعداد خواهد بود.

قانون اعلام شده برای یافتن LCM از برابری LCM(a, b)=a b: GCM(a, b) پیروی می کند. در واقع، حاصل ضرب اعداد a و b برابر است با حاصلضرب تمام عوامل دخیل در بسط اعداد a و b. به نوبه خود، gcd(a, b) برابر است با حاصلضرب همه عوامل اولی که به طور همزمان در بسط اعداد a و b وجود دارند (که در بخش یافتن gcd با استفاده از تجزیه اعداد به عوامل اول توضیح داده شده است. ).

بیایید یک مثال بزنیم. بگذارید بدانیم که 75=3 5 5 و 210=2 3 5 7 . حاصل ضرب تمام عوامل این بسط ها را بنویسید: 2 3 3 5 5 5 7 . حال تمام عواملی را که هم در بسط عدد 75 و هم در بسط عدد 210 وجود دارد را از این محصول حذف می کنیم (این عوامل عبارتند از 3 و 5)، سپس حاصلضرب به شکل 2 3 5 5 7 خواهد بود. مقدار این حاصلضرب برابر است با کمترین مضرب مشترک 75 و 210 یعنی LCM(75, 210)= 2 3 5 5 7=1 050 .

بعد از اینکه اعداد 441 و 700 را در ضرایب اول قرار دادید، کمترین مضرب مشترک این اعداد را پیدا کنید.

بیایید اعداد 441 و 700 را به ضرایب اول تجزیه کنیم:

441=3 3 7 7 و 700 = 2 2 5 5 7 بدست می آوریم.

حال بیایید از همه عوامل دخیل در بسط این اعداد حاصل ضرب کنیم: 2 2 3 3 5 5 7 7 7 . اجازه دهید همه عواملی را که به طور همزمان در هر دو بسط وجود دارند از این محصول حذف کنیم (فقط یک عامل وجود دارد - این عدد 7 است): 2 2 3 3 5 5 7 7 . بنابراین LCM(441, 700)=2 2 3 3 5 5 7 7 = 44 100 .

LCM(441، 700)= 44 100 .

قانون یافتن LCM با استفاده از تجزیه اعداد به عوامل اول را می توان کمی متفاوت فرموله کرد. اگر عوامل مفقود شده از بسط عدد b را به عوامل حاصل از بسط عدد a اضافه کنیم، مقدار حاصلضرب برابر با کمترین مضرب مشترک اعداد a و b خواهد بود.

برای مثال، بیایید همه اعداد یکسان 75 و 210 را در نظر بگیریم، بسط آنها به ضرایب اول به صورت زیر است: 75=3 5 5 و 210=2 3 5 7 . به فاکتورهای 3، 5 و 5 از تجزیه عدد 75، فاکتورهای گمشده 2 و 7 را از تجزیه عدد 210 اضافه می کنیم، حاصل ضرب 2 3 5 5 7 را به دست می آوریم که مقدار آن LCM (75) است. ، 210).

کوچکترین مضرب مشترک 84 و 648 را پیدا کنید.

ابتدا تجزیه اعداد 84 و 648 را به ضرایب اول بدست می آوریم. آنها شبیه 84=2 2 3 7 و 648=2 2 2 3 3 3 3 هستند. به فاکتورهای 2، 2، 3 و 7 از تجزیه عدد 84، فاکتورهای گمشده 2، 3، 3 و 3 را از تجزیه عدد 648 اضافه می کنیم، حاصل ضرب 2 2 2 3 3 3 3 7 را به دست می آوریم. که برابر با 4 536 است. بنابراین، حداقل مضرب مشترک مورد نظر اعداد 84 و 648، 4536 است.

یافتن LCM سه یا چند عدد

کمترین مضرب مشترک سه یا چند عدد را می توان با یافتن متوالی LCM دو عدد پیدا کرد. قضیه مربوطه را به یاد بیاورید که راهی برای یافتن LCM سه یا چند عدد می دهد.

بگذارید اعداد صحیح مثبت a 1 , a 2 , …, a k داده شوند، کمترین مضرب مشترک m k این اعداد در محاسبه ترتیبی یافت می شود m 2 = LCM (a 1 , a 2 ), m 3 = LCM (m 2 , a 3) , … , m k =LCM(m k−1 , a k) .

کاربرد این قضیه را در مثال یافتن مضرب مشترک چهار عدد در نظر بگیرید.

LCM چهار عدد 140، 9، 54 و 250 را بیابید.

ابتدا m 2 = LCM (a 1 , a 2) = LCM (140, 9) را پیدا می کنیم. برای انجام این کار، با استفاده از الگوریتم اقلیدسی، gcd(140, 9) را تعیین می کنیم، 140=9 15+5، 9=5 1+4، 5=4 1+1، 4=1 4 داریم، بنابراین، gcd( 140، 9)=1، از آنجا LCM(140، 9)=140 9: GCD(140، 9)= 140 9:1=1 260. یعنی m 2 = 1 260 .

اکنون m 3 = LCM (m 2 , a 3) = LCM (1 260, 54) را پیدا می کنیم. بیایید آن را از طریق gcd(1 260, 54) محاسبه کنیم که توسط الگوریتم اقلیدس نیز تعیین می شود: 1 260=54 23+18 , 54=18 3 . سپس gcd(1 260, 54)=18، از آنجا LCM(1 260, 54)= 1 260 54:gcd(1 260, 54)= 1 260 54:18=3 780 . یعنی m 3 \u003d 3 780.

باقی مانده است که m 4 = LCM (m 3 , a 4) = LCM (3 780, 250) را پیدا کنید. برای انجام این کار، GCD(3 780, 250) را با استفاده از الگوریتم اقلیدس پیدا می کنیم: 3 780=250 15+30 , 250=30 8+10 , 30=10 3 . بنابراین، gcd(3 780، 250) = 10، از این رو LCM(3 780، 250) = 3 780 250:gcd(3 780، 250) = 3 780 250:10=94 500. یعنی m 4 \u003d 94 500.

بنابراین کمترین مضرب مشترک چهار عدد اصلی 94500 است.

LCM(140، 9، 54، 250)=94500.

در بسیاری از موارد، کمترین مضرب مشترک سه یا چند اعداد به راحتی با استفاده از فاکتورسازی اول اعداد داده شده یافت می شود. در این صورت باید از قانون زیر پیروی کرد. کمترین مضرب مشترک چند عدد برابر با حاصل ضرب است که به صورت زیر تشکیل می شود: عوامل گمشده از بسط عدد دوم به همه عوامل از بسط عدد اول اضافه می شوند، عوامل مفقود از بسط عدد اول. عدد سوم به فاکتورهای بدست آمده اضافه می شود و غیره.

مثالی از یافتن کمترین مضرب مشترک با استفاده از تجزیه اعداد به عوامل اول را در نظر بگیرید.

کوچکترین مضرب مشترک پنج عدد 84، 6، 48، 7، 143 را بیابید.

ابتدا تجزیه این اعداد را به عوامل اول به دست می آوریم: 84=2 2 3 7 , 6=2 3 , 48=2 2 2 2 3 , 7 (7 عدد اول است، منطبق بر تجزیه آن به عوامل اول است) و 143=11 13 .

برای یافتن LCM این اعداد، به فاکتورهای عدد اول 84 (آنها 2، 2، 3 و 7 هستند) باید فاکتورهای گمشده از بسط عدد دوم 6 را اضافه کنید. بسط عدد 6 شامل فاکتورهای گمشده نیست، زیرا هر دو و 2 در حال حاضر در بسط اولین عدد 84 وجود دارند. علاوه بر فاکتورهای 2، 2، 3 و 7، فاکتورهای گمشده 2 و 2 را از بسط عدد سوم 48 اضافه می کنیم، مجموعه ای از عوامل 2، 2، 2، 2، 3 و 7 را به دست می آوریم. نیازی به افزودن فاکتورها به این مجموعه در مرحله بعد نیست، زیرا 7 قبلاً در آن موجود است. در نهایت به فاکتورهای 2، 2، 2، 2، 3 و 7 فاکتورهای گمشده 11 و 13 را از بسط عدد 143 اضافه می کنیم. حاصلضرب 2 2 2 2 3 7 11 13 را بدست می آوریم که برابر با 48 048 است.

بنابراین، LCM(84, 6, 48, 7, 143)=48048.

LCM(84، 6، 48، 7، 143)=48048.

یافتن کمترین مضرب مشترک اعداد منفی

گاهی اوقات کارهایی وجود دارد که در آنها باید کمترین مضرب مشترک اعداد را پیدا کنید که در میان آنها یک، چند یا همه اعداد منفی هستند. در این موارد، همه اعداد منفی باید با اعداد مخالف خود جایگزین شوند و پس از آن باید LCM اعداد مثبت را پیدا کرد. این راهی برای یافتن LCM اعداد منفی است. برای مثال، LCM(54، -34)=LCM(54، 34) و LCM(-622، -46، -54، -888) = LCM(622، 46، 54، 888).

ما می‌توانیم این کار را انجام دهیم زیرا مجموعه مضرب a با مجموعه مضرب -a یکسان است (a و -a اعداد متضاد هستند). در واقع، فرض کنید b مضرب a باشد، سپس b بر a بخش پذیر است، و مفهوم بخش پذیری وجود چنین عدد صحیح q را تایید می کند که b=a q . اما برابری b=(-a)·(-q) نیز صادق خواهد بود، که به موجب همان مفهوم تقسیم پذیری، به این معنی است که b بر −a بخش پذیر است، یعنی b مضرب −a است. عبارت معکوس نیز درست است: اگر b مضرب −a باشد، b نیز مضرب a است.

کوچکترین مضرب مشترک اعداد منفی -145 و -45 را پیدا کنید.

بیایید اعداد منفی -145 و -45 را با اعداد مقابل آنها 145 و 45 جایگزین کنیم. ما LCM(-145، -45)=LCM(145، 45) داریم. با تعیین gcd(145, 45)=5 (به عنوان مثال با استفاده از الگوریتم اقلیدس)، LCM(145, 45)=145 45:gcd(145, 45)= 145 45:5=1 305 را محاسبه می کنیم. بنابراین، کمترین مضرب مشترک اعداد صحیح منفی -145 و -45 1305 است.

www.cleverstudents.ru

ما به مطالعه تقسیم بندی ادامه می دهیم. در این درس به مفاهیمی مانند GCDو NOC.

GCDبزرگترین مقسوم علیه مشترک است.

NOCکمترین مضرب مشترک است.

موضوع نسبتا خسته کننده است، اما درک آن ضروری است. بدون درک این مبحث، نمی توانید به طور موثر با کسری کار کنید که یک مانع واقعی در ریاضیات است.

بزرگترین مقسوم علیه مشترک

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

برای اینکه این تعریف را به خوبی درک کنیم، به جای متغیرها را جایگزین می کنیم آو ببه عنوان مثال، به جای یک متغیر، هر دو عدد آعدد 12 را جایگزین کنید و به جای متغیر بشماره 9. حال بیایید سعی کنیم این تعریف را بخوانیم:

بزرگترین مقسوم علیه اعداد 12 و 9 بزرگترین عددی است که توسط آن 12 و 9 بدون باقی مانده تقسیم می شود.

از تعریف مشخص می شود که ما در مورد مقسوم علیه مشترک اعداد 12 و 9 صحبت می کنیم و این مقسوم علیه بزرگترین مقسوم علیه موجود است. این بزرگترین مقسوم علیه مشترک (gcd) باید پیدا شود.

برای یافتن بزرگترین مقسوم علیه مشترک دو عدد از سه روش استفاده می شود. روش اول کاملاً وقت گیر است، اما به شما امکان می دهد ماهیت موضوع را به خوبی درک کنید و کل معنای آن را احساس کنید.

روش دوم و سوم بسیار ساده است و یافتن سریع GCD را ممکن می کند. ما هر سه روش را در نظر خواهیم گرفت. و چه چیزی را در عمل اعمال کنید - شما انتخاب می کنید.

راه اول این است که تمام مقسوم علیه های ممکن دو عدد را پیدا کنید و بزرگترین آنها را انتخاب کنید. بیایید این روش را در مثال زیر در نظر بگیریم: بزرگترین مقسوم علیه مشترک اعداد 12 و 9 را پیدا کنید.

ابتدا همه مقسوم‌کننده‌های ممکن عدد 12 را پیدا می‌کنیم. برای این کار، 12 را به همه مقسوم‌کننده‌های بین 1 تا 12 تقسیم می‌کنیم. اگر مقسوم‌کننده اجازه می‌دهد 12 را بدون باقی مانده تقسیم کنیم، آن را با رنگ آبی برجسته می‌کنیم و یک عدد می‌سازیم. توضیح مناسب در داخل پرانتز

12: 1 = 12
(12 تقسیم بر 1 بدون باقی مانده، بنابراین 1 مقسوم علیه 12 است)

12: 2 = 6
(12 تقسیم بر 2 بدون باقی مانده، بنابراین 2 مقسوم علیه 12 است)

12: 3 = 4
(12 تقسیم بر 3 بدون باقی مانده، بنابراین 3 مقسوم علیه 12 است)

12: 4 = 3
(12 تقسیم بر 4 بدون باقی مانده، بنابراین 4 مقسوم علیه 12 است)

12:5 = 2 (2 باقی مانده)
(12 بدون باقی مانده بر 5 تقسیم نمی شود، بنابراین 5 مقسوم علیه 12 نیست)

12: 6 = 2
(12 تقسیم بر 6 بدون باقی مانده، بنابراین 6 مقسوم علیه 12 است)

12: 7 = 1 (5 باقی مانده)
(12 بدون باقیمانده بر 7 تقسیم نمی شود، بنابراین 7 مقسوم علیه 12 نیست)

12: 8 = 1 (4 باقی مانده)
(12 بدون باقی مانده بر 8 تقسیم نمی شود، بنابراین 8 مقسوم علیه 12 نیست)

12:9 = 1 (3 باقی مانده)
(12 بدون باقیمانده بر 9 تقسیم نمی شود، بنابراین 9 مقسوم علیه 12 نیست)

12: 10 = 1 (2 باقی مانده)
(12 بدون باقی مانده بر 10 تقسیم نمی شود، بنابراین 10 مقسوم علیه 12 نیست)

12:11 = 1 (1 باقی مانده)
(12 بدون باقی مانده بر 11 تقسیم نمی شود، بنابراین 11 مقسوم علیه 12 نیست)

12: 12 = 1
(12 تقسیم بر 12 بدون باقی مانده، بنابراین 12 مقسوم علیه 12 است)

حال بیایید مقسوم علیه های عدد 9 را پیدا کنیم. برای این کار، تمام مقسوم علیه های 1 تا 9 را بررسی کنید.

9: 1 = 9
(9 تقسیم بر 1 بدون باقی مانده، بنابراین 1 مقسوم علیه 9 است)

9: 2 = 4 (1 باقی مانده)
(9 بدون باقی مانده بر 2 تقسیم نمی شود، بنابراین 2 مقسوم علیه 9 نیست)

9: 3 = 3
(9 تقسیم بر 3 بدون باقی مانده، بنابراین 3 مقسوم علیه 9 است)

9: 4 = 2 (1 باقی مانده)
(9 بدون باقی مانده بر 4 تقسیم نمی شود، بنابراین 4 مقسوم علیه 9 نیست)

9:5 = 1 (4 باقی مانده)
(9 بدون باقی مانده بر 5 تقسیم نمی شود، بنابراین 5 مقسوم علیه 9 نیست)

9: 6 = 1 (3 باقی مانده)
(9 بدون باقی مانده بر 6 تقسیم نمی شود، بنابراین 6 مقسوم علیه 9 نیست)

9:7 = 1 (2 باقی مانده)
(9 بدون باقی مانده بر 7 تقسیم نمی شود، بنابراین 7 مقسوم علیه 9 نیست)

9:8 = 1 (1 باقی مانده)
(9 بدون باقی مانده بر 8 تقسیم نمی شود، بنابراین 8 مقسوم علیه 9 نیست)

9: 9 = 1
(9 تقسیم بر 9 بدون باقی مانده، بنابراین 9 مقسوم علیه 9 است)

حال مقسوم علیه هر دو عدد را بنویسید. اعدادی که با رنگ آبی مشخص شده اند مقسوم علیه هستند. بیایید آنها را بنویسیم:

با نوشتن مقسوم‌گیرنده‌ها، می‌توانید فوراً تعیین کنید که کدام بزرگ‌ترین و رایج‌ترین است.

طبق تعریف، بزرگترین مقسوم علیه 12 و 9 عددی است که 12 و 9 بر آن به طور مساوی بخش پذیر باشند. بزرگترین و مشترک اعداد 12 و 9 عدد 3 است

هر دو عدد 12 و عدد 9 بدون باقی مانده بر 3 بخش پذیرند:

بنابراین gcd (12 و 9) = 3

راه دوم برای پیدا کردن GCD

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

مثال 1. GCD اعداد 24 و 18 را پیدا کنید

ابتدا، بیایید هر دو عدد را به عوامل اول فاکتور کنیم:

حال عوامل مشترک آنها را ضرب می کنیم. برای اینکه گیج نشوید، می توان بر عوامل مشترک زیر خط کشید.

ما به تجزیه عدد 24 نگاه می کنیم. عامل اول آن 2 است. ما در تجزیه عدد 18 به دنبال همان عامل هستیم و می بینیم که آن هم وجود دارد. زیر هر دو مورد خط می کشیم:

باز هم به تجزیه عدد 24 نگاه می کنیم. عامل دوم آن نیز 2 است. ما در تجزیه عدد 18 به دنبال همان عامل هستیم و می بینیم که برای بار دوم وجود ندارد. سپس ما چیزی را برجسته نمی کنیم.

دو بعدی در بسط عدد 24 نیز در بسط عدد 18 وجود ندارد.

به آخرین عامل در تجزیه عدد 24 می گذریم. این ضریب 3 است. ما در تجزیه عدد 18 به دنبال همان عامل هستیم و می بینیم که آن هم وجود دارد. ما بر هر سه مورد تأکید می کنیم:

بنابراین، فاکتورهای مشترک اعداد 24 و 18، فاکتورهای 2 و 3 هستند. برای به دست آوردن GCD، این عوامل باید ضرب شوند:

بنابراین gcd (24 و 18) = 6

راه سوم برای یافتن GCD

حال سومین راه را برای یافتن بزرگترین مقسوم علیه مشترک در نظر بگیرید. ماهیت این روش در این واقعیت نهفته است که اعداد مورد جستجو برای بزرگترین مقسوم علیه مشترک به ضرایب اول تجزیه می شوند. سپس از تجزیه عدد اول عواملی که در تجزیه عدد دوم لحاظ نشده اند حذف می شوند. اعداد باقی مانده در بسط اول ضرب می شوند و GCD بدست می آید.

برای مثال بیایید GCD اعداد 28 و 16 را به این ترتیب پیدا کنیم. اول از همه، این اعداد را به عوامل اول تجزیه می کنیم:

ما دو بسط گرفتیم: و

حال از بسط عدد اول عواملی را که در بسط عدد دوم نمی گنجد حذف می کنیم. بسط عدد دوم شامل هفت نمی شود. ما آن را از اولین بسط حذف خواهیم کرد:

حالا فاکتورهای باقی مانده را ضرب می کنیم و GCD را می گیریم:

عدد 4 بزرگترین مقسوم علیه اعداد 28 و 16 است. هر دوی این اعداد بدون باقی مانده بر 4 بخش پذیرند:

مثال 2 GCD اعداد 100 و 40 را پیدا کنید

فاکتور گرفتن عدد 100

فاکتور گرفتن عدد 40

ما دو بسط گرفتیم:

حال از بسط عدد اول عواملی را که در بسط عدد دوم نمی گنجد حذف می کنیم. بسط عدد دوم شامل یک پنج نیست (فقط یک پنج وجود دارد). ما آن را از اولین تجزیه حذف می کنیم

اعداد باقیمانده را ضرب کنید:

به جواب 20 رسیدیم پس عدد 20 بزرگترین مقسوم علیه اعداد 100 و 40 است. این دو عدد بدون باقی مانده بر 20 بخش پذیرند:

GCD (100 و 40) = 20.

مثال 3 gcd اعداد 72 و 128 را پیدا کنید

فاکتور گرفتن عدد 72

فاکتور گرفتن عدد 128

2×2×2×2×2×2×2

حال از بسط عدد اول عواملی را که در بسط عدد دوم نمی گنجد حذف می کنیم. بسط عدد دوم شامل دو سه قلو نمی شود (اصلاً وجود ندارد). ما آنها را از اولین بسط حذف می کنیم:

ما جواب 8 را گرفتیم. بنابراین عدد 8 بزرگترین مقسوم علیه اعداد 72 و 128 است. این دو عدد بدون باقی مانده بر 8 بخش پذیر هستند:

GCD (72 و 128) = 8

پیدا کردن GCD برای اعداد چندگانه

بزرگترین مقسوم علیه مشترک را می توان برای چندین عدد و نه فقط برای دو پیدا کرد. برای این کار، اعدادی که برای بزرگترین مقسوم علیه مشترک پیدا می شوند به ضرایب اول تجزیه می شوند، سپس حاصل ضرب ضرایب اول مشترک این اعداد به دست می آید.

برای مثال، بیایید GCD را برای اعداد 18، 24 و 36 پیدا کنیم

فاکتورگیری عدد 18

فاکتورگیری عدد 24

فاکتورگیری عدد 36

ما سه بسط گرفتیم:

حال عوامل رایج در این اعداد را انتخاب کرده و زیر آنها خط می زنیم. عوامل مشترک باید در هر سه عدد گنجانده شود:

می بینیم که فاکتورهای مشترک برای اعداد 18، 24 و 36 فاکتورهای 2 و 3 هستند. با ضرب این عوامل، GCD مورد نظر را به دست می آوریم:

ما جواب 6 را گرفتیم. بنابراین عدد 6 بزرگترین مقسوم علیه اعداد 18، 24 و 36 است. این سه عدد بدون باقیمانده بر 6 بخش پذیرند:

GCD (18، 24 و 36) = 6

مثال 2 gcd را برای اعداد 12، 24، 36 و 42 پیدا کنید

بیایید هر عدد را فاکتورسازی کنیم. سپس حاصل ضرب عوامل مشترک این اعداد را می یابیم.

فاکتورگیری عدد 12

فاکتورگیری عدد 42

ما چهار بسط گرفتیم:

حال عوامل رایج در این اعداد را انتخاب کرده و زیر آنها خط می زنیم. عوامل مشترک باید در هر چهار عدد گنجانده شود:

می بینیم که فاکتورهای مشترک برای اعداد 12، 24، 36 و 42 فاکتورهای 2 و 3 هستند. با ضرب این عوامل، GCD مورد نظر را به دست می آوریم:

ما جواب 6 را گرفتیم. بنابراین عدد 6 بزرگترین مقسوم علیه اعداد 12، 24، 36 و 42 است. این اعداد بدون باقی مانده بر 6 بخش پذیر هستند:

gcd(12، 24، 36 و 42) = 6

از درس قبل می دانیم که اگر عددی بدون باقیمانده بر عدد دیگری تقسیم شود، مضرب این عدد نامیده می شود.

معلوم می شود که یک مضرب می تواند با چندین عدد مشترک باشد. و اکنون به مضربی از دو عدد علاقه مند خواهیم بود، در حالی که باید تا حد امکان کوچک باشد.

تعریف. حداقل مضرب مشترک (LCM) اعداد آو ب- آو ب آو شماره ب.

تعریف شامل دو متغیر است آو ب. بیایید هر دو عدد را جایگزین این متغیرها کنیم. به عنوان مثال، به جای یک متغیر آعدد 9 را جایگزین کنید و به جای متغیر ببیایید عدد 12 را جایگزین کنیم. حال بیایید سعی کنیم تعریف را بخوانیم:

حداقل مضرب مشترک (LCM) اعداد 9 و 12 - کوچکترین عددی است که مضرب است 9 و 12 . به عبارت دیگر، عدد بسیار کوچکی است که بدون باقیمانده بر عدد بخش پذیر است 9 و روی شماره 12 .

از تعریف مشخص است که LCM کوچکترین عددی است که بدون باقیمانده بر 9 و 12 بخش پذیر است. این LCM باید پیدا شود.

دو راه برای یافتن کمترین مضرب مشترک (LCM) وجود دارد. راه اول این است که می توانید مضرب های اول دو عدد را یادداشت کنید و سپس از بین این مضرب ها عددی را انتخاب کنید که برای هر دو عدد مشترک و کوچک باشد. بیایید این روش را اعمال کنیم.

اول از همه، بیایید اولین مضرب های عدد 9 را پیدا کنیم. برای پیدا کردن مضرب های 9، باید این نه را در اعداد 1 تا 9 ضرب کنید. پاسخ هایی که می گیرید مضربی از عدد 9 خواهد بود. ، بیا شروع کنیم. چندتایی با رنگ قرمز برجسته خواهند شد:

حالا مضرب عدد 12 را پیدا می کنیم. برای این کار 12 را به نوبت در تمام اعداد 1 تا 12 ضرب می کنیم.

تعریف.بزرگترین عدد طبیعی که اعداد a و b بدون باقی مانده بر آن بخش پذیرند نامیده می شود بزرگترین مقسوم علیه مشترک (gcd)این اعداد

بیایید بزرگترین مقسوم علیه اعداد 24 و 35 را پیدا کنیم.
مقسوم علیه های 24 اعداد 1، 2، 3، 4، 6، 8، 12، 24 و مقسوم علیه های 35 اعداد 1، 5، 7، 35 خواهند بود.
می بینیم که اعداد 24 و 35 فقط یک مقسوم علیه مشترک دارند - عدد 1. چنین اعدادی نامیده می شوند. coprime.

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

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

با فاکتور گیری اعداد 48 و 36 به دست می آید:
48 = 2 * 2 * 2 * 2 * 3, 36 = 2 * 2 * 3 * 3.
از عواملی که در بسط اعداد اول گنجانده شده است، مواردی را که در بسط عدد دوم گنجانده نشده اند (یعنی دو دس) حذف می کنیم.
ضرایب 2 * 2 * 3 باقی می مانند. حاصلضرب آنها 12 است. این عدد بزرگترین مقسوم علیه مشترک اعداد 48 و 36 است. بزرگترین مقسوم علیه مشترک سه عدد یا بیشتر نیز یافت می شود.

برای پیدا کردن بزرگترین مقسوم علیه مشترک

2) از عواملی که در بسط یکی از این اعداد گنجانده شده است، مواردی را که در بسط اعداد دیگر گنجانده نشده اند خط بزنید.
3) حاصلضرب عوامل باقیمانده را بیابید.

اگر همه اعداد داده شده بر یکی از آنها بخش پذیر باشند، این عدد است بزرگترین مقسوم علیه مشترکاعداد داده شده
به عنوان مثال، بزرگترین مقسوم علیه مشترک 15، 45، 75 و 180، 15 است، زیرا همه اعداد دیگر را تقسیم می کند: 45، 75، و 180.

کمترین مضرب مشترک (LCM)

تعریف. کمترین مضرب مشترک (LCM)اعداد طبیعی a و b کوچکترین عدد طبیعی هستند که مضرب هر دو a و b هستند. کمترین مضرب مشترک (LCM) اعداد 75 و 60 را می توان بدون نوشتن مضرب این اعداد در یک ردیف پیدا کرد. برای انجام این کار ، 75 و 60 را به عوامل ساده تجزیه می کنیم: 75 \u003d 3 * 5 * 5 و 60 \u003d 2 * 2 * 3 * 5.
فاکتورهای موجود در بسط اعداد اول را می نویسیم و فاکتورهای گمشده 2 و 2 را از بسط عدد دوم به آنها اضافه می کنیم (یعنی عوامل را با هم ترکیب می کنیم).
پنج عامل 2 * 2 * 3 * 5 * 5 بدست می آوریم که حاصل ضرب آنها 300 می شود. این عدد کمترین مضرب مشترک اعداد 75 و 60 است.

همچنین کوچکترین مضرب مشترک سه عدد یا بیشتر را پیدا کنید.

به کمترین مضرب مشترک را پیدا کنیدچندین عدد طبیعی، شما نیاز دارید:
1) آنها را به عوامل اول تجزیه کنید.
2) عوامل موجود در گسترش یکی از اعداد را بنویسید.
3) عوامل گمشده از بسط اعداد باقیمانده را به آنها اضافه کنید.
4) حاصلضرب عوامل حاصل را بیابید.

توجه داشته باشید که اگر یکی از این اعداد بر همه اعداد دیگر بخش پذیر باشد، این عدد کمترین مضرب مشترک این اعداد است.
برای مثال، کمترین مضرب مشترک 12، 15، 20 و 60 60 خواهد بود، زیرا بر همه اعداد داده شده بخش پذیر است.

فیثاغورث (قرن ششم قبل از میلاد) و شاگردانش موضوع تقسیم پذیری اعداد را مطالعه کردند. عددی برابر مجموع همه مقسوم علیه های آن (بدون خود عدد) عدد کامل را می گفتند. به عنوان مثال، اعداد 6 (6 = 1 + 2 + 3)، 28 (28 = 1 + 2 + 4 + 7 + 14) کامل هستند. اعداد کامل بعدی 496، 8128، 33،550،336 هستند. فیثاغورثی ها فقط سه عدد کامل اول را می دانستند. چهارم - 8128 - در قرن اول شناخته شد. n ه. پنجم - 33 550 336 - در قرن 15 یافت شد. تا سال 1983، 27 عدد کامل از قبل شناخته شده بود. اما تا به حال، دانشمندان نمی دانند که آیا اعداد کامل فرد وجود دارد یا خیر، آیا بزرگترین عدد کامل وجود دارد یا خیر.
علاقه ریاضیدانان باستانی به اعداد اول به این دلیل است که هر عددی یا اول است یا می توان آن را به عنوان حاصلضرب اعداد اول نشان داد، یعنی اعداد اول مانند آجرهایی هستند که بقیه اعداد طبیعی از آن ساخته شده اند.
احتمالاً متوجه شده اید که اعداد اول در سری اعداد طبیعی به طور ناهموار رخ می دهند - در برخی از قسمت های سری تعداد آنها بیشتر است، در برخی دیگر - کمتر. اما هر چه بیشتر در امتداد سری اعداد حرکت کنیم، اعداد اول نادرتر می شوند. این سوال مطرح می شود: آیا آخرین (بزرگترین) عدد اول وجود دارد؟ ریاضیدان یونانی باستان اقلیدس (قرن سوم قبل از میلاد) در کتاب خود "آغاز" که برای دو هزار سال کتاب اصلی ریاضیات بود، ثابت کرد که بی نهایت اعداد اول وجود دارد، یعنی پشت هر عدد اول یک عدد زوج وجود دارد. عدد اول بزرگتر
برای یافتن اعداد اول، یکی دیگر از ریاضیدانان یونانی در همان زمان، اراتوستنس، چنین روشی را ارائه کرد. او همه اعداد را از 1 تا فلان عدد یادداشت کرد و سپس واحد را که نه عدد اول است و نه ترکیبی خط کشید، سپس تمام اعداد بعد از 2 را از طریق یک خط زد (اعدادی که مضرب 2 هستند، یعنی 4، 6، 8، و غیره). اولین عدد باقیمانده بعد از 2، 3 بود. سپس، پس از دو، تمام اعداد بعد از 3 خط زده شدند (اعدادی که مضرب 3 هستند، یعنی 6، 9، 12 و غیره). در پایان، فقط اعداد اول بدون خط باقی ماندند.