Evolton

京都大学 2022年度 前期日程 第2次学力試験理系数学 第3問

nを自然数とする.
3つの整数n2+2, n4+2, n6+2の最大公約数Anを求めよ.

難易度5/ 10計算量4/ 10目安15分

整数 最大公約数、合同式、偶奇性

方針

共通に割る素因数を調べる。まず差を取り、共通約数が 2(1−n2) も割ることを使う。奇素数 q が共通約数を割るなら、q∤n であり、n2≡−2 と n2≡1(modq) が同時に成り立つため q=3 に限られる。残る候補は2と3だけなので、2の指数、3の指数をそれぞれ確認する。特に3については、9が3つすべてを割ることはないことを n2(mod9) で確認する。

解答

3つの整数 n2+2,n4+2,n6+2 の最大公約数を An とする。

まず、An は n2+2 と n4+2 を割るので、その整数係数の差 n4+2−n2(n2+2)=2(1−n2) も割る。したがって An∣2(1−n2) である。

奇素数 q が An を割るとする。もし q∣n なら、q∣n2+2 より q∣2 となり、q が奇素数であることに反する。したがって q∤n である。 q∣An なので n2+2≡0(modq) であり、n2≡−2(modq) である。また An∣2(1−n2) かつ q は奇素数だから 1−n2≡0(modq) すなわち n2≡1(modq) である。よって 1≡−2(modq) となり、3≡0(modq) である。したがって奇素因数は3に限られる。

次に2の出方を調べる。n が奇数のとき、n2,n4,n6 はすべて奇数なので、3つの数はすべて奇数であり、2は An を割らない。n が偶数のときは、n2,n4,n6 は4の倍数なので n2+2≡n4+2≡n6+2≡2(mod4) である。したがって2は割るが、4は割らない。

次に3の出方を調べる。n が3の倍数のとき、3つの数はいずれも 2(mod3) に合同なので、3は An を割らない。n が3の倍数でないとき、n2≡1(mod3) であるから、3つの数はいずれも 1+2≡0(mod3) となり、3は An を割る。

ただし、9が常に共通に割るわけではないことを確認する。3∤n のとき、n2 の9での余りは 1,4,7 のいずれかである。もし n2≡1(mod9) なら n2+2≡3(mod9) である。もし n2≡4(mod9) なら n2+2≡6(mod9) である。もし n2≡7(mod9) なら n4+2≡72+2≡4+2≡6(mod9) である。いずれの場合も、3つすべてが9で割り切れることはない。したがって3の指数は高くても1である。

以上より、An は2と3の有無だけで決まる。n を6で割った余りで分類するとAn={6(n≡2,4(mod6)),3(n≡1,5(mod6)),2(n≡0(mod6)),1(n≡3(mod6))である。

別解

解法2

方針

x=n2 とおき、x+2 を法として x≡−2 を使う。後ろ2数の余りはそれぞれ6と −6 なので、3数の最大公約数が gcd⁡(n2+2,6) に正確に一致することを示す。最後は n mod 6 だけで分類する。

解答

x=n2 とおく。x+2 を法とすれば x≡−2 だからx2+2≡(−2)2+2=6(modx+2),x3+2≡(−2)3+2=−6(modx+2).したがって3数の共通約数は x+2 と6の共通約数であり、An∣gcd⁡(x+2,6).逆に d∣x+2 かつ d∣6 とする。x≡−2(modd) だからx2+2≡6≡0(modd),x3+2≡−6≡0(modd).よって d は3数すべての共通約数である。したがってAn=gcd⁡(n2+2,6).n を6で割った余りごとに n2+2 を6で見るとn mod 6012345n2+2 mod 6230503である。よってAn={6(n≡2,4(mod6)),3(n≡1,5(mod6)),2(n≡0(mod6)),1(n≡3(mod6)).

総評

最大公約数を求める整数問題。目安時間は12〜18分。公式出題意図はユークリッドの互除法を題材に整数問題の理解を評価するとしている。素因数を2と3へ絞って指数まで確認する解法と、合同式で一気に An=gcd⁡(n2+2,6) とする解法がある。後者では『共通約数なら6を割る』だけでなく、gcd⁡(n2+2,6) の各約数が後ろ2数も割る逆向きを書く。

Evolton Pro

月額
2,480円(税込)
保存・印刷
公開過去問PDF・オーダーメイド問題集PDF
プランを確認・登録

冊子PDFで見る京大の整数の問題で問題集を作る

出典: 京都大学 2022年度 一般選抜(前期日程)数学(大学公式の問題PDF)。問題文はHTML表示のために再入力・数式組版しています。