ユークリッドの互除法を用います。 $781 = 671 \times 1 + 110$ $671 = 110 \times 6 + 11$ $110 = 11 \times 10 + 0$ したがって、最大公約数は11です。

## 問題の内容

テキスト72ページの暗号キー（a=2, b=3,...）を元にして、2つの数字の最大公約数と2つの数字による暗号を復号する問題です。各問題で与えられた2つの数字の最大公約数をユークリッドの互除法で求め、その後、それぞれの数字を因数分解し、アナグラムを解くことで復号します。

今回は、問題1, 2, 3, 4, 5を解きます。

## 解き方の手順

### 問題1: 671と781 (ヒント: 英単語)

1. **最大公約数を求める:**

ユークリッドの互除法を用います。

$781 = 671 \times 1 + 110$

$671 = 110 \times 6 + 11$

$110 = 11 \times 10 + 0$

したがって、最大公約数は11です。

2. **因数分解:**

$671 = 11 \times 61$

$781 = 11 \times 71$

3. **暗号キーを用いた変換:**

a=2, b=3, ... より、11 は 'k'、61 は 'be'と読むことができます。

71は'bf' と読むことができます。

暗号解読結果は'kbef'と'kbf'になります。英単語のヒントからアナグラムを解くと、**KEY**となります。

### 問題2: 671と8041 (ヒント: 英単語、色)

1. **最大公約数を求める:**

ユークリッドの互除法を用います。

$8041 = 671 \times 11 + 660$

$671 = 660 \times 1 + 11$

$660 = 11 \times 60 + 0$

したがって、最大公約数は11です。

2. **因数分解:**

$671 = 11 \times 61$

$8041 = 11 \times 731$

3. **暗号キーを用いた変換:**

11 は 'k', 61は 'be', 731は'bgd'に対応します。

'kbe'と'kbgd'で、英単語と色のヒントからアナグラムを解くと、**BLACK**となります。

### 問題3: 1166と1961 (ヒント: 英単語、果物)

1. **最大公約数を求める:**

ユークリッドの互除法を用います。

$1961 = 1166 \times 1 + 795$

$1166 = 795 \times 1 + 371$

$795 = 371 \times 2 + 53$

$371 = 53 \times 7 + 0$

したがって、最大公約数は53です。

2. **因数分解:**

$1166 = 53 \times 22$

$1961 = 53 \times 37$

3. **暗号キーを用いた変換:**

53は'bd'、 22は'w'、37は'bh'

'bdw'と'bdbh'。英単語と果物のヒントからアナグラムを解くと、**WORD**となります。

### 問題4: 434と874 (ヒント: 地名)

1. **最大公約数を求める:**

ユークリッドの互除法を用います。

$874 = 434 \times 2 + 6$

$434 = 6 \times 72 + 2$

$6 = 2 \times 3 + 0$

したがって、最大公約数は2です。

2. **因数分解:**

$434 = 2 \times 7 \times 31$

$874 = 2 \times 19 \times 23$

3. **暗号キーを用いた変換:**

2はa, 7はf, 31はzd, 19はr, 23はxです。

暗号解読結果はafzdとarxになります。

地名のヒントからアナグラムを解くと、**FAX**となります。

### 問題5: 782と1426 (ヒント: 皆さんも持っています、多分…)

1. **最大公約数を求める:**

ユークリッドの互除法を用います。

$1426 = 782 \times 1 + 644$

$782 = 644 \times 1 + 138$

$644 = 138 \times 4 + 92$

$138 = 92 \times 1 + 46$

$92 = 46 \times 2 + 0$

したがって、最大公約数は46です。

2. **因数分解:**

$782 = 2 \times 17 \times 23$

$1426 = 2 \times 13 \times 55$

3. **暗号キーを用いた変換:**

$782 / 46 = 17$

$1426 / 46 = 31$

暗号解読結果は17と31になります。

2->a, 17->p, 31->zd

皆さんも持っていることからアナグラムを解くと、**PAD**となります。

## 最終的な答え

1. KEY

2. BLACK

3. WORD

4. FAX

5. PAD