【証明】隣商差と商余和

【予想–Hypotheses】

ユークリッド除法において、漸化式q(n+1)=2q(n)+r(n)が成り立つとき、s(n)=q(n+1)-q(n)=q(n)+r(n)

なお、このs(n)を「商余和」或いは「隣商差」と呼び、定義する。

【証明–Proof】

ユークリッド除法において、次のように式を定める。

q(n+1)=2q(n)+r(n)ー①

ただし、q(n)、r(n)はそれぞれ、第n項の商、第n項の剰余である。

両辺にr(n)を足して、

q(n+1)+r(n)=2{q(n)+r(n)}ー②

②は、前回証明した合同式の定理より、

q(n+1)+r(n)≡2{q(n)+r(n)}≡0(mod2)

合同式の原理から、mを定数とすると、

2{q(n)+r(n)}=2m

q(n)+r(n)=mー③

同様に、

q(n+1)+r(n)=2m

③で、r(n)=m-q(n)より、

q(n+1)-q(n)=mー④

③、④より、

q(n+1)-q(n)=q(n)+r(n)ー⑤

⑤はmに等しいから、m=s(n)とおくと、

s(n)=q(n+1)-q(n)=q(n)+r(n)

∴ユークリッド除法において、漸化式q(n+1)=2q(n)+r(n)が成り立つとき、s(n)=q(n+1)-q(n)=q(n)+r(n)

【補足】

命題の意味をユークリッド除法的にすると、(被除数)-(商)=(商)+(剰余)となる。この右辺を「商余和」と呼んでいる。

【編集後記】

前回に引き続き、整数論の研究である。実はこんな証明しなくても、ただ2q(n)をq(n)に分割して移項でいいのだけど、見つけた当時はこんな流れだったので。ちなみに、この規則性の成立により、除数2で割っていったときの被除数の規則性が上の漸化式で判明するので、今後の研究が容易になることを期待している。

例;8を2進展開するとき。ただし、括弧内の値は被除数から次の被除数を引いた値である。

8=4×2+0…s=4(8-4=4)

4=2×2+0…s=2(4-2=2)

2=1×2+0…s=1(2-1=1)

1=0×2+1…s=1(1-0=1)

このように、規則性が存在するので、これを参考に整数論を展開させていける。

今後は、ユークリッド除法の一般項を探すが、その過程で新たな法則を見つけられるように努力したい。