problemyriad

技能一覧 › 数学A 整数の性質

互いに素な法への分解

のように法を互いに素な数に分け、「 で割り切れる でも でも割り切れる」を使って、条件を満たす余りの組を数えられる

前提

この技能までの道筋（20 技能）
算数中学高校大学大学院

読み込み中…

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

一覧で見る（前提が先）
  1. 分数のたし算・ひき算 （算数 計算と数のきまり）
  2. 小数の四則計算 （算数 計算と数のきまり）
  3. 正負の数の加法・減法 （中学数学 数と式）
  4. 分数のかけ算・わり算 （算数 計算と数のきまり）
  5. 四則の混じった計算の順序 （算数 計算と数のきまり）
  6. 正負の数の乗除・累乗と四則混合 （中学数学 数と式）
  7. 分配法則を使った計算のくふう （算数 計算と数のきまり）
  8. 文字式の計算（同類項・分配法則） （中学数学 数と式）
  9. 乗法公式による展開 （中学数学 数と式）
  10. 因数分解 （中学数学 数と式）
  11. 約数の見つけ方 （算数 整数の性質）
  12. 文字式で表した整数の性質 （中学数学 数と式）
  13. 余りによる整数の分類 （数学A 整数の性質）
  14. 樹形図で数え上げる （算数 場合の数）
  15. 積の法則と和の法則 （算数 場合の数）
  16. 和の法則・積の法則と樹形図 （数学A 場合の数と確率）
  17. 合同式 （数学A 整数の性質）
  18. 最大公約数と最小公倍数 （算数 整数の性質）
  19. 素因数分解と約数の個数 （算数 整数の性質）
  20. 最大公約数と最小公倍数 （数学A 整数の性質）

説明

のように、法（割る数）を互いに素な数の積に分けると、「 で割った余り」を「 で割った余り」と「 で割った余り」の組に置き換えて考えられます。 や のような小さい法なら、余りを全部調べるのは簡単です。そのため、大きな法での条件を小さな法ごとの条件に分けて数えられます。 が で割り切れる の個数を数えるときなどに使います。

なぜそうしてよいのか

まず「 で割り切れる でも でも割り切れる」を確かめます。 で割り切れる数が でも でも割り切れるのは明らかです。逆に、整数 が でも でも割り切れるとします。 を素因数分解すると、 で割り切れるので素因数 を含み、 で割り切れるので素因数 も含みます。 と は異なる素数なので、 の素因数分解には が丸ごと入っています。よって は の倍数です。一般に、互いに素な は共通の素因数をもちません。そのため、 でも でも割り切れる数の素因数分解には、 の素因数と の素因数が重ならずに両方入ります。したがってその数は で割り切れます。互いに素でないと、共通の素因数が 1 回分しか保証されないので、この議論は成り立ちません。

次に、 の 個の数それぞれに、( で割った余り, で割った余り ) の組を対応させます。異なる 2 数 が同じ組をもつとします。すると は でも でも割り切れるので、上の事実から で割り切れます。ところが なので、これはありえません。したがって、 個の数に対応する組はすべて異なります。組は全部で 通りしかないので、どの組もちょうど 1 回ずつ現れます。この議論は「差が 未満の 個の整数」なら何でも成り立ちます。たとえば連続する 個の整数 でも同じです。

このことから、「 を法として条件を満たす余り」の個数は、次の積になります。

これは積の法則そのものです。ただし、条件そのものが「 での条件」と「 での条件」に分かれている必要があります。それを保証するのが最初の同値です。

手順

  1. 法を互いに素な数の積に分ける（例：、）。素因数分解して、同じ素数を別々の因数に入れないようにする。

  2. 「 で割り切れる 各因数で割り切れる」を使い、条件を因数ごとの条件に書き換える（例： かつ ）。

  3. それぞれの法で、合同式を使って余りを全部調べ、条件を満たす余りの個数を数える。

  4. 各法での個数を掛け合わせる。これが、元の法 で条件を満たす余りの個数になる。連続する 個の整数（例： から まで）のうち条件を満たすものの個数もこれと同じ。

  5. 範囲が から までなら、さらに 倍する。範囲が の倍数で区切れないときは、はみ出した部分を別に数える。

例題

を満たす整数 のうち、 が で割り切れるものの個数を求めよ。

例題の解答

手順1： と分ける。 と は互いに素である。

手順2：「 が で割り切れる」を「 かつ 」と書き換える。

手順3（法 ）： のとき、 はそれぞれ と合同になる。どれも なので、条件を満たす余りは 個。

手順3（法 ）： について を計算する。
- ：
- ：
- ：
- ：
- ：
- ：
- ：

よって、条件を満たす余りは の 個。

手順4： は連続する 個の整数で、どの 2 数の差も 未満である。そのため、idea と同じ理由で、( で割った余り, で割った余り ) の 通りの組がちょうど 1 回ずつ現れる。（ は と同じ組 をもつので、 の を に置き換えただけ、とみてもよい。）したがって、条件を満たす の個数は 個。

手順5：範囲はちょうど から なので、答えはそのまま 個。

（確かめ：法 の条件はすべての で成り立つので、 を満たせばよい。そのような は の 個で、一致する。）

答え:

よくある誤り

この説明は AI が書き、別の AI が例題を独立に解いて答えを確かめ、説明を一歩ずつ査読しました。

入口の問題

この技能を使う問題

この技能の次に学べること