質問: この場面でユークリッド互助法を使い、最大... ■どこまで理解しているか この場面でユークリッド互助法を使い、最大公約数を表せることまでわかります ■どこが具体的にわからないか 2の100乗を2の78乗で割った商が最大公約数として出てきますが、そのあと2の56乗は余りなのに2の22乗で割れる理由がわからないです。
回答: こんばんは! 解説の1行目〜2行目では、278−1 と 222−1 の最大公約数が、222−1 と 256−1 の最大公約数と等しいということを述べています。波線をつけている3行目でも、再び互除法を用いているだけですよ。256−1−234(222−1)=234−1 という計算式は、解説1行目と同じ形をしていることに注意しましょう。互除法は、その繰り返しの中で最大公約数が変化しないというのが強みでした。それを利用して、最大公約数をキープしつつ数を小さくしています。