【証明】隣商差と商余和

【予想–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)

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

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

【証明】ユークリッド除法における「被除数と剰余の和」

【予想–Hypothesis】

ユークリッド除法において、被除数pとpに対する剰余rの和を2で割った剰余は0となる。

【証明–Proof】

題意より、次のことがいえる。

p+r≡0(mod2)ー(A)

ユークリッド除法を題意より、漸化式で表す。ただし、qは商とし、第n項の値をq(n)のように表す。

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

q(n)=2q(n-1)+r(n-1)ー②

①式はp=q(n+1)より、次のように表せる。

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

②、③で除法の原理より、q(n+1)-q(n)を2で割った剰余は、r(n)-r(n-1)を2で割った剰余に等しいから、

q(n+1)-q(n)≡r(n)-r(n-1)(mod2)ー④

(以後、法2として考える。)

④に③を代入すると、

2q(n)+r(n)-q(n)≡r(n)-r(n-1)

q(n)+r(n-1)≡0

q(n+1)+r(n)≡0

p+r(n)≡0

以上より、p+r≡0(mod2)となるから、命題Aは証明された。

∴ユークリッド除法において、被除数pと剰余rの和は法を2として0に合同である。 Q.E.D.

この理論が正しいと仮定して拡張すると、除数はどんな値でも一定の形を保った式になると予想されます。ただ単に除数2を3,4,5,...と置き換えて証明できますからね。それはまた後日で。

【補足】用語解説

• ユークリッド除法...p=aq+rにおいて、0≦r<aとする除法の原理。
• 合同式...aをmで割った時の剰余が、bをmで割った時の剰余に等しいとき、a≡b(mod m)と表す。mを法といい、≡で成り立つとき、合同であるという。
• 漸化式...第n項、第n+1項を用いる、規則性がある数列の式。例として、漸化式【a(n+1)=a(n)+d】は【dを公差とする等差数列】である。

一寸先は闇

科学って何があるかわからない。 ー

ー 近々開催される、あるフェスティバルの準備が粗方終わった後の話。

部活動の一環として、息抜き(?)に研究テーマを再構築してやり直そうと参考書とか読み更けていると、ふと、有名なサンドボックスゲーム「minecraft」で昔考えてみた回路の理論があった訳でして…でも、当時の知識では到底解くのも無理難題として放置した、という適当な話があったんですね。

ただ、

「今なら解けるんじゃね？」

っていう、半端なく適当な妄信を元に、1週間前からか、やってみた。

解けないんですよね、これが。

最初はただの、「10進数から2進数に変換する理論の定式化」っていう、数Aの頃にやったことをもっかいやり直しているだけだろうなーと考えていたら、気づけば早1週間…。

とりあえず、現段階で、法則性は間違いなくあると踏んで、数列の漸化式を出すという過程にまで躍り出れた訳です。

ここからが本題で、「一般項は何？」っていう話をして、そこから余についての規則性を定式化し、さらに……嗚呼、終わらない旅（笑）

ちなみに、ここまでやっていることは全て物理の電子回路での一部。数学という森に迷い込んだようです…助けを求めて、それでやっと手掛かりは見つけましたね。ただ、出口は見えそうで見えない…

満足行く答えがあるかはわかりません。証明するまで一寸先は闇ですから ー