回答編集履歴
1
補足
answer
CHANGED
|
@@ -1,7 +1,11 @@
|
|
|
1
1
|
(証明)以下、積は*記号を用いず文字を並べて表現する。
|
|
2
2
|
n = pa + q, p = rb + s(ただし、p, q, r, sは0以上の整数で、q < a, s < b)とする。
|
|
3
3
|
この時、n / a / b = rである。
|
|
4
|
-
n = (rb + s)a + q = rab + (sa + q)
|
|
4
|
+
n = (rb + s)a + q = rab + (sa + q)
|
|
5
|
+
|
|
6
|
+
ここでsa + q < abが示せれば、nをabで割った商がr,余りがsa + qということになり、
|
|
7
|
+
n / ab = rとなる。
|
|
8
|
+
|
|
5
9
|
sa + q - ab = a(s - b) + q
|
|
6
10
|
s, bは0以上の整数でs < bなのでs - bは-1以下の整数
|
|
7
11
|
よってa(s - b) <= -a
|