不定方程式の最小値

質問

5で割ると2余り、7で割ると4余り、11で割ると8余るような自然数nで最小のものを求めよ。

という問題で、x =6,y=4 の整数解を使うと上手く答えが出るのですが、他の解を使うと答えが一致しないのですが、何故でしょう？

解答にあった答えは、382 でした

回答No.3

asuncion · ベストアンサー

別の特殊解を使いましょうか。
5で割ると２あまり、7で割ると４あまり、11で割ると8あまる自然数をnとすると、
n = 5x + 2, n = 7y + 4, n = 11z + 8（x, y, zは整数）と表わせる。
5x + 2 = 7y + 4より5x - 7y = 2 ... (1)
x = 20, y = 14は(1)の整数解の1つだから、
5・20 - 7・14 = 2 ... (2)
(1) - (2)より5(x - 20) - 7(y - 14) = 0, 5(x - 20) = 7(y - 14)
x - 20 = 7k, y - 14 = 5k（kは整数）
x = 7k + 20, y = 5k + 14
n = 5x + 2 = 5(7k + 20) + 2 = 35k + 102 ... (3)
7y + 4 = 11z + 8より、7y - 11z = 4 ... (4)
y = 32, z = 20は（４）の整数解の１つだから、
7・32 - 11・20 = 4 ... (5)
(4) - (5)より7(y - 32) - 11(z - 20) = 0, 7(y - 32) = 11(z - 20)
y - 32 = 11m, z - 20 = 7m（mは整数）
y = 11m + 32, z = 7m + 20
n = 7y + 4 = 7(11m + 32) + 4 = 77m + 228 ... (6)
(3)(6)より35k + 102 = 77m + 228, 35k - 77m = 126, 5k - 11m = 18
k = 8, m = 2は特殊解の１つだから、5(k - 8) - 11(m - 2) = 0
5(k - 8) = 11(m - 2)
k - 8 = 11s, m - 2 = 5ｓ（sは整数）
k = 11s + 8, m = 5s + 2
n = 35k + 102 = 35(11s + 8) + 102 = 385s + 382
これはs = 0のとき最小だから、求めるn = 382
同じ結果になりましたね。

お礼

ありがとうございました。
とても分かりやすかったです。

回答No.4

f272

#1です。
「5で割ると2余り、7で割ると4余り、11で割ると8余るような自然数n」に3を加えると，5と7と11の公倍数になることは明らかです。そのような自然数nで最小であるものは5と7と11の最小公倍数から3を引いたものになるので，382だということはすぐわかります。
何か難しく考えているのではないですか？

お礼

ありがとうございます。
そんな簡単な解き方があったんですね。

回答No.2

asuncion

5で割ると２あまり、7で割ると４あまり、11で割ると8あまる自然数をnとすると、
n = 5x + 2, n = 7y + 4, n = 11z + 8（x, y, zは整数）と表わせる。
5x + 2 = 7y + 4より5x - 7y = 2 ... (1)
x = 6, y = 4は(1)の整数解の1つだから、
5・6 - 7・4 = 2 ... (2)
(1) - (2)より5(x - 6) - 7(y - 4) = 0, 5(x - 6) = 7(y - 4)
x - 6 = 7k, y - 4 = 5k（kは整数）
x = 7k + 6, y = 5k + 4
n = 5x + 2 = 5(7k + 6) + 2 = 35k + 32 ... (3)
7y + 4 = 11z + 8より、7y - 11z = 4 ... (4)
y = 10, z = 6は（４）の整数解の１つだから、
7・10 - 11・6 = 4 ... (5)
(4) - (5)より7(y - 10) - 11(z - 6) = 0, 7(y - 10) = 11(z - 6)
y - 10 = 11m, z - 6 = 7m（mは整数）
y = 11m + 10, z = 7m + 6
n = 7y + 4 = 7(11m + 10) + 4 = 77m + 74 ... (6)
(3)(6)より35k + 32 = 77m + 74, 35k - 77m = 42, 5k - 11m = 6
k = 10, m = 4は特殊解の１つだから、5(k - 10) - 11(m - 4) = 0
5(k - 10) = 11(m - 4)
k - 10 = 11s, m - 4 = 5ｓ（sは整数）
k = 11s + 10, m = 5s + 4
n = 35k + 32 = 35(11s + 10) + 32 = 385s + 382
これはs = 0のとき最小だから、求めるn = 382

お礼

ありがとうございました。
しっかり理解できました。

回答No.1

f272

「x =6,y=4 の整数解」というのがなんだかわかりませんが，とにかくあなたが計算間違いをしているだけです。

お礼

少し問題を錯覚していました。
ありがとうございます。