質問編集履歴
2
自己解決につき〆切
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -144,6 +144,10 @@
|
|
|
144
144
|
|
|
145
145
|
|
|
146
146
|
|
|
147
|
+
2019/02/27 追記: 〆切ました。
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
147
151
|
### extgcd が問題の条件を満たす解を与えることの証明
|
|
148
152
|
|
|
149
153
|
|
1
自分なりに考えた証明を追記
test
CHANGED
|
File without changes
|
test
CHANGED
|
@@ -129,3 +129,97 @@
|
|
|
129
129
|
|
|
130
130
|
|
|
131
131
|
[AOJ submission](https://onlinejudge.u-aizu.ac.jp/status/users/tyanon/submissions/1/NTL_1_E/judge/3398056/C++14)
|
|
132
|
+
|
|
133
|
+
|
|
134
|
+
|
|
135
|
+
----
|
|
136
|
+
|
|
137
|
+
|
|
138
|
+
|
|
139
|
+
2019/02/25 追記:
|
|
140
|
+
|
|
141
|
+
|
|
142
|
+
|
|
143
|
+
[StackExchange の記事](https://math.stackexchange.com/questions/670405/does-the-extended-euclidean-algorithm-always-return-the-smallest-coefficients-of) を参考にしつつ証明を考えてみました。あまりこういうのは書いたことがないので、間違っていたらご指摘いただきたいです。正しいという確信が得られるまでもうしばらく回答を受け付けたいと思います。
|
|
144
|
+
|
|
145
|
+
|
|
146
|
+
|
|
147
|
+
### extgcd が問題の条件を満たす解を与えることの証明
|
|
148
|
+
|
|
149
|
+
|
|
150
|
+
|
|
151
|
+
※gcd(0,0)=0 と定義する。
|
|
152
|
+
|
|
153
|
+
|
|
154
|
+
|
|
155
|
+
a,b を整数とする。g=gcd(a,b) および ax+by=g の整数解 (X,Y) を求める関数 extgcd(a,b)=(g,X,Y) を考える。
|
|
156
|
+
|
|
157
|
+
|X|+|Y| が最小の解を最小解と呼ぶ(唯一とは限らない)。
|
|
158
|
+
|
|
159
|
+
|
|
160
|
+
|
|
161
|
+
* extgcd(a,b)=(g,X,Y) ならば extgcd(-a,b)=(g,-X,Y), extgcd(a,-b)=(g,X,-Y) なので、a>=0, b>=0についてのみ考えれば十分。
|
|
162
|
+
|
|
163
|
+
* gcd(a,b)>1 のとき、a=ga', b=gb' とおくと、ax+by=g は a'x+b'y=1 に帰着する。よって、gcd(a,b)<=1 についてのみ考えれば十分。
|
|
164
|
+
|
|
165
|
+
* extgcd(a,b)=(g,X,Y) ならば extgcd(b,a)=(g,Y,X) なので、a>=b についてのみ考えれば十分。
|
|
166
|
+
|
|
167
|
+
* extgcd(0,0)=(0,0,0), extgcd(1,0)=(1,1,0), extgcd(1,1)=(1,0,1) と定義する。いずれも最小解になっている。
|
|
168
|
+
|
|
169
|
+
|
|
170
|
+
|
|
171
|
+
以上より、後は gcd(a,b)=1, a>b>=2 についてのみ考えれば十分。
|
|
172
|
+
|
|
173
|
+
extgcd(a,b)=(1,X,Y) とする。a を b で割って a=qb+r と表す (0<r<b)
|
|
174
|
+
|
|
175
|
+
extgcd(b,r)=(1,X',Y') ならば、bX'+rY'=1 に r=a-qb を代入して
|
|
176
|
+
|
|
177
|
+
X=Y', Y=X'-qY' が得られる。
|
|
178
|
+
|
|
179
|
+
|
|
180
|
+
|
|
181
|
+
このとき、|X|<=b/2, |Y|<=a/2 が成り立つことを帰納法で示す。
|
|
182
|
+
|
|
183
|
+
|
|
184
|
+
|
|
185
|
+
g=gcd(a,b)=1 だから、extgcdの再帰呼び出し中のある時点で第2引数が1になる。この直前の extgcd(A,B) を考える。
|
|
186
|
+
|
|
187
|
+
A=QB+1, A>B>=2 である。
|
|
188
|
+
|
|
189
|
+
extgcd(B,1)=(1,0,1) より、extgcd(A,B)=(1,1,-Q) である。よって
|
|
190
|
+
|
|
191
|
+
|1|<=B/2, |-Q|=Q<=QB/2<A/2 より、A,B については命題は成り立っている。
|
|
192
|
+
|
|
193
|
+
|
|
194
|
+
|
|
195
|
+
次に一般の a,b について考える。a=qb+r, extgcd(a,b)=(1,X,Y) とする。
|
|
196
|
+
|
|
197
|
+
extgcd(b,r)=(1,X',Y'), |X'|<=r/2, |Y'|<=b/2 ならば、
|
|
198
|
+
|
|
199
|
+
|X|=|Y'|<=b/2
|
|
200
|
+
|
|
201
|
+
|Y|=|X'-qY'|<=|X'|+|qY'|<=r/2+qb/2=(qb+r)/2=a/2
|
|
202
|
+
|
|
203
|
+
より、a,b についても命題は成り立つ。
|
|
204
|
+
|
|
205
|
+
|
|
206
|
+
|
|
207
|
+
よって命題は gcd(a,b)=1, a>b>=2 なる全ての a,b について成り立つ。
|
|
208
|
+
|
|
209
|
+
|
|
210
|
+
|
|
211
|
+
ところで、ax+by=1 の一般解は (x,y)=(X+mb,Y-ma) と表せる。
|
|
212
|
+
|
|
213
|
+
|X|<=b/2 より、m!=0 のとき |X+mb|>=|X|
|
|
214
|
+
|
|
215
|
+
|Y|<=a/2 より、m!=0 のとき |Y-ma|>=|Y|
|
|
216
|
+
|
|
217
|
+
なので、X,Y は最小解である。最小解が他に存在するためには |X|=b/2, |Y|=a/2 でなければならず、このとき aX+bY は ab, 0, -ab のいずれかになるが、いずれも gcd(a,b)=1 に反する。よって、gcd(a,b)=1, a>b>=2 のとき、ax+by=1 の最小解は唯一である。
|
|
218
|
+
|
|
219
|
+
|
|
220
|
+
|
|
221
|
+
他に最小解が複数存在しうるのは (a,b)=(1,1) のみであり、このとき ax+by=1 の最小解は (1,0),(0,1) の2通りある。しかし extgcd(1,1)=(1,0,1) と定義したから、X<=Y は満たされている。
|
|
222
|
+
|
|
223
|
+
|
|
224
|
+
|
|
225
|
+
結局、この extgcd の定義では常に最小解が得られ、最小解が複数ある場合は X<=Y なるものが得られる。証明終
|