【2023上智大学・理工】44311と43873の最大公約数｜ユークリッド互除法

【2023上智大学・理工・第１問(１)】

\(44311\) と \(43873\) との最大公約数は [ ア ] である．

ユークリッドの互除法

【ユークリッドの互除法】

\(2\) つの自然数 \(a\) 、\(b\) において、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\)

\(a=b\times q+r\) のとき

\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい

【2017横浜市立大学・医学部】148953/298767を約分して、既約分数にせよ

\(43873=44311\times 1+438\) ・・・①

\(44311=438\times 101+73\) ・・・②

\(438=73\times 6\) ・・・③

したがって，求める最大公約数は \(73\) ・・・[ ア ]

①式から，\(43873\) と \(44311\) の最大公約数は，

\(44311\) と \(438\) の最大公約数に等しいことがわかります．

②式から，\(44311\) と \(438\) の最大公約数は，

\(438\) と \(73\) の最大公約数に等しいことがわかります．

③式から，\(438\) と \(73\) の最大公約数は，\(73\) とわかるため，

\(44311\) と \(43873\) との最大公約数が \(73\) と求まります！