数学の質問です。写真の問題でどうして、5n+6と3n+1の最大公約数は、n-4と13の最大公約数に等

数学の質問です。写真の問題でどうして、5n+6と3n+1の最大公約数は、n-4と13の最大公約数に等しいといえるのでしょうか

質問者からの補足コメント

• 忘れてました

  
    補足日時：2022/08/06 14:18

No.4 ベストアンサー 回答者： mtrajcp 回答日時： 2022/08/06 16:47

5n+6と3n+1の最大公約数をdとすると

5n+6=ad…(1)
3n+1=bd…(2)
(a,b)=1
となるa,bがある

5n+6-(3n+1)=2n+5
↓これに(1),(2)を代入すると
ad-bd=2n+5
(a-b)d=2n+5…(3)

3n+1-(2n+5)=n-4
↓これに(2),(3)を代入すると
bd-(a-b)d=n-4
(2b-a)d=n-4…(4)

2n+5-2(n-4)=13
↓これに(3),(4)を代入すると
(a-b)d-2(2b-a)d=13
(3a-5b)d=13…(5)

(2b-a,3a-5b)=cとすると

2b-a=xc
3a-5b=yc
となるx,yがある
6b-3a=3xc
b=(3x+y)c
xc=2b-a=2(3x+y)c-a
a=2(3x+y)c-xc=(5x+2y)c
cはaとbの公約数になる
aとbは互いに素だから
c=1
だから
(2b-a,3a-5b)=1
(2b-a)d=n-4…(4)
(3a-5b)d=13…(5)
だから
(5n+6と3n+1の最大公約数)
d
は
n-4と13の最大公約数

No.6 回答者： ありものがたり 回答日時： 2022/08/06 22:37

gcd{ 5n+6, 3n+1 }

= gcd{ 3n+1, 2(3n+1)-(5n+6) } = gcd{ 3n+1, n-4 }
= gcd{ n-4, (3n+1)-3(n-4) } = gcd{ n-4, 13 }.

No.5 回答者： windwald 回答日時： 2022/08/06 18:42

写真、逆立ちして読めって言うの……？

図が無いのだから、この程度なら文字を打ち込みましょう。

この回答へのお礼

ごめんなさい。気づきませんでした。ほんとにごめんなさい。

お礼日時：2022/08/10 21:03

No.3 回答者： t_fumiaki 回答日時： 2022/08/06 16:07

a,bでaをbで割った余りをcとすると、

a,bの最大公約数=b,cの最大公約数。（証明は自身で調べる）

b,cの最大公約数は、bと(bをc割った余りd）との最大公約数
・
・
と続く。


例えば
48と18の最大公約数は6。
48÷18は余り12だから、18と12最大公約数は6。上の6と同じになる。

これを繰り返し使ってるのがユークリッドの互除法
例 96と36の最大公約数を求める。
・96÷36は商2余り24

36と24の最大公約数を求める。
・36÷24は商1余り12

24と12の最大公約数を求める。
・24÷12は商2余り0 だから最大公約数は12

これを遡れば、最大公約数は12
96と36の最大公約数＝36と24の最大公約数=24と12の最大公約数だから。

これを文字式で行なってるのが問題の写真の内容。

No.2 回答者： ほい3 回答日時： 2022/08/06 14:43

13a=5n+6　公約数はそれを素数にもつので　

13b=3n+1　と表せる
13(a-b)=2n+5

2n+5が13の倍数になるには
2n+5=13　で、n=4
2n+5=26　で、割り切れず無理
2n+5=39　で、n=17
13づつ増えそうでn=30、43
次は56で50超えで無理

質問とはずれてますが…

No.1 回答者： kairou 回答日時： 2022/08/06 14:19

写真が 見当たりませんが。