整数問題

質問

二つの奇数a，b にたいして，m = 11a + b，n = 3a + b とおく．つぎのことを証明せよ．
m，n の最大公約数は，a，b の最大公約数をd として，2d，4d，8d のいずれかである．

僕はユークリッドの互除法を考えました。
(11a+b)=(3a+b)*1+8a
よってmnの最大公約数は3a+bと8aの最大公約数である。
さらに(3a+b)=(3/8)*8a+b
として8aとbの最大公約数が求める最大公約数と考えましたが、ここで矛盾が生じます。
bは奇数であるので偶数の2d等を因数に持たない。
よく考え直してみたのですが、ユークリッドは商が整数にならなければならないのでしょうか？2回目にユークリッドを使うときに商が3/8となってるのがまずいのでしょうか？
またこの問題はどう解いたらよいでしょうか？教えてください。

回答No.1

take_5

＞僕はユークリッドの互除法を考えました。

そういう感覚が必要な、ちょつと面白い問題だ。

m-n＝8a、11n-3m＝8bである。
従って、mとnの最大公約数kは8aと8bの公約数でもある。条件から、a＝pd、b＝qd　（dは奇数、pとqは互いに素）とすると、8aと8bの公約数は8dの約数でもある。
又、aもbも奇数であるから、mとnは偶数で、and、dの倍数から、mとnの最大公約数は　2d　の倍数である。
以上より、mとnの最大公約数は　8d　の約数であるから、2d、or、4d、or、8d。

お礼

回答ありがとうございます。
おもしろい問題ですね