整数問題の解き方｜約数の個数・余り・不定方程式【公務員数的推理】

約数の個数：指数に1を足してかける

約数の個数は、数えあげなくても素因数分解の指数から一発で出ます。

「指数＋1」をかけるのは、それぞれの素数を0個から指数個まで選べるからです。36の約数は 1,2,3,4,6,9,12,18,36 のちょうど9個。素因数分解の計算機で確かめられます。

例題：7で割ると3余り、5で割ると2余る2けたの整数は？

セナ

条件が2つもあると、どこから手をつければ……。

ホクト先生

片方ずつ攻めよう。まず「7で割って3余る数」を小さい順に：3, 10, 17, 24, 31…。この中から「5で割って2余る」ものを探すと、17が最初に見つかる。あとは7と5の最小公倍数35ごとにくり返すから、17, 52, 87…。2けたなら17, 52, 87だね。

→整数問題の解き方（3ステップ）

① まず素因数分解するか、条件の数を小さい順に書き出す

② 約数・倍数なら公式（指数＋1）、余りなら最小公倍数の周期を見つける

③ 範囲（2けた・3けたなど）でしぼって答えを確定

「ax＋by＝c を満たす自然数 x, y」は、解を1組見つけてから等間隔でずらすのが定石です。

例題：3x＋5y＝30 の自然数解（0以上）。
→ y＝0のとき x＝10、y＝3のとき x＝5、y＝6のとき x＝0。x が5減るとy が3増える（係数を入れかえた分だけ動く）規則になっているので、(10,0)(5,3)(0,6)の3組。表で書き出すと見落としません。

✕公務員試験で狙われる定番ミス

❌ 約数の個数で「指数をそのままかける」（必ず指数＋1）
❌ 余りの問題で周期（最小公倍数）を使わず、片方だけで答える
❌ 不定方程式で「自然数（または0以上）」の範囲を外れた解まで数える

72の約数は何個？（答え：72＝2³×3² → (3+1)×(2+1)＝12個）
4で割ると1余り、6で割ると3余る2けたの最小の数は？（答え：9…は1けた、次は21。4で割ると1余り6で割ると3余る＝最小公倍数12周期で 9,21,33… 2けた最小は21）
2x＋3y＝12 の自然数解（0以上）は？（答え：(0,4)(3,2)(6,0)）

FAQよくある質問

約数の個数の求め方は？

素因数分解して、各指数に1を足してかけ算します。たとえば 36＝2²×3² なら、(2+1)×(2+1)＝9個。指数に1を足すのは「その素数を0個〜指数個まで選べる」からです。

「7で割ると3余り、5で割ると2余る数」はどう求める？

まず一方の条件を満たす数を小さい順に書き（7で割って3余る＝3, 10, 17, 24…）、その中からもう一方も満たす数を探します（17は5で割ると2余る）。あとは7と5の最小公倍数35ごとにくり返すので、17, 52, 87…が答えです。

不定方程式（ax＋by＝c）の自然数解の求め方は？

解を1つ見つけてから、規則的にずらします。たとえば 3x＋5y＝30 なら、x＝5,y＝3が1つの解。x を5増やすとy が3減る（係数を入れかえた分だけ動く）ので、(0,6)(5,3)(10,0)が自然数解です。

整数問題が苦手です。何から固めるべき？

素因数分解と、最大公約数・最小公倍数です。約数・倍数・余りの問題は、ほぼこの2つに帰着します。計算ツールの素因数分解・GCD/LCM計算機で手を動かして感覚をつかむのが近道です。