素数を合成数＋合成数に分解する - RPGツクールと数学のブログ

例えば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$ を用いた解の表示が可能です：

fermiumbay13.hatenablog.com

$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$ であれば必ず存在します。数直線のイメージで言えば当然なのですが、証明しようと思うとややこしいです：

fermiumbay13.hatenablog.com

これを使って、 $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$