- C/C++の宿題片付けます 167代目
998 ：オナヌ[sage]：2014/08/25(月) 12:20:35.37 ID:famPiloD - 7x-14y=1 に整数解が無い理由→左辺は7の倍数だが右辺はそうではない
7x-4y=1 に整数解がある理由→7x(x=0,1,2,3)を4で割った時の余りが
すべて異なるので4で割って1あまるものがある→7x0=1+4y0となるx0,y0
がある→整数解を持つ
7x(x=0,1,2,3)を4で割った時の余りが異なる理由→余りが同じ0<=x0,x1<=3
(x0≠x1)で7(x0-x1)は4の倍数だが7と4の互いに素なのでx0-x1が
4の倍数だがこれはありえない
7x-14y=2に整数解がある理由→7x-14y=1に整数解があるから2x,2yという
整数解がある
7x-14y=28に整数解がある理由→7,14の最大公約数7で右辺が割れるから
両辺が割れてx-2y=4.最大公約数で割った数同士は互いに素だから
7x-4y=1,7x'-4y'=1を満たす４つの整数x,x',y,y'の関係
7(x-x')=4(y-y')=z
zは7,4の倍数だから7,4の公倍数で、7,4の最小公倍数の倍数
（公倍数は最小公倍数の倍数だから）
z=LCM(7,4)t (tは整数)
∴x'=x+(LCM(7,4)/7)t
|