クサキョウチクトウ (オイランソウ)。まだ咲き始めだなあ。
【問】
は正の整数とする。
を
で割った余りを
とおく。
数列 は
を満たすことを示せ。
に対して、
は ともに正の整数で、互いに素であることを証明せよ。
【解】
とおくと、
したがって、
である。
がともに正の整数であること:
から、
は正の整数である。 の正の整数について、帰納法の仮定を使って
を正の整数だとすると、
の
から、 も正の整数である。
が互いに素であること:
の最大公約数は
だから
は互いに素である。
の正の整数について、帰納法の仮定を使って
は互いに素だとする。
まず、 の最大公約数は、
の最大公約数に等しい 。このことを以下に証明する。
(以下、証明)
から、
であるが、任意の の公約数は
も割り切るので
と
の公約数である。逆に任意の
の公約数は
も割り切るので、
と
の公約数である。したがって
の公約数全体の集合は、
の公約数全体の集合と等しく、したがって最大公約数も等しい。
(以上証明終わり)
ところが、 の最大公約数は
である。このことを以下に証明する。
(以下証明)
から、
なので、 の任意の公約数
は、
を割り切る。
は
で割り切れるので、
も
で割り切れる。いま、
と仮定すると、
の最大公約数が
であることに矛盾する。したがって、
の最大公約数は
である。
(以上証明終わり)
の最大公約数は、
の最大公約数に等しく、
である。//