ユークリッドの互除法

nを自然数としたとき、10n+40と3n+13の最大公約数をnの値によって場合分けして答えよ 至急でお願いします。 ユークリッドの互除法をやったあとからわかりません。

こんにちは。 コメントをありがとうございました。 大変参考になりました。 A=10n+40、B=3n+13としておきます。 ユークリッドの互除法そのものではなく、その原理に AとBの最大公約数は、A=p×B+Rと書けたときのBとRの最大公約数に等しい があります。余りといってしまうと割る数より小さくなければなりませんが、そうでなくとも大丈夫で、たとえば 42と12について42＝2×12＋18として（１８は余りではない）も、 42と１２の最大公約数は１２と１８の最大公約数に等しい ということが成り立ちます。 よって、この問題ではユークリッドの互除法でやった余りかどうかわからないもの、たとえば２回目の互除をやった時の１０が割る数n+1より小さいかどうかわからなくても、１０とn+1の最大公約数はさかのぼっていくと10n+40と3n+13の最大公約数に等しいことがわかりますね。 A=3B+(n+1) B=3(n+1)+10 ここまででAとBの最大公約数はn+1と１０の最大公約数に等しいとわかり、しかも10の約数は1,2,5,10しかありません。 この先は具体的に考えるしかないです。 n+1が2を約数に持つのはnが奇数のとき。 n+1が5を約数に持つのはnの一の位が4か9のとき。 n+1が2も5も約数にもたないのは一の位が4以外の偶数のとき。 これで答が書けますね。 これで大丈夫ですか? わかったとか、このあたりがまだよくわからないとか、コメント欄に返事を書いてくださいね。よろしく。