「教えて!ピックアップ」リリース!

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

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

  • 忘れてました

    「数学の質問です。写真の問題でどうして、5」の補足画像1
      補足日時:2022/08/06 14:18

A 回答 (6件)

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の最大公約数
    • good
    • 0

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 }.
    • good
    • 0

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


図が無いのだから、この程度なら文字を打ち込みましょう。
    • good
    • 0
この回答へのお礼

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

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

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の最大公約数だから。

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

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超えで無理

質問とはずれてますが…
    • good
    • 0

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

    • good
    • 0

お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!

このQ&Aを見た人はこんなQ&Aも見ています


このQ&Aを見た人がよく見るQ&A

人気Q&Aランキング