この問題は、利用者からの報告を受けて確認中です。答えや解説に誤りがあるかもしれません。

整数論の問題

難易度 3期末試験の応用レベル大学数学整数論

$1729 = 7 \cdot 13 \cdot 19$ である。 $x^{2} + x + 1$ が $1729$ で割り切れるような正の整数 $x$ のうち、最小のものを求めよ。

この問題で使うもの

中国剰余定理と連立合同式（説明と入口の問題）
互いに素な法への分解（説明と入口の問題）
合同式（説明と入口の問題）
法 $m$ での逆元（拡張ユークリッドの互除法）（説明と入口の問題）

この問題を解けるようになるまで（25 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

中国剰余定理を使い、法 $1729$ の合同式を法 $7$ , $13$ , $19$ の 3 つの合同式に分けて考える。

ヒント 2

各素数 $p$ について $x^{2} + x + 1 \equiv 0 (mod p)$ の解を求める（それぞれ 2 個ある）。そのあと $x \equiv a e_{7} + b e_{13} + c e_{19} (mod 1729)$ となる基底 $e_{7}, e_{13}, e_{19}$ を作る。

ヒント 3

解は法 $7$ で $x \equiv 2, 4$ 、法 $13$ で $x \equiv 3, 9$ 、法 $19$ で $x \equiv 7, 11$ 。基底は $e_{7} = 988$ , $e_{13} = 1197$ , $e_{19} = 1274$ 。8 通りの組合せを $1729$ で割った余りを比べる。

答えと解説

答えを見る

562

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

$7, 13, 19$ は互いに異なる素数なので、中国剰余定理より
$x^{2} + x + 1 \equiv 0 (mod 1729)$
は、次の 3 つの合同式を同時にみたすことと同値である。
$x^{2} + x + 1 \equiv 0 (mod 7), x^{2} + x + 1 \equiv 0 (mod 13), x^{2} + x + 1 \equiv 0 (mod 19) .$

各素数を法とする解. 素数 $p$ を法とする 2 次合同式の解は高々 2 個である。
- 法 $7$ : $2^{2} + 2 + 1 = 7$ , $4^{2} + 4 + 1 = 21 = 3 \cdot 7$ より $x \equiv 2, 4 (mod 7)$ 。
- 法 $13$ : $3^{2} + 3 + 1 = 13$ , $9^{2} + 9 + 1 = 91 = 7 \cdot 13$ より $x \equiv 3, 9 (mod 13)$ 。
- 法 $19$ : $7^{2} + 7 + 1 = 57 = 3 \cdot 19$ , $1 1^{2} + 11 + 1 = 133 = 7 \cdot 19$ より $x \equiv 7, 11 (mod 19)$ 。

したがって法 $1729$ での解は $2 \cdot 2 \cdot 2 = 8$ 個ある。

中国剰余定理の基底.
- $e_{7} \equiv 1 (mod 7)$ , $e_{7} \equiv 0 (mod 247)$ : $247 \equiv 2 (mod 7)$ , $2^{- 1} \equiv 4 (mod 7)$ より $e_{7} = 247 \cdot 4 = 988$ 。
- $e_{13} \equiv 1 (mod 13)$ , $e_{13} \equiv 0 (mod 133)$ : $133 \equiv 3 (mod 13)$ , $3^{- 1} \equiv 9 (mod 13)$ より $e_{13} = 133 \cdot 9 = 1197$ 。
- $e_{19} \equiv 1 (mod 19)$ , $e_{19} \equiv 0 (mod 91)$ : $91 \equiv 15 (mod 19)$ , $15 \cdot 14 = 210 \equiv 1 (mod 19)$ より $e_{19} = 91 \cdot 14 = 1274$ 。

解は $x \equiv a e_{7} + b e_{13} + c e_{19} (mod 1729)$ （ $a \in {2, 4}, b \in {3, 9}, c \in {7, 11}$ ）。各項を $1729$ で割った余りは
$2 e_{7} \equiv 247, 4 e_{7} \equiv 494, 3 e_{13} \equiv 133, 9 e_{13} \equiv 399, 7 e_{19} \equiv 273, 11 e_{19} \equiv 182.$

8 個の解. これらを組み合わせると（ $0$ 以上 $1728$ 以下で）
$247 + 133 + 273 = 653, 247 + 133 + 182 = 562, 247 + 399 + 273 = 919, 247 + 399 + 182 = 828, 494 + 133 + 273 = 900, 494 + 133 + 182 = 809, 494 + 399 + 273 = 1166, 494 + 399 + 182 = 1075.$
（ $x$ が解なら $- 1 - x$ も解なので、和が $1728$ になる組 $653 + 1075$ , $562 + 1166$ , $919 + 809$ , $828 + 900$ ができていることも確認できる。）

$x = 0$ は解でないので、正の整数の解のうち最小のものは $562$ である。

検算. $56 2^{2} + 562 + 1 = 315844 + 563 = 316407 = 1729 \cdot 183$ より確かに割り切れる。

よって答えは $562$ 。

別解

$1729 = 7 \cdot 13 \cdot 19$ なので、各素数を法として $x^{2} + x + 1 \equiv 0$ を解き、中国剰余定理で合わせる。

(1) 法ごとの解
- 法 7: $x \equiv 2, 4$ （ $4 + 2 + 1 = 7$ 、 $16 + 4 + 1 = 21$ ）
- 法 13: $x \equiv 3, 9$ （ $9 + 3 + 1 = 13$ 、 $81 + 9 + 1 = 91$ ）
- 法 19: $x \equiv 7, 11$ （ $49 + 7 + 1 = 57$ 、 $121 + 11 + 1 = 133$ ）

(2) 法 91 での解
法 7 と法 13 の解を合わせると $x \equiv 9, 16, 74, 81 (mod 91)$ となる。

(3) 法 19 を加える
$x = r + 91 k$ とおく。 $91 \equiv 15 (mod 19)$ なので $r + 15 k \equiv 7$ または $11 (mod 19)$ を解く。
- $r = 9$ : $x = 919, 828$
- $r = 16$ : $x = 653, 562$
- $r = 74$ : $x = 1166, 1075$
- $r = 81$ : $x = 900, 809$

$1729$ を法とする 8 個の解は $562, 653, 809, 828, 900, 919, 1075, 1166$ である。 $x$ と $- 1 - x$ が対になっており、 $562 + 1166 = 1728$ となって整合する。

(4) 検算
$56 2^{2} + 562 + 1 = 316407 = 1729 \cdot 183$ となり、確かに割り切れる。

最小の正の整数解は $562$ 。

整数論の問題

この問題で使うもの

ヒント

答えと解説

次のおすすめ

この問題の確認

間違いを報告する

関連する問題