PGCD و خوارزمية إقليدس و PPCM

ما يطلبه منك البرنامج

• تعيين PGCD بخوارزمية إقليدس
• PGCD(ka;kb)=k PGCD(a;b), PGCD(a;b)=PGCD(b;r)
• عددان أوليان فيما بينهما
• PPCM و العلاقة PGCD(a;b)× PPCM(a;b)=ab, PPCM(ka;kb)=|k|PPCM

القوانين

• PGCD× PPCM=ab
• PGCD(a;b)=PGCD(b;r) (إقليدس)

نوع التمرين الذي يأتي في الباك

• تعيين PGCD و استثمار علاقة PPCM متوسط

  حساب PGCD(a;b) بإقليدس ثم استنتاج PPCM عبر PGCD× PPCM=ab

من الدرس

نريد تبليط أرضية مستطيلة أبعادها 12 و8 ببلاطات مربّعة متطابقة، دون قصّ أيّ بلاطة. ما أكبر ضلع مربّع يحقّق ذلك؟

المصطلحات

• القاسم المشترك الأكبر
• المضاعف المشترك الأصغر
• أوليان فيما بينهما

يُبنى على

• القسمة الإقليدية و قابلية القسمة في ℤ