Ẹ̀rọ Ìṣirò LCM àti GCD

Nípa ẹ̀rọ ìṣirò yìí

Olùpín tó tóbi jù tí wọ́n jọ ní (GCD) ti nọ́ńbà odidi méjì ni nọ́ńbà tó tóbi jù tó pín àwọn méjèèjì láìsí ìyókù, tí a sábà máa ń rí nípasẹ̀ algorithm Euclid (pípín léraléra pẹ̀lú ìyókù — ọ̀kan lára àwọn algorithm tó dàgbà jù nínú ìṣirò, tó bẹ̀rẹ̀ láti Elements ti Euclid). Ìlọ́po tó kéré jù tí wọ́n jọ ní (LCM) ni nọ́ńbà tó kéré jù tí àwọn nọ́ńbà odidi méjèèjì pín láìsí ìyókù, tí a ṣírò láti GCD nípa LCM(a,b) = (a×b) / GCD(a,b).

Àwọn èrò wọ̀nyí wà níbi gbogbo: àwọn akẹ́kọ̀ọ́ ń lo GCD láti sọ àwọn ìdá-ẹ̀ya di rọrùn sí ìsàlẹ̀ jùlọ; algorithm Euclid jẹ́ ìpìlẹ̀ àwọn ìgbésẹ̀ pàtàkì nínú cryptography RSA (ṣíṣírò àwọn ìdàkejì modular); LCM sì ń yanjú àwọn ìṣòro ìṣètò àkókò bíi rírí ìgbà tí ìṣẹ̀lẹ̀ méjì tó ń tún ara wọn ṣe yóò tún jọ pàdé (fún àpẹẹrẹ ọkọ̀ akérò lórí àwọn àyípo tó yàtọ̀, tàbí ìpín gear nínú ṣíṣe mekaniki). Tẹ nọ́ńbà odidi méjì sí i láti rí GCD àti LCM méjèèjì.