Question

あ

数Aのユークリッドの互除法のところの問題です。
何故答えが22になるのか分かりません…
どなたか解き方を教えてください！

2
2436, 1182 のどちらを割っても余りが16にな
るような整数のうち, 最大のものを求めよ。
S+$
小
0
22
お茶お激

ユークリッドの互除法

Answer 1

Yuki

2436と1182を何かで割ると余りが16になることより、2436－16=2420 と 1182－16=1166を割った時に割り切れる数の最大の数を考える。
つまり、2420と1166の最大公約数を考える。

ユークリッドの互除法より
2420=1166×2+88
1166=88×13+22
88=22×4

なので最大公約数は22
よって答えは22

Answer 2

内職の「ｳﾞｫﾆ！」です@北大総理絶対合格！

今思いついた解法なんで合ってるか分かりませんが…
それぞれを2436=gn+16,1182=gm+16と起きます。
すると2420=gn,1166=gmとなります。よってこの2数の最大公約数gをユークリッドの互除法で求めれば22が出る…ハズ

Answer 3

ゆう

こうです！

ゆう

あまりが16ってことは、2436-16=2430と1182-16=1166を割ったらあまりは0になる。すなわち、2430と1166の最大公約数を求めれば良い

Answer 4

きょん

2436と1182をそれぞれNで割ったと考える。

この時の商をそれぞれp,qとして
2436=Np+16
1182=Nq+16

変形すると
2420=Np
1166=Nq

2420=2^2×5×11^2
1166=2×11×53

Nは共通している部分なので、2×11=22
pは110,qは53