【証明】ユークリッド除法における「被除数と剰余の和」
【予想–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を公差とする等差数列】である。
