RPGツクールと数学のブログ

RPGツクールと数学についてのブログです。

素数を合成数+合成数に分解する

過去の記事の再考です:

blogs.yahoo.co.jp

例えば30個のブロックを長方形状に並べようと考えます。5×6とか、3×10とか、色々な長方形として並べられますね。

f:id:fermiumbay13:20180316022954p:plain

しかし、31個のブロックとなると話が変わります。31は素数なので、1×31、31×1、のパターンしか無いのです。短辺が1の長方形として並べましたーー、なんて言ってみても、え?これが長方形??などとあしらわれます。

f:id:fermiumbay13:20180316023006p:plain

31に限らず、並べる個数が素数の場合は常にこの問題が生じます。それでも何とかしてきれいに並べることはできないものでしょうか。

そこで、一つの長方形として並べるのではなく、二つの長方形として並べることを考えてみます。これなら個数が素数でも、一辺が2以上であるような長方形として並べることが出来そうです。実際、例えば3×7+5×2=31の等式があるので、二つの長方形として31個のブロックを並べきることができます。

f:id:fermiumbay13:20180316023428p:plain… 3×7+5×2=31

任意の素数合成数合成数の形で表現することが可能であれば、個数が素数であっても長方形状に並べることが可能となりますね。合成数合成数素数の表示が可能となれば、両辺に何か数を掛けることによって、合成数合成数合成数の表示も可能になります。

合成数合成数素数の表示が可能となる素数の条件

例えば2の場合は、2=1+1しかないので、明らかに合成数合成数にはできません。素数が小さい場合はどうしても無理なようです。では、素数がある程度大きくなれば常に合成数合成数の表示が可能となるでしょうか?? という問題を解決しましょう。

実は13以上の素数であれば常に可能です。THさんにいただいた美しい証明:

任意の素数pについて、 ab+cd=pを満たす2以上の自然数a,b,c,dが存在する条件を求める。

ここでa=b=3, c=2とすると、 p=9+2dと表される。 d \ge 2より右辺は 13以上の任意の奇数であり、 13以上の素数 pは常に奇数であるから、 pに対応する dは常に存在する。

逆に、13未満の素数(2, 3, 5, 7, 11)はいずれのパターンも不可能と簡単に分かります。13未満は不可、13以上は常に可能、ということですね!

こんなすっきりと証明出来るなんて……THさんに感謝さまさまです。

合成数の組を探す方法

13以上の素数であれば必ず合成数合成数で表すことができるので、具体的にその合成数の組を探す手順を示します。

素数 pについて、 ab+cd=pを満たす2以上の自然数 a,b,c,dを求める。

① 好きな数 aを決める。

 \displaystyle \frac{p-a}{a+1} \gt cを満たす cを決める。

不定方程式 ab+cd=pを満たす自然数 b, dを求める。

③の b,dは次の式に当てはめると自動で求まります。

 \displaystyle f(a, c)=\begin{cases}0 \qquad (c = 1)\\ \frac{1 - c f(c, a \mod c)}{a \mod c} \qquad (c \ne 1)\end{cases} として

 \displaystyle \frac{1-p\frac{1-af(a, c)}{c}}{a} \lt n \lt \frac{pf(a,c)-1}{c} を満たす整数 nを決めて

 \displaystyle \begin{cases}b=pf(a,c)-cn\\d=p\frac{1-af(a, c)}{c}+an\end{cases}

 a, cは比較的自由に決めることができ、これにより長方形の形を概ね決めることができます。

例:83を分解する

試しに 83を分解してみましょう。 p=83として、 ab+cd=83と表します。

 aは好きな数で指定可能です。 a=7としましょう。

次に cを求めます。 \displaystyle \frac{p-a}{a+1}=\frac{83-7}{7+1}=\frac{76}{8}=9.5 \gt cより、 9以下なら何でも良いです。 c=9としましょう。

 b, dを求めるため、上記の③の過程の nの範囲を求めます。

 \displaystyle f(a, c)=f(7, 9)=\frac{1 - 9 f(9, 7)}{7}=\frac{1 - 9 \frac{1 - 7 f(7, 2)}{2}}{7}=\frac{1 - 9 \frac{1 - 7 \frac{1 - 2 f(2, 1)}{1}}{2}}{7}

 \displaystyle =\frac{1 - 9 \frac{1 - 7 \frac{1 - 2 \times 0}{1}}{2}}{7}=\frac{1 - 9 \frac{1 - 7}{2}}{7}=\frac{1 + 27}{7}=4 

 nの範囲の下限は
 \displaystyle \frac{1-p\frac{1-af(a, c)}{c}}{a}=\frac{1-83\frac{1-7f(7, 9)}{9}}{7}=\frac{1-83\frac{1-7\times 4}{9}}{7}=\frac{1+83\times 3}{7}=\frac{250}{7}=35.7\cdots 

 nの範囲の上限は
 \displaystyle \frac{pf(a,c)-1}{c}=\frac{83f(7,9)-1}{9}=\frac{83\times4-1}{9}=\frac{331}{9}=36.7\cdots 

となることから 35.7 \lt n \lt 36.7となり、範囲を満たすのは n=36だけとなります。

 \displaystyle \begin{cases} b=83 \times 4-9\times36=8 \\ d=83 \times \frac{1-7 \times 4}{9}+7\times 36=83 \times(-3)+7\times 36=3\end{cases}

以上より、次の式表示が可能になります。

 7\times8+9\times3=83

f:id:fermiumbay13:20180318083224p:plain… 7×8+9×3=83

これなら、ブロックの個数が実は素数だなんて気付きませんね!

導出

 ab+cd=pは、 a,c,pを定数とみると、未知数が b,d不定方程式と見なせます。一次不定方程式は、整数 nを用いた解の表示が可能です:

blogs.yahoo.co.jp

 b, d \gt 1の条件を使うと、 nの範囲は次式に定まります。

 \displaystyle \frac{1-p\frac{1-af(a, c)}{c}}{a} \lt n \lt \frac{pf(a,c)-1}{c}

この範囲を満たすnが存在する ⇔ 解b,dが存在する ということになります。逆に言うと、定数a, cはこの範囲にnが存在するようなものでなければなりません。

ここで、実数\alpha,\beta、整数nについて\alpha \lt n \lt \betaを満たす nは、 \beta-\alpha \gt 1であれば必ず存在します。数直線のイメージで言えば当然なのですが、証明しようと思うとややこしいです(R-Z存在定理という臭い名前で呼んでいました):

blogs.yahoo.co.jp

これを使って、nが必ず存在するための条件を求めます:

 \displaystyle \frac{pf(a,c)-1}{c}-\frac{1-p\frac{1-af(a, c)}{c}}{a} \gt 1
 \displaystyle a\left(pf(a,c)-1\right)-c\left(1-p\frac{1-af(a, c)}{c}\right) \gt ac
 \displaystyle a\left(pf(a,c)-1\right)-\left(c-p(1-af(a, c))\right) \gt ac
 \displaystyle apf(a,c)-a-c+p(1-af(a, c)) \gt ac
 \displaystyle apf(a,c)-a-c+p-apf(a, c) \gt ac
 \displaystyle p \gt a+c+ac

任意の素数 pに対して、自然数 a,cがこの条件を満たせば必ず対応する解 b,dが存在するということになります。範囲を満たしていなくても存在するかもしれないですが、探すのは大変なので、この条件をもとに探すのが妥当でしょう。

 aを好きに決めて、 cの範囲を求める形にするよう変形すれば、

 \displaystyle \frac{p-a}{a+1} \gt c

となります。これで前述の手順が得られます。