整数の性質の問題
正の整数 に対して、 と の最小公倍数を とする。 を満たす正の整数 のうち、
が成り立つものすべての和を求めよ。
この問題で使うもの
- ユークリッドの互除法（説明と入口の問題）
- 最大公約数と最小公倍数（説明と入口の問題）
- 合同式（説明と入口の問題）
この問題を解けるようになるまで（21 技能）
読み込み中…
右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。
ヒント
行き詰まったら、上から順に 1 つずつ開いてください。
ヒント 1
最大公約数を とすると、 が成り立ちます。条件を の条件に言い換えましょう。
ヒント 2
ユークリッドの互除法と同じように、 から を引く、という操作を繰り返して、最大公約数を を含む式と定数の最大公約数に帰着させましょう。
ヒント 3
は と の最大公約数、さらに と の最大公約数に等しく、最終的に と の最大公約数になります。 が の倍数となる を 以下で数え上げましょう。
答えと解説
答えを見る
どこでつまずきましたか？（選ぶと、戻る場所を案内します）
解説を読む
と の最大公約数を とする。正の整数 について「最大公約数 最小公倍数 」が成り立つので
である。よって条件 は と同値である。
次に、ユークリッドの互除法の考え方（ のとき と の最大公約数は と の最大公約数に等しい）を用いて を調べる。
より は と の最大公約数に等しい。
より は と の最大公約数に等しい。
より は と の最大公約数に等しい。
は素数なので は または であり、 となるのは が の倍数のとき、すなわち
のときである。
でこれを満たす は
の 個（次の は を超える）。
確認として のとき , で最大公約数は である。
これらは初項 、末項 、項数 の等差数列なので、和は
よって答えは である。
別解
最大公約数を とすると なので、条件は と同値である。
より は の約数、つまり または である。
となるのは のとき。 なら より となり、 と は互いに素なので も成り立つ。したがって条件は だけでよい。
。 より の逆元は なので 。
の範囲では の7個。
検算: のとき 、 で 。
和は 。