ユークリッドの互除法

割り算と最大公約数には性質がある。

a÷b = q...r(aとbの最大公約数とqとrの最大公約数は等しい)この性質を用いて最大公約数を求める方法をユークリッドの互除法という。

345と253の最大公約数を求める。

345÷253=1...92　253÷92=2...69　92÷69=1...23 69÷23=3

これにより92、69の最大公約数は23であり、345、253の最大公約数は23と求められる。