2つの自然数の最大公約数を互除法を用いて求める問題です。 (1) 779 と 533 (2) 962 と 407

1. 問題の内容

2つの自然数の最大公約数を互除法を用いて求める問題です。

(1) 779 と 533

(2) 962 と 407

2. 解き方の手順

(1) 779 と 533 の最大公約数を求める。

* 779 を 533 で割る。

$779 = 533 \times 1 + 246$

* 533 を 246 で割る。

$533 = 246 \times 2 + 41$

* 246 を 41 で割る。

$246 = 41 \times 6 + 0$

余りが 0 になったので、最大公約数は 41 です。

(2) 962 と 407 の最大公約数を求める。

* 962 を 407 で割る。

$962 = 407 \times 2 + 148$

* 407 を 148 で割る。

$407 = 148 \times 2 + 111$

* 148 を 111 で割る。

$148 = 111 \times 1 + 37$

* 111 を 37 で割る。

$111 = 37 \times 3 + 0$

余りが 0 になったので、最大公約数は 37 です。

3. 最終的な答え

(1) 41

(2) 37