見た質問
ログイン 新規登録

お使いのブラウザ(Internet Explorer)では閲覧、ログイン、質問の作成や回答などに不具合が生じることがございます。
誠に恐れ入りますが、下記の推奨ブラウザをご利用くださいませ。

推奨ブラウザ:Google Chrome(グーグル・クローム)

この場面でユークリッド互助法を使い、最大...

■どこまで理解しているか


この場面でユークリッド互助法を使い、最大公約数を表せることまでわかります

■どこが具体的にわからないか


2の100乗を2の78乗で割った商が最大公約数として出てきますが、そのあと2の56乗は余りなのに2の22乗で割れる理由がわからないです。

回答(1件)

ベストアンサーに選ばれました
オンライン家庭教師

こんばんは!


解説の1行目〜2行目では、27812^{78} -122212^{22} -1 の最大公約数が、22212^{22} -125612^{56} -1 の最大公約数と等しいということを述べています。

波線をつけている3行目でも、再び互除法を用いているだけですよ。

2561234(2221)=23412^{56} -1 - 2^{34} (2^{22} -1) = 2^{34} -1 という計算式は、解説1行目と同じ形をしていることに注意しましょう。

互除法は、その繰り返しの中で最大公約数が変化しないというのが強みでした。

それを利用して、最大公約数をキープしつつ数を小さくしています。

この回答をした先生に
オンラインでの個別指導を依頼できます

林 俊介
オンライン家庭教師

自己紹介

みなさん、こんにちは! 林 俊介 (はやし しゅんすけ)と申します。 ---------- 私の塾...

合格実績

合格実績のうち一部をお示しいたします! <中学受験> 女子学院中学校 豊島岡女子学園中学校 渋谷教...
あなたがベストアンサーに選んだ
林 俊介
さんはオンライン家庭教師をしています

他の質問・回答も見る

この質問に関連する文章

(2) 34-Bについて,(3gーb)d=14mだからdは14月の約数である。 (3)(1)(2)よりdは14mと14月の公約数であり、mとnは互いに素である から14mと14の最大公約数は14である。よってdは14の約数であり,d=14 となることがあればそれが最大である。 (1(2)でd=14とすると m-5b-a, n-3a-b ここでmとが互いに素となる やようにa=1, あ=2とした。 他の例としては, a-4, b-1, 第=1, #=11, A=56, B=14 答えは14. 第=9, #=1とするとA=14, B-28でd-14になる。 -013 演習題(解答は p.83) aとあの最大公約数を(a, b) で表すとき,以下の問いに答えよ。 (1)(2100-1, 278-1)-(278ー1, 22-1)であることを示せ。 (2)(28-1, 223-1)=(22-1, 212-1)であることを示せ。 (3)(2100-1, 278-1)の値を求めよ。 (1)は前文のkとして 商をとる。(2)もほは同 様。 72 ~2にすると数値が tr. るこ こについては,連続5整...

※質問に添付された画像から自動で抽出しているため、一部画像と異なるテキストが入っている場合があります