※整数の余りと数列の漸化式。
実質的には高校1年生レベルで東大京大数学に良く出るテーマ。
教科書をひと通りマスターしてから東大数学が始まります。
(1)(2)は確実に得点したい。
少し説明すると
「和の余りは、余りの和。積の余りは、余りの積」
なんか俳句みたいですね。(意外と知らない人が多い)
でもこれが「ユークリッドの互除法」の本質なんだ。*
桜で鍛えれば「偏差値50からの東大数学8割越え」も夢ではない。
東大数学の思考の流れを桜で体感しよう!
Do it now !
*ユークリッドの互除法(ユークリッドのごじょほう、英: Euclidean Algorithm)は、2 つの自然数の最大公約数を求める手法の一つである。
2 つの自然数 a, b (a ≧ b) について、a の b による剰余を r とすると、 a と b との最大公約数は b と r との最大公約数に等しいという性質が成り立つ。この性質を利用して、 b を r で割った剰余、 除数 r をその剰余で割った剰余、と剰余を求める計算を逐次繰り返すと、剰余が 0 になった時の除数が a と b との最大公約数となる。
明示的に記述された最古のアルゴリズムとしても知られ、紀元前300年頃に記されたユークリッドの『原論』第 7 巻、命題 1 から 3 がそれである。