x.yを自然数とする 3x+7yで表すことのできない最大の整数を求めよ やり方を教えてください！

x.yを自然数とする
3x+7yで表すことのできない最大の整数を求めよ

やり方を教えてください！

No.5 ベストアンサー 回答者： majimelon37 回答日時： 2018/09/23 09:42

x.yを自然数とする。

3x+7yで表すことのできない最大の整数を求めよ。
(1)x=1,2,3,4とy=1,2,3,4の時、n=3x+7yとなる数を作る。大きさ順に並べ変える。
x　1 2 3 4　5　6　1　2　3　4　1
y　1 1 1 1　1　1　2　2　2　2 3
n 10 13 16 19 22 25 17 20 23 26 24
並べ替え10 13 16 17 19 20 22 23 24 25 26
ぬけているもの1~9　11 12 14 15 18 21　答えは21となる。後は参考理論。
(2)表すことのできないものを求めるためには、まず表すことのできる方法を知る必要がある。そのために、表したい数をnとして、方程式
n=3x+7y＿①
を解く。ここでx.yを自然数とする条件をはずし、x,yを整数とした時の解を調べる。
これはディオファントス方程式という名で古代ギリシアから知られ、解も解っている。
(3)一般式Ax＋By＝Cをr1x2+r2x1=Cとし、係数A,Bの大きい方をr1=7、小さい方をr2=3とする。B=7，A=3，C=nだからr1=7，r2=3とする。未知数はx1=x，x2=yとなる。
下の表を埋める形式で計算する。割り算の公式を繰り返す。
r1÷r2= 7÷3=q1余りr3からq1=2，r3=1
r2÷r3= 3÷1=q2余りr4からq2=3，r4=0
割り算が割り切れたら、r3=1はA,Bの最大公約数GCMである。解は、まずx3=0とする。x2＝C/GCM=n/1。C/GCMが整数の時だけ解がある。y=x2=n
x1は、公式x1=x3－q1･x2を使う。
x1=x3－q1･x2=0－2･x2=－2n=x　表から、ここまで計算できた。
方程式n=3x+7yはx=－2n ，y=nが一つの解で、n=3(－2n)+7nで成立する。
kを任意整数として、
x=－2n+7k ，y=n－3k＿②が一般解である。
検算n=3x+7y=3(－2n+7k)+7(n－3k)=nが成立する。
(4)x，yが自然数であるためには、x≧1、y≧1が条件だから、②の一般解から
x=－2n+7k≧1＿③
y=n－3k≧1＿④
ABの2通りを調べる。
(A)③④の両方成立するとき
③×3+④×7を作ると
－6n+21k+7n－21k=n≧10＿⑤
n≦9は解がない。
(B)　③から3.5k－0.5≧n＿⑥
④からn≧3k+1＿⑦
⑥⑦から3.5k－0.5≧n≧3k+1＿⑧これが矛盾なく成立するのは⑨の条件をみたす。
3.5k－0.5≧3k+1
0.5k≧1.5
k≧3＿⑨
不等式⑧の下限3k+1と上限3.5k－0.5を表にする。
k= 3， 4， 5， 6， 7， 8， 9， 10， 11，
3k+1=10，13， 16， 19， 22，25， 28， 31， 34
3.5k－0.5=10，13.5，17，20.5，24，27.5，31， 34.5，38
範囲にはずれるのは11，12，14，15，18，21 。
n≧25では範囲が連続となる。

No.7 回答者： syotao 回答日時： 2018/09/24 11:24

nを自然数として

不定方程式、3x+7y＝ｎ･･･①の特殊解としてｘ＝－2ｎ、ｙ＝ｎがとれる。
3x+7y＝0　の一般解はｘ＝7ｔ、ｙ＝－3ｔ（ｔは任意の整数）だから
①の一般解はｘ＝－2ｎ＋7ｔ、ｙ＝－3ｔ＋ｎ　になる。
この一般解でｘ、ｙともに≧1とすれば
(1＋2ｎ)/7≦ｔ≦(ｎ－1)/3･･･②　
つまり①に自然数解があるためには②を満たす整数ｔが存在することが
必要十分条件になる。
②の右辺と左辺の差はｎ≧31ならば１以上になるので
ｎ≧31ならば②をみたす整数ｔは存在する。
またｎ＝22からｎ＝30までについても個別に計算すれば
②をみたす整数ｔを求められるから結局
ｎ≧22ならば①に自然数解が存在する。
ところがｎ＝21について②の左辺右辺を計算するとそれぞれ6.14、6.66になって
②をみたすｔは存在しない。
∴求める答えはｎ＝21です。

No.6 回答者： majimelon37 回答日時： 2018/09/23 15:58

No.5で書き忘れたこと

表を使った方法はユークリッドの互除法という名が付いている。
最大公約数を計算する定番の方法です。
解の公式x[i]=x[i+2]－q1･x[i+1]の方はあまり普及してない。

No.4 回答者： tekcycle 回答日時： 2018/09/21 23:41

まずやり方がぁじゃないです。

自分で色々いじって観察するんです。
最初にやり方を求めるのも良いですが、やり方だらけになって収拾が付かなくなります。

１０はどう表せる？
１１は？
１２は？
１３、１４、１５は表せるとして１６は。
なぜ、何が表せて、なぜ、何が表せない？
１，２は表せませんよね。４、５も無理。
ｎ＜７の場合、表せるのは３ｋだけで３ｋ＋１，３ｋ＋２は表せない。
ところが、６が３ｋで７は３ｋ＋１だけれど、これは表せる。３・０＋７・１。
すると以降、これを使えば、３ｋ＋１に相当する数が３(ｋ－２)＋７で全て表せる。
更に数を大きくしていくと、さてどうなるか。

具体的に数を書き出してみて、具体例に則して観察し、法則や原因を掴む。

No.3 回答者： 文理活 回答日時： 2018/09/21 18:32

任意の 21 より大きい自然数を, 3 で割った余りによって 3 通りに分類すればいい.

No.2 回答者： t_fumiaki 回答日時： 2018/09/21 17:21

以下を参考にして、後は自分で手を動かす。

https://detail.chiebukuro.yahoo.co.jp/qa/questio …

No.1 回答者： doc_somday 回答日時： 2018/09/21 16:59

その数をＡとする。

Ａを７で割った時の余りをＢとする。Ｂが３で割れない時Ａが求める数の一つである。
だがこれでは最大かどうか分からない。