学習院大学2017年(理)第2問

最近の学習院大学では文系学部で整数問題が出題されていましたが、今年は理系で出題されたようです。整式の最大公約数に関する問題です。


《問題》

自然数 $n$ に対して、$3n^3+n$ と $n^3+1$ の最大公約数を $g$ とする。

(1)すべての $n$ について、$g \ne 5$ であることを示せ。

(2)$g=14$ となるような $n$ の最小値を求めよ。

(学習院大学2017 (理)前期第2問)


《考え方》

この手の問題ではユークリッドの互除法が大活躍します。私が解いた際は以下のような方法を考えました。

●  ● 《解答例》   

ある自然数$A$、$B$の最大公約数を$\text{GCD}(A,B)$と表記することにする。

まず、$g=\text{GCD}(3n^3+n,n^3+1)$である。

($\text{mod} \ 3$ を考えて)$3n^3+n$ と $n^3+1$ はともに$3$の倍数となることは無いから、$n^3+1$を$3$倍して$$g=\text{GCD}(3n^3+n,3n^3+3)$$である。互除法の原理より、

$\begin{align} g
&=\text{GCD}(3n^3+n,n^3+1) \\
&=\text{GCD}(3n^3+n-3(n^3+1),n^3+1) \\
&=\text{GCD}(n-3,n^3+1) \end{align}$

となる。ここで、$n^3+1$と$n$は互いに素なので、$n^3+1$と$n^2$も互いに素。よって$n-3$に$n^2$を乗じて先程と同様に互除法の原理を用いると、

$\begin{align}& \ \ \ \ \ \text{GCD}(n-3,n^3+1) \\
&= \text{GCD}(n-3,n^3+1-n^2(n-3)) \\
&= \text{GCD}(n-3,3n^2+1) \end{align}$

となる。全く同様にして$3n^2+1$の次数を下げる($n-3$に$3n$を乗じて差を取る)と、

$\begin{align}& \ \ \ \ \ \text{GCD}(n-3,3n^2+1)\\
&=\text{GCD}(n-3,3n^2+1-3n(n-3)) \\
&=\text{GCD}(n-3,9n+1) \\
&=\text{GCD}(n-3,9n+1-9(n-3)) \\
&=\text{GCD}(n-3,28) \end{align}$

となる。これより(1)は自明(∵$28$は$5$の倍数でない)で、(2)は $n-3=14$ を解いて $n=17$ と求められる。

●  ● 《解答例終わり》   


(コメント)

ユークリッドの互除法を利用することによって大抵の整式であれば次数を下げることができます。何が起こっているか分からないという人もいるかもしれませんが・・・。ユークリッドの互除法については「整数第2章第1節第4項」をご覧下さい。

何かに何かを掛けて差を取る、という操作は一見万能ですが、本問のように最大公約数を主題とする場合は「互いに素でなければならない」という条件が付きまといます。

 

コメントを残す

メールアドレスが公開されることはありません。 が付いている欄は必須項目です