(1) 整数 $x, y$ が $65x + 432y = 1$ を満たすとき、最小の正の $y$ の値を求める。 (2) $\sqrt{6}$ を連分数展開して途中で打ち切ると、$\sqrt{6}$ の有理数による近似が得られる。 $\sqrt{6} \approx a + \frac{1}{b + \frac{1}{c + \frac{1}{d + \frac{1}{e}}}} = \frac{p}{q}$ と近似するとき、$p$ の値を求める。 (3) 2次行列 $A, B$ の積 $AB$ を定義通りに計算すると、成分のかけ算を8回行う。ここで $AB$ を7回の成分のかけ算で実行できる方法を見つけたと仮定する。このとき、4次行列 $P, Q$ の積 $PQ$ は $x$ 回の成分のかけ算で得られる。$x$ の値を求める。 ただし、$P = \begin{bmatrix} P_1 & P_2 \\ P_3 & P_4 \end{bmatrix}, Q = \begin{bmatrix} Q_1 & Q_2 \\ Q_3 & Q_4 \end{bmatrix}$ であり、$PQ = \begin{bmatrix} P_1Q_1 + P_2Q_3 & P_1Q_2 + P_2Q_4 \\ P_3Q_1 + P_4Q_3 & P_3Q_2 + P_4Q_4 \end{bmatrix}$ である。

1. 問題の内容

(1) 整数 $x, y$ が $65x + 432y = 1$ を満たすとき、最小の正の $y$ の値を求める。

(2) $\sqrt{6}$ を連分数展開して途中で打ち切ると、$\sqrt{6}$ の有理数による近似が得られる。

$\sqrt{6} \approx a + \frac{1}{b + \frac{1}{c + \frac{1}{d + \frac{1}{e}}}} = \frac{p}{q}$ と近似するとき、$p$ の値を求める。

(3) 2次行列 $A, B$ の積 $AB$ を定義通りに計算すると、成分のかけ算を8回行う。ここで $AB$ を7回の成分のかけ算で実行できる方法を見つけたと仮定する。このとき、4次行列 $P, Q$ の積 $PQ$ は $x$ 回の成分のかけ算で得られる。$x$ の値を求める。

ただし、$P = \begin{bmatrix} P_1 & P_2 \\ P_3 & P_4 \end{bmatrix}, Q = \begin{bmatrix} Q_1 & Q_2 \\ Q_3 & Q_4 \end{bmatrix}$ であり、$PQ = \begin{bmatrix} P_1Q_1 + P_2Q_3 & P_1Q_2 + P_2Q_4 \\ P_3Q_1 + P_4Q_3 & P_3Q_2 + P_4Q_4 \end{bmatrix}$ である。

2. 解き方の手順

(1) $65x + 432y = 1$ を満たす整数 $x, y$ を求める。まず、拡張ユークリッド互除法を用いて特殊解を求める。

$432 = 6 \cdot 65 + 42$

$65 = 1 \cdot 42 + 23$

$42 = 1 \cdot 23 + 19$

$23 = 1 \cdot 19 + 4$

$19 = 4 \cdot 4 + 3$

$4 = 1 \cdot 3 + 1$

したがって、

$1 = 4 - 1 \cdot 3 = 4 - 1 \cdot (19 - 4 \cdot 4) = 5 \cdot 4 - 1 \cdot 19 = 5 \cdot (23 - 1 \cdot 19) - 1 \cdot 19 = 5 \cdot 23 - 6 \cdot 19 = 5 \cdot 23 - 6 \cdot (42 - 1 \cdot 23) = 11 \cdot 23 - 6 \cdot 42 = 11 \cdot (65 - 1 \cdot 42) - 6 \cdot 42 = 11 \cdot 65 - 17 \cdot 42 = 11 \cdot 65 - 17 \cdot (432 - 6 \cdot 65) = 113 \cdot 65 - 17 \cdot 432$

よって、$65(113) + 432(-17) = 1$ 。

したがって、一般解は $x = 113 + 432k, y = -17 - 65k$ （$k$ は整数）。

$y > 0$ より、$-17 - 65k > 0$ 、すなわち $k < -\frac{17}{65} \approx -0.26$ 。

$k$ は整数なので、最大の $k$ は $-1$ である。

$k = -1$ のとき $y = -17 - 65(-1) = -17 + 65 = 48$。

$y$ の最小値は $48$。

(2) $\sqrt{6} = 2 + (\sqrt{6} - 2) = 2 + \frac{1}{\frac{1}{\sqrt{6}-2}} = 2 + \frac{1}{\frac{\sqrt{6}+2}{2}} = 2 + \frac{1}{2 + \frac{\sqrt{6}-2}{2}} = 2 + \frac{1}{2 + \frac{1}{ \frac{2}{\sqrt{6} - 2}}} = 2 + \frac{1}{2 + \frac{1}{\sqrt{6}+2}} = 2 + \frac{1}{2 + \frac{1}{4 + (\sqrt{6} - 2)}} \approx 2 + \frac{1}{2 + \frac{1}{4}} = 2 + \frac{1}{\frac{9}{4}} = 2 + \frac{4}{9} = \frac{18 + 4}{9} = \frac{22}{9}$ 。

したがって、$p = 22$。

(3) $PQ = \begin{bmatrix} P_1Q_1 + P_2Q_3 & P_1Q_2 + P_2Q_4 \\ P_3Q_1 + P_4Q_3 & P_3Q_2 + P_4Q_4 \end{bmatrix}$

$P_1Q_1, P_2Q_3, P_1Q_2, P_2Q_4, P_3Q_1, P_4Q_3, P_3Q_2, P_4Q_4$ はすべて2次行列の積なので、各々7回の掛け算で計算できる。

したがって、$P_1Q_1 + P_2Q_3$ の計算には $7 + 7 + 4 = 18$ 回の掛け算が必要。

$P_1Q_2 + P_2Q_4, P_3Q_1 + P_4Q_3, P_3Q_2 + P_4Q_4$ も同様に18回の掛け算が必要。

したがって、$PQ$ の計算に必要な掛け算の回数は $18 \times 4 = 28$。 よって，$x = 28$。

3. 最終的な答え

(1) 48

(2) 22

(3) 28