7で割ると2余り、11で割ると3余るような300以下の自然数すべて求めよ という問題で最小の58を見

7で割ると2余り、11で割ると3余るような300以下の自然数すべて求めよ
という問題で最小の58を見つけたとき77を足していくとそれが答えになるのはなぜなのでしょうか？

No.1 ベストアンサー 回答者： mtrajcp 回答日時： 2023/12/12 20:10

n=7m+2

n=11j+3

7m+2=11j+3
7m-11j=1

11=7+4
11-7=4
7=4+3
7-4=3
4-3=1
↓この3に3=7-4を代入すると
4-(7-4)=1
4-7+4=1
2*4-7=1
↓この4に4=11-7を代入すると
2(11-7)-7=1
11*2-7*2-7=1
11*2+7(-3)=1
7(-3)-11(-2)=1
↓7m-11j=1からこれを引くと
7(m+3)-11(j+2)=0
7(m+3)=11(j+2)
↓右辺は11の倍数だから左辺も11の倍数だからm+3も11の倍数だから
m+3=11k となる整数kがある
m=11k-3
↓これをn=7m+2に代入すると
n=7(11k-3)+2
n=77k-21+2
n=77k-19
∴
n=77(k-1)+58

No.6 回答者： ssawatake 回答日時： 2023/12/14 20:14

58+77nを7で割ると、77nは割り切れるから、余りは58の方から出る。

58+77nを11で割ると、77nは割り切れるから、余りは58の方から出る。

nは0､1､2､3､･････で良いから、順番に代入すれば、
58に77を足していくのと同じ。

No.5 回答者： mtrajcp 回答日時： 2023/12/13 10:56

nを77で割ると58余る数とすると

n=77k+58

n=77k+58=7(11k+8)+2
だから
nを7で割ると2余る

n=77k+58=11(7k+5)+3
だから
nを11で割ると3余る

だから

58=77*0+58 は答えになる
135=77+58=77*1+58 は答えになる
212=77+135=77*2+58 は答えになる
289=77+212=77*3+58 は答えになる

No.4 回答者： masterkoto 回答日時： 2023/12/12 22:37

7で割ると2余る数は7おきに出現しますよね

だからそのような数は、58の次は
これに7をくわえた65
その次は7×2＝14を加えた72
…
と続きます
同様に11で割ると3余る数は11おきに出現
そして
58に7づつ加えていった数と
58に11づつ加えていった数が次に一致するのはいつかと言うと、いうまでもなく
7づつ加えた数と11づつ加えた数が一致するときです
それは
7×1、7×2、7×3…
11×1、11×2、11×3…
と調べる方法で見れば
7と11の最小公倍数77を加えたときだと気がつくと思います
その次も、一致するのは77を加えたとき…
です
77(×n)を加えた数は
58に7づつ加えていった数であり
58に11づつ加えていった数でもあるので
それは、7で割ると2余り、11で割ると3余るような数になるわけです

No.3 回答者： ありものがたり 回答日時： 2023/12/12 20:15

77 は、7 と 11 の最小公倍数です。

問題の数 x は、x = 7a+2 = 11b+3 (a,bは整数), 0 < x ≦ 300
と表される自然数 n です。
n を求めるためには、7a+2 = 11b+3 を満たす整数 a,b を求めてから
その中で x が 0 < x ≦ 300 を満たすものを求めるとよいでしょう。

7a+2 = 11b+3 すなわち 7a - 11b = 1 を満たす整数 a,b を求めるには、
この式を満たす 7A - 11B = 1 なる A,B を見つけてから、
両式から定数項 1 を消去して 7(a - A) = 11(b - B) を考えればいい。
両辺の値は 7 の倍数かつ 11 の倍数ですから
7(a - a0) = 11(b - b0) = (ｇｃｄ 7,11)k {kは整数} と置くことができて、
a = a0 + k(ｇｃｄ 7,11)/7, b = b0 + k(ｇｃｄ 7,11)/11
が全ての (a,b) になります。

7 と 11 が互いに素なので (gcd 7,11) = 7・11 = 77 であり、
a = a0 + 11k, b = b0 + 7k にです。

No.2 回答者： 閑野 回答日時： 2023/12/12 20:13

７７が７と１１の最小公倍数だからです。

小学校６年生ぐらいで習いませんでしたか？