メインコンテンツへスキップ
見出し画像

素因数分解の裏技と素数判定のコツ

    素因数分解は小さい数、例えば3030程度であれば2×3×52\times3\times5と割とすぐに求めることができます。しかし、4桁など桁が増えていくと一気に時間がかかります(これを応用したのがRSA暗号です)。ここではそのような大変な素因数分解をできるだけ「早く」やる方法を紹介します。

    「□の倍数」の楽な判定方法

    まずは数が何の倍数かの割と楽な判定方法を紹介します。

    2の倍数

    これは簡単で、一の位が2の倍数(偶数)であれば2の倍数です。
    たとえば、43164316や1489014890は2の倍数で、133133や1982319823は2の倍数ではありません。
    なぜ成立するのかの証明を以下に記しておきます。

    【成立することの証明】
    n,m,kを自然数とする。ここで、任意の自然数αに対して十の位以上の数をn,一の位の数をmとする。(つまりα=10n+mとおく)mが2の倍数であるとき、m=2kと表せるので、α=10n+2k=2(5n+k)n,kはともに自然数であるから、2(5n+k)は2の倍数である。よって、自然数では一の位が2の倍数であればその数は2の倍数である。n,m,kを自然数とする。\\ここで、任意の自然数\alphaに対して十の位以上の数をn,\\一の位の数をmとする。(つまり\alpha=10n+mとおく)\\mが2の倍数であるとき、m=2kと表せるので、\\ \alpha=10n+2k=2(5n+k)\\n,kはともに自然数であるから、2(5n+k)は2の倍数である。\\よって、自然数では一の位が2の倍数であればその数は2の倍数である。

    3の倍数、9の倍数

    次に3の倍数と9の倍数です。これはすべての位の数字を足したときに3の倍数になっていればその数は3の倍数です。例えば、123123は1+2+3=61+2+3=6で6は3の倍数なので123123は3の倍数です。
    9の倍数は同様にすべての位の数字を足したときに9の倍数になっていればその数は9の倍数です。例えば、378378は3+7+8=183+7+8=18で18は9の倍数なので378378は9の倍数です。

    【成立することの証明】
    ここでは3の倍数のみにしますが、9の倍数もほぼ同様です。
    n1,n2,n3,…を自然数とする。kを自然数として、k桁の自然数Xを考えると、X=10k−1nk+10k−2nk−1+10k−3nk−2+…+102n3+10n2+n1 …(i)仮定よりXが3の倍数のときすべての位を足すと3の倍数になるから、aを自然数とし、nk+nk−1+nk−2+…+n3+n2+n1=3aとおくと、n1=3a−nk−nk−1−nk−2−…−n3−n2 …(ii)(ii)を(i)に代入すると、X=10k−1nk+10k−2nk−1+10k−3nk−2+…+102n3+10n2+3a−nk−nk−1−nk−2−…−n3−n2ここで、10n−1が3の倍数になる(※下を参照)ので、10k−1nk+10k−2nk−1+10k−3nk−2+…+102n3+10n2+3a−nk−nk−1−nk−2−…−n3−n2=(10k−1−1)nk+(10k−2−1)nk−1+…+(102−1)n3+(10−1)n2+3amを自然数として10n−1=3m1,3m2…とおくと、上の式は3m1nk+3m2nk−1+…+3mk−2n3+3mk−1n2+3a=3(m1nk+m2nk−1+…+mk−2n3+mk−1n2+a)カッコ内は自然数であるから、上の式は3の倍数である。よって、仮定は成立する。n_1,n_2,n_3,…を自然数とする。\\kを自然数として、k桁の自然数Xを考えると、\\X=10^{k-1}n_k+10^{k-2}n_{k-1}+10^{k-3}n_{k-2}+…+10^2n_3+10n_2+n_1  …(\mathrm{i})\\仮定よりXが3の倍数のときすべての位を足すと3の倍数になるから、\\aを自然数とし、n_k+n_{k-1}+n_{k-2}+…+n_3+n_2+n_1=3aとおくと、\\n_1=3a-n_k-n_{k-1}-n_{k-2}-…-n_3-n_2  …(\mathrm{ii})\\ (\mathrm{ii})を(\mathrm{i})に代入すると、\\X=10^{k-1}n_k+10^{k-2}n_{k-1}+10^{k-3}n_{k-2}+…+10^2n_3+10n_2+3a-n_k-n_{k-1}-n_{k-2}-…-n_3-n_2\\ここで、10^n-1が3の倍数になる(※下を参照)ので、\\10^{k-1}n_k+10^{k-2}n_{k-1}+10^{k-3}n_{k-2}+…+10^2n_3+10n_2+3a-n_k-n_{k-1}-n_{k-2}-…-n_3-n_2\\=(10^{k-1}-1)n_k+(10^{k-2}-1)n_{k-1}+…+(10^2-1)n_3+(10-1)n_2+3a\\mを自然数として10^n-1=3m_1,3m_2…とおくと、上の式は\\3m_1n_k+3m_2n_{k-1}+…+3m_{k-2}n_3+3m_{k-1}n_2+3a\\=3(m_1n_k+m_2n_{k-1}+…+m_{k-2}n_3+m_{k-1}n_2+a)\\カッコ内は自然数であるから、上の式は3の倍数である。\\よって、仮定は成立する。

    ※10n−1が3の倍数になる証明(数学的帰納法を利用)(i) n=1のとき、10n−1=10−1=9 よってn=1のとき命題は真(ii) n=kのとき成り立つと仮定し、n=k+1のときを考えると、   10k+1−1=10⋅10k−1=(10⋅10k−10)+9=10(10k−1)+9   10k−1は3の倍数と仮定しているので、   αを自然数とし仮に3αとおくと、   10(10k−1)+9=10⋅3α+9=30α+9=3(10α+3)   10α+3は自然数であるから、3(10α+3)は3の倍数である。   よって、10k−1が3の倍数とするとき、10k+1−1は3の倍数になる。(i),(ii)より、10n−1は3の倍数になる。(証明終わり)※10^n-1が3の倍数になる証明(数学的帰納法を利用)\\(\mathrm{i})  n=1のとき、10^n-1=10-1=9\\ よってn=1のとき命題は真\\(\mathrm{ii})  n=kのとき成り立つと仮定し、n=k+1のときを考えると、\\    10^{k+1}-1=10\cdot10^k-1=(10\cdot10^k-10)+9=10(10^k-1)+9\\    10^k-1は3の倍数と仮定しているので、\\     \alphaを自然数とし仮に3\alphaとおくと、\\    10(10^k-1)+9=10\cdot3\alpha+9=30\alpha+9=3(10\alpha+3)\\    10\alpha+3は自然数であるから、3(10\alpha+3)は3の倍数である。\\    よって、10^k-1が3の倍数とするとき、10^{k+1}-1は3の倍数になる。\\(\mathrm{i}),(\mathrm{ii})より、10^n-1は3の倍数になる。(証明終わり)

    4の倍数、8の倍数

    4の倍数、8の倍数ともに本質的には見分け方はあまり変わりません。

    まずは4の倍数です。
    どのような自然数でも下2桁が4の倍数ならばその数は4の倍数です。
    【下2桁が4の倍数かどうかの見分け方】
     ・十の位が偶数のとき
      一の位が0,4,80,4,8ならば4の倍数
     ・十の位が奇数のとき
      一の位が2,62,6ならば4の倍数

    次に8の倍数です。
    下3桁が8の倍数であればその数は8の倍数です。
    下3桁に関しては見分け方はあまりありませんが、8=2×48=2\times4を利用して一度2で割った後に4の倍数かどうかを判断するということはできます。

    【成立することの証明】
    ここでは4の倍数のみにしますが、8の倍数もほぼ同様です。
    任意の自然数 X において、百の位以上の数をm,下2桁をnとすると、X=100m+nと表せる。ここで、nが4の倍数のとき、n=4a(aは自然数)とすると、X=100m+4a=4(25m+a)25m+aは自然数であるから、4(25m+a)は4の倍数になる。よって、自然数の下2桁が4の倍数ならばその数は4の倍数になる。任意の自然数  X  において、百の位以上の数をm,下2桁をnとすると、\\X=100m+nと表せる。\\ここで、nが4の倍数のとき、n=4a(aは自然数)とすると、\\X=100m+4a=4(25m+a)\\25m+aは自然数であるから、4(25m+a)は4の倍数になる。\\よって、自然数の下2桁が4の倍数ならばその数は4の倍数になる。

    【下2桁の見分け方の証明(?)】
    100未満の4の倍数は、0,4,812,1620,24,2832,3640,44,4852,5660,64,6872,7680,84,8892,96ここで、一の位に注目すると、十の位が偶数のとき:一の位は0,4,8十の位が奇数のとき:一の位は2,6100未満の4の倍数は、\\0,4,8\\12,16\\20,24,28\\32,36\\40,44,48\\ 52,56\\ 60,64,68\\ 72,76\\ 80,84,88\\92,96\\ここで、一の位に注目すると、\\十の位が偶数のとき:一の位は0,4,8\\十の位が奇数のとき:一の位は2,6

    5の倍数

    5の倍数は2の倍数よりも簡単で、一の位が00か55のときはその数は5の倍数です。例えば、284765284765や1239012390は5の倍数で、1349613496や13411341は5の倍数ではありません。

    【成立することの証明】
    任意の自然数 X において、一の位の数をn,十の位以上の数をmとする。(↑つまり、284765であればn=5,m=28476)ここで、X=10m+nを利用する。(i) 一の位の数が0(n=0)のとき  n=0のとき、10m+n=10m=5×2m  2mは自然数であるから、5×2mは5の倍数(ii) 一の位の数が5(n=5)のとき  n=5のとき、10m+n=10m+5=5(2m+1)  2m+1は自然数であるから、5(2m+1)は5の倍数(i),(ii)より、命題は真任意の自然数  X  において、一の位の数をn,十の位以上の数をmとする。\\(↑つまり、284765であればn=5,m=28476)\\ここで、X=10m+nを利用する。\\(\mathrm{i})  一の位の数が0(n=0)のとき\\   n=0のとき、10m+n=10m=5\times2m\\   2mは自然数であるから、5\times2mは5の倍数\\(\mathrm{ii})  一の位の数が5(n=5)のとき\\   n=5のとき、10m+n=10m+5=5(2m+1)\\   2m+1は自然数であるから、5(2m+1)は5の倍数\\(\mathrm{i}),(\mathrm{ii})より、命題は真

    6の倍数

    6の倍数は、2の倍数かつ3の倍数であるものです。
    (6=2×36=2\times3かつ2,3ともに素数のため)
    つまり、一の位が偶数かつすべての位の数字を足したときに3の倍数になるものが6の倍数になります。

    7の倍数

    7の倍数は少し特殊な考え方をします。
    7の倍数になる条件は以下のようになります。
    ・2桁の場合
     十の位−(一の位×2)の絶対値が7の倍数十の位-(一の位\times2)の絶対値が7の倍数
    ・3桁の場合
     (百の位×2)+下2桁が7の倍数(百の位\times2)+下2桁が7の倍数
    ・4桁以上の場合
     十の位以上の数−(一の位×2)が7の倍数十の位以上の数-(一の位\times2)が7の倍数
    ※4桁以上の場合ですべてできますが、3桁の場合のやりかたは楽にするテクニックです。

    例えば、9191は9−8×2=−7,−79-8\times2=-7,-7の絶対値は77のため7の倍数で、616616も6×2+16=286\times2+16=28で7の倍数、という感じです。

    【成立することの証明】
    ここでは4桁以上の場合の証明を紹介します。
    他もほぼ同じやり方で証明することができます。
    任意の自然数 X において、十の位以上の数をm、一の位をnとして、任意の自然数 X を X=10m+nとおき、Xが7の倍数のときを自然数kを使って10m+n=7kとおく。ここで、「十の位以上の数−(一の位×2)」はm−2nと表され、10m+n=7kよりn=7k−10mなのでこれを代入すると、m−2(7k−10m)=21m−14k=7(3m−2k)3m−2kは整数なので、7(3m−2k)は7の倍数になる。よって、命題は真である。任意の自然数  X  において、十の位以上の数をm、一の位をnとして、\\任意の自然数  X  を  X=10m+nとおき、\\Xが7の倍数のときを自然数kを使って10m+n=7kとおく。\\ここで、「十の位以上の数-(一の位\times2)」はm-2nと表され、\\10m+n=7kよりn=7k-10mなのでこれを代入すると、\\m-2(7k-10m)=21m-14k=7(3m-2k)\\3m-2kは整数なので、7(3m-2k)は7の倍数になる。\\よって、命題は真である。

    因数分解の公式の利用

    次に因数分解の公式を利用して因数を求める方法です。これはすこしレベル高めですが、慣れてしまえば簡単です。基本的に使う公式は和と差の積の公式です。

    2乗の和と差の利用

    100−n100-nの形や10000−m10000-mの形のときに有効です。

    a2−b2=(a+b)(a−b)a^2-b^2=(a+b)(a-b)

    例題:9271を素因数分解せよ。例題:9271を素因数分解せよ。

    これはまず偶数ではないので2で割り切れず、9+2+7+1=199+2+7+1=19で3や9で割り切れないことはすぐにわかりますが、素因数はすぐに見当もつきません。そこで、以下のように因数分解を利用して解きます。

    9271=10000−729=1002−272=(100+27)(100−27)=127×7373,127ともに素数なので、9271=73×1279271\\=10000-729\\=100^2-27^2\\=(100+27)(100-27)\\=127\times73\\73,127ともに素数なので、\\9271=73\times127

    基本的に4桁は1002−n2100^2-n^2や202−n220^2-n^2の形にして分解することが多いと思います。また、例えば3936=202−82=28×123936=20^2-8^2=28\times12のように単純に公式に代入して計算しただけでは素因数分解が完了しないパターンもありますが、2桁程度であればあまり時間はかからないので楽にできると思います。

    3乗の和と差の利用(発展)

    1000±k1000\pm kの形のときに使いやすいと思いますが、
    2乗の形よりは少し使いづらいです。

    a3+b3=(a+b)(a2−ab+b2)a3−b3=(a−b)(a2+ab+b2)a^3+b^3=(a+b)(a^2-ab+b^2)\\ a^3-b^3=(a-b)(a^2+ab+b^2)

    例題:2331を素因数分解せよ。例題:2331を素因数分解せよ。

    当然のように2,3,5,7で割り切れないので、これも工夫して解きます。

    1343=1000+1331=103+113a3+b3=(a+b)(a2−ab+b2) にa=10,b=11 を代入して計算すると、103+113=(10+11)(102−10×11+112)=21×11121×111=3×7×3×37=32×7×371343=1000+1331=10^3+11^3\\a^3+b^3=(a+b)(a^2-ab+b^2)  に\\a=10,b=11  を代入して計算すると、\\10^3+11^3=(10+11)(10^2-10\times11+11^2)=21\times111\\21\times111=3\times7\times3\times37=3^2\times7\times37

    素数判定の方法の応用

    最後に1つずつ素数で割るときの「どこまでやるか」の判定法です。これは素数判定の方法を応用します。

    自然数 n の約数を調べるには、nまでの数で割れるか調べればよい。自然数  n  の約数を調べるには、\sqrt{n}までの数で割れるか調べればよい。

    これはn\sqrt{n}を超えると既出の数との掛け算でnnになるという性質を利用しています。

    これを利用すると、「どこまで調べればよいか」が分かります。

    例題:323を素因数分解せよ。例題:323を素因数分解せよ。

    182=32418^2=324より18までの素数で割れるか調べればよいので、
    323÷2→×323÷3→×323÷5→×323÷7→×323÷11→×323÷13→×323÷17=19 〇323\div2\to\times\\323\div3\to\times\\323\div5\to\times\\323\div7\to\times\\323\div11\to\times\\323\div13\to\times\\323\div17=19  〇
    よって、323=17×19323=17\times19

    平方根の整理の応用

    これは平方根の整理を大体暗記している人限定で、本来は素因数分解して整理するところを暗記している人は逆算でできるということです。例えば、12=23\sqrt{12}=2\sqrt{3}や18=32\sqrt{18}=3\sqrt{2}はよく使うので覚えている人は多いと思います。整理するときに外に出すものは基本的に2乗なので、これらのことから12=22×3,18=32×212=2^2\times3,18=3^2\times2とできます。

    練習問題

    次の数を素因数分解せよ。(1) 171(2) 496(3) 19422次の数を素因数分解せよ。\\(1)  171\\(2)  496\\(3)  19422




    ↓↓↓ 解答・解説 ↓↓↓



    解答・解説

    (1) 1+7+1=9 なので 171 は 9 で割り切れる。   171÷9=19 なので、171=9×19(2) 496 を地道に 2 で割っていくと、496=24×31(3) 普通に分解するのは大変なので、少し工夫する。   19422=2×9711=2×(1002−172)=2×(100−17)×(100+17)  =2×83×117=2×83×9×13=2×32×13×83(1)  1+7+1=9  なので  171  は  9  で割り切れる。\\    171\div9=19  なので、171=9\times19\\(2)  496  を地道に  2  で割っていくと、496=2^4\times31\\(3)  普通に分解するのは大変なので、少し工夫する。\\    19422=2\times9711=2\times(100^2-17^2)=2\times(100-17)\times(100+17)\\   =2\times83\times117=2\times83\times9\times13=2\times3^2\times13\times83


    この記事が参加している募集

     
     
    数学とPythonが好きな人です。 主に数学と自作のPythonプログラムの解説記事を書いています。 最近はBVE関連にハマってます… X垢(主にBVE):https://x.com/__init__92435

    あなたへのおすすめ