帰納法の問題について

次のような問題で悩んでおります。

問：どのような自然数k,lを用いても6k+13lと書き表すことができない最大の整数nを求めよ。

最終的にはこれを帰納法で証明しろという問題なのですが、帰納法証明自体は
手順としてはわかるのですが、このnを求めるのがわかりません。
地道に計算していくしかないのでしょうか？
手元にある教科書では、nが6k+13lと書けないことの証明（n-13lは6の倍数ではない）
はあるのですが、それが最大の整数だということの説明がなくて困っています。（ちなみにこの問題の回答はn=59）

おそらく帰納法自体を私がちゃんと理解できてないのでわからないと
おもっているのですが、どなたかわかる方教えてください。

No.3 ベストアンサー 回答者： mis_take 回答日時： 2007/01/31 15:05

「帰納法」ではなく「数学的帰納法」ですね。

帰納法はいくつかの事例から結論を類推することで，得られた結論が正しい保証はありません。したがって証明とは認められません。
類推した結論を正確に証明するの方法のひとつが，数学的帰納法です。

この問題で数学的帰納法で証明したいことは何でしょうか？
６ｋ＋１３ｌの形で表せない数をいろいろ探して 59 が最大の数らしいことがわかります。
P(n)：「59より大きいｎはこの形で表せない」
を数学的帰納法で示します。

ふつうの数学的帰納法は
(1) P(1)
(2) P(m)⇒P(m+1)　（m≧1）
を示すことにより，
(3) P(n)　（n≧1）
を証明しますが，この問題では
(1) P(60),P(61),P(62),P(63),P(64),P(65)
(2) P(m)⇒P(m+6)　（m≧60）
を示すことにより
(3) P(n)　（ｎ≧60）
を証明します。

なお，一般に，a,b が互いに素のとき，ak+bl （k,lは非負整数）で表せない最大の数は，(a-1)(b-1)-1 です。

この回答へのお礼

もともとの問題としては、５９より大きい整数は6k+13lで表せる
ことを示せという問題で、回答としてもほぼお答え頂きました
通りです。

(a-1)(b-1)-1の部分が一番しりたいことでした。
ありがとうございました。

お礼日時：2007/02/01 03:01

No.4 回答者： lick6 回答日時： 2007/01/31 17:22

負でない整数 k , l に対して(つまり k ≧ 0, l ≧ 0 かつ k , l は整数)

n = 6k + 13l で表せる整数は
(i)l = 0 のとき
n は 0 以上のすべての 6 の倍数を取りうる
(ii)l = 1 のとき
n は 13 以上のすべての 6 で割ると 1 余る整数を取りうる
(iii)l = 2 のとき
n は 26 以上のすべての 6 で割ると 2 余る整数を取りうる
・・・
(vi)l = 5 のとき
n は 65 以上のすべての 6 で割ると 5 余る整数を取りうる
(vii)l ≧ 6 のとき
l を 6 で割った商を q ,余りを r とすると
l = 6q + r (q ≧ 1 , r = 0 , 1 , 2 , 3 , 4 , 5) と表せ
n = 6k + 13l
　 = 6k + 13(6q + r)
　 = 6(k + 13q) + 13r
となり r の値で (i)～(vi) のいずれかに含まれる

数学的帰納法かどうかはわかりませんが、このようにすれば有限個を調べて終わりにできますね。

＃３さんがおっしゃっていますが
a,b が互いに素のとき，ak + bl （k , l は自然数）は ab + 1 以上のすべての自然数を表すことができる。
k , l が自然数ではなく非負整数のときは
k ≧ 1 , l ≧ 1
ak + bl ≧ ab + 1
a(k - 1) + b(l - 1) ≧ ab - a - b + 1
K = k - 1 , L = l - 1 とすると
K ≧ 0 , L ≧ 0
aK + bL ≧ ab - a - b + 1
　　　　　 = (a - 1)(b - 1)
とすることで導けます。

「a,b が互いに素のとき，ak + bl （k , l は自然数）は ab + 1 以上のすべての自然数を表すことができる」の証明は
n ≧ ab + 1 のとき
n - ab ≧ 1
このとき「b 個の数 a , 2a , 3a , … , ba を b で割った余りはすべて異なる」という定理から
n - a , a - 2a , n - 3a , … , n - ba を b で割った余りはすべて異なる
つまりこの中に一つ b で割り切れるものが必ず存在する
そのとき n - ka と表すと
n - ka = bl という形で表せる
∴ n = ka + bl という形で表せる

この回答へのお礼

ご回答ありがとうざいました。

お礼日時：2007/02/01 03:03

No.2 回答者： age_momo 回答日時： 2007/01/31 13:51

#1です。

投稿してから気づきました。k,lは自然数ではなく、負でない整数ですかね。
それなら下の式

(n-1)=6(k+2)+13(l-1)=6(k-11)+13(l+1)

のどちらも出来なくなるのはk<11,l<1ですから

6*10+13*0=60

1引いて59ですね。

この回答へのお礼

回答ありがとうございます。
ご指摘の通り自然数ではなく、非不整数です。
ご迷惑おかけいたしました。

お礼日時：2007/02/01 02:56

No.1 回答者： age_momo 回答日時： 2007/01/31 13:44

＞ちなみにこの問題の回答はn=59

？？？60は書き表せますかね？？？78ではないですか？

とりあえず、もしk,lに自然数と言う制約がつかなければ全ての整数を

6k+13l

で表すことが出来るのはいいでしょうか？

6*(-2)+13*1=1

ですから両辺に任意の整数をかければその整数ができます。
だからk,lが十分に大きければn=6k+13lなら(n+1)=6(k-2)+13(l+1)で
(n+1)を表すことが出来るはずですね。
逆に考えれば

(n-1)=6(k+2)+13(l-1)

で表すことができ、また、k>11なら

(n-1)=6(k+2)+13(l-1)=6(k-11)+13(l+5)

とすることが出来ます。これらどちらも出来なくなるのはl≦1、k≦11
よって求める数字は

6*11+13*1=79

から1を引いた78となると思います。