高校数学 - ノリの悪い日記

前回の中学入試についての記事は, もちろん中国剰余定理が背景にあるわけだが, 同じようにして解ける高校数学の問題をやってみる. 以下の解法は参考書には挙げられていないので, 書く気になった. 参考書には, 合同式を使った解法が別解として挙げられていて, それは,

$46x \equiv 4 \quad (\mathrm{mod} \ 35)$

をいきなり解くやり方である.

※ なお, 連分数を使って解くやり方は以前の記事で示した。しかし, ユークリッド互助法を逆にたどるやり方を含めて, 右辺を $1$ としてまず解くやり方は, 前記事の問題のような場合, 出てきた結果を $3890$ 倍するのだろうか. ちなみにこのやり方で

$66x + 35y = 3890$

を実際に (かなりの時間をかけて) とくと, $k$ を整数として,

$x = -35010+ 35k$ ,
$y = 66130 -66k$

となり, 自然数の最小値は, $k = 1001$ のときで, $x = 25$ , $y = 64$ である. こういった方法で自然数解を求めることはよい方法とは言えない. //

【問】
次の方程式の整数解をすべて求めよ.

$46x - 35y = 4$

【解】

$35 = 5 \times 7$ だから,

$46x \equiv 4 \quad (\mathrm{mod} \ 5)$
$x \equiv 4 \quad (\mathrm{mod} \ 5)$

また,

$46x \equiv 4 \quad (\mathrm{mod} \ 7)$
$4x \equiv 4 \quad (\mathrm{mod} \ 7)$
$x \equiv 1 \quad (\mathrm{mod} \ 7)$

$m$ を整数として, $x = 7m + 1$ とおくと,

$7m+1 \equiv 4 \quad (\mathrm{mod} \ 5)$
$2m \equiv 3 \equiv -2 \quad (\mathrm{mod} \ 5)$
$m \equiv -1 \equiv 4 \quad (\mathrm{mod} \ 5)$

これを満たす $m$ として $4$ をとれば, 特解として $x = 29$ . 一般解は, $k$ を整数として,

$x = 29 + 35 k$

$46 \times 29 \\ = 46(30-1) \\ = 1380-46\\ = 1334$

$1334-4= 1330$

$1330\div 35 \\= 1330 \times 2 \div 70 \\= 133 \times 2 \div 7 \\= 19 \times 2 \\= 38$

したがって, 特解は, $y = 38$ で一般解は,

$46 (x -29) -35(y -38) = 0$
$46\times 35k -35(y -38) = 0$
$46k - (y -38) = 0$

から

$y = 38 + 46k$

以上より,

$x = 29 + 35 k$ ,
$y = 38 + 46k$

で $k$ は整数である.
//

もうひとつやって見る.

【問】
次の方程式の整数解をすべて求めよ.

$48x + 539y = 77$

【解】

$48 = 3 \times 16$ として,

$539y \equiv 77 \quad (\mathrm{mod} \ 3)$
$2y \equiv 2 \quad (\mathrm{mod} \ 3)$
$y \equiv 1 \quad (\mathrm{mod} \ 3)$

また,

$539y \equiv 77 \quad (\mathrm{mod} \ 16)$
$11y \equiv -3 \quad (\mathrm{mod} \ 16)$

$m$ を整数として, $y = 3m + 1$ とおくと,

$11(3m+1) \equiv -3 \quad (\mathrm{mod} \ 16)$
$33m \equiv -14 \quad (\mathrm{mod} \ 16)$
$m \equiv 2 \quad (\mathrm{mod} \ 16)$

これを満たす $m$ として $2$ をとれば, 特解として $y = 7$ . 一般解は, $k$ を整数として,

$y = 7 + 48 k$

$48x \\= 77- 539(7 + 48k) \\= 7(11-539) -539 \times 48k \\=-7 \times 528 -539 \times 48k$

したがって,

$x = -77 -539k$

以上より,

$x = -77 - 539k$ ,
$y = 7 + 48k$

で $k$ は整数である.
//

※ もっとも,

$539y \equiv 77 \quad (\mathrm{mod} \ 48)$
$11y \equiv 77 \quad (\mathrm{mod} \ 48)$
$y \equiv 7 \quad (\mathrm{mod} \ 48)$

に気付くのなら, こちらの方がずっと早い.

前の記事の最初の問題も,

$66x \equiv 3890 \quad (\mathrm{mod} \ 35)$
$-4x \equiv 40 \quad (\mathrm{mod} \ 35)$
$x \equiv -10 \equiv 25 \quad (\mathrm{mod} \ 35)$

などとできれば, 直ちに解ける. やり方はいろいろあって,

$-4x \equiv 5 \quad (\mathrm{mod} \ 35)$

からでも,

$-4x \equiv 5 \equiv -30 \quad (\mathrm{mod} \ 35)$
$2x \equiv 15 \equiv -20 \quad (\mathrm{mod} \ 35)$
$x \equiv -10 \equiv 25 \quad (\mathrm{mod} \ 35)$

とできるし, 他にもうひとつだけ示せば,

$66x \equiv 5 \quad (\mathrm{mod} \ 35)$

としておいて, これから $35x$ を左辺に加えて,

$101x \equiv 5 \quad (\mathrm{mod} \ 35)$

を作って, もうひとつ, $2$ つ前の式から, $70x$ を左辺から引いて,

$-4x \equiv 5 \quad (\mathrm{mod} \ 35)$

両辺を $25$ 倍して,

$-100 x \equiv 125 \equiv 20 \quad (\mathrm{mod} \ 35)$

として, 両式を加えて,

$x \equiv 25 \quad (\mathrm{mod} \ 35)$

などとすればよい.//

※ なお, どうしても楽しい試行錯誤がしたくなければ,

$31x \equiv 5 \pmod{35}$

を解くのに, オイラーのトーシェント関数の値を

$\phi(35) = \phi(7) \phi(5) = 6 \times 4 = 24$

と求め、オイラーの定理を適用すると、

$31^{24} \equiv 1 \pmod{35}$

だから, 求める $x$ は、

$31x \equiv 5\times 31^{24} \pmod{35}$
$x \equiv 5 \times 31^{23} \pmod{35}$
$x \equiv 5 \times (-4)^{23} \pmod{35}$

で, 後はひたすら右辺を簡単にしてゆけばよい.

※ より強くは、カーマイケルの定理を使って, $\phi(7) = 6$ と $\phi(5) = 4$ の最小公倍数は $12$ だから,

$31^{12} \equiv 1 \pmod{35}$

である。したがって,

$x \equiv 5 \times (-4)^{11} \pmod{35}$

とすればよい. 法の値と素な数の「位数」 (法のもとで初めて $1$ となる累乗の指数) は, 12 の約数のどれかとなる.
//

なんか凄そうだが, ユークリッド互除法を逆にたどって解くより早く結果が得られる.

$(-4)^{1} \equiv -4 \pmod{35}$
$(-4)^{2} \equiv 16 \pmod{35}$
$(-4)^{3} \equiv -64 \equiv 6 \pmod{35}$
$(-4)^{4} \equiv -24 \equiv 11 \pmod{35}$
$(-4)^{5} \equiv -44 \equiv -9 \pmod{35}$
$(-4)^{6} \equiv 36 \equiv 1 \pmod{35}$