2017年度「プログラミング言語1」「プログラミング言語演習」のページ

練習問題

2017年5月18日出題
  1. \(a+bi\) (ただし、\(a\) と \(b\) は整数、\(i\) は虚数単位)の形で表せる複素数をガウス整数と呼ぶ。ガウス整数とガウス整数の積はガウス整数となる。ガウス整数 \(a+bi\) でガウス整数 \(m+ni\) が割り切れるとは、あるガウス整数 \(x+yi\) が存在して、\((a+bi)(x+yi)=m+ni\) が成り立つことと定義する。

    1. (おまけ)ガウス整数とガウス整数の積はガウス整数となることを証明せよ。

    2. ガウス整数の積を計算するプログラムを書け。整数 \(a\), \(b\), \(m\), \(n\) を入力し、\((a+bi)(m+ni)=p+qi\) となる整数 \(p\), \(q\) を求めて出力せよ。

    3. ガウス整数でガウス整数が割り切れるかを判定するプログラムを書け。整数 \(a\), \(b\), \(m\), \(n\) を入力し、\(a+bi\) で \(m+ni\) が割り切れるときは Oui と、そうでないときは Non と出力せよ。

    ヒント1

    \(i^2=-1\)

    ヒント2

    \(\left(a+bi\right)\left(a-bi\right) = a^2+b^2\)

    ヒント3

    ガウス整数のことをいったん忘れて複素数の範囲で計算すると、 \[ \begin{aligned} \frac{m+ni}{a+bi} &= \frac{(a-bi)(m+ni)}{(a-bi)(a+bi)} \\ &= \frac{am+bn}{a^2+b^2}+\frac{an-bm}{a^2+b^2}i \end{aligned} \] となる。 ここでガウス整数のことを思い出すと、\(\dfrac{m+ni}{a+bi}\) がガウス整数である必要十分条件は、\(\dfrac{am+bn}{a^2+b^2}\) も \(\dfrac{an-bm}{a^2+b^2}\) も普通の意味の整数であることである。 したがって、\(a+bi\) で \(m+ni\) が割り切れる必要十分条件は、 \(am+bn\) も \(an-bm\) も \(a^2+b^2\) で割り切れることである。

  2. \(a+b\omega\) (ただし、\(a\) と \(b\) は整数、\(\omega=(-1+\sqrt{3}i)/2\))の形で表せる複素数をアイゼンシュタイン整数と呼ぶ。アイゼンシュタイン整数とアイゼンシュタイン整数の積はアイゼンシュタイン整数となる。アイゼンシュタイン整数 \(a+b\omega\) でアイゼンシュタイン整数 \(m+n\omega\) が割り切れるとは、あるアイゼンシュタイン整数 \(x+y\omega\) が存在して、\((a+b\omega)(x+y\omega)=m+n\omega\) が成り立つことと定義する。

    1. (おまけ)アイゼンシュタイン整数とアイゼンシュタイン整数の積はアイゼンシュタイン整数となることを証明せよ。

    2. アイゼンシュタイン整数の積を計算するプログラムを書け。整数 \(a\), \(b\), \(m\), \(n\) を入力し、\((a+b\omega)(m+n\omega)=p+q\omega\) となる整数 \(p\), \(q\) を求めて出力せよ。

    3. アイゼンシュタイン整数でアイゼンシュタイン整数が割り切れるかを判定するプログラムを書け。整数 \(a\), \(b\), \(m\), \(n\) を入力し、\(a+b\omega\) で \(m+n\omega\) が割り切れるときは Ja と、そうでないときは Nein と出力せよ。

    ヒント1
    \(\omega^2=-1-\omega\)
    ヒント2
    \(\left(a+b\omega\right)\left(a-b-b\omega\right) = a^2-ab+b^2\)
    ヒント3

    アイゼンシュタイン整数のことをいったん忘れて複素数の範囲で計算すると、 \[ \begin{aligned} \frac{m+n\omega}{a+b\omega} &= \frac{(a-b-b\omega)(m+n\omega)}{(a-b-b\omega)(a+b\omega)} \\ &= \frac{am-bm+bn}{a^2-ab+b^2}+\frac{an-bm}{a^2-ab+b^2}\omega \end{aligned} \] となる。 ここでアイゼンシュタイン整数のことを思い出すと、\(\dfrac{m+n\omega}{a+b\omega}\) がアイゼンシュタイン整数である必要十分条件は、\(\dfrac{am-bm+bn}{a^2-ab+b^2}\) も \(\dfrac{an-bm}{a^2-ab+b^2}\) も普通の意味の整数であることである。 したがって、\(a+b\omega\) で \(m+n\omega\) が割り切れる必要十分条件は、 \(am-bm+bn\) も \(an-bm\) も \(a^2-ab+b^2\) で割り切れることである。


戻る
奈良女子大学生活環境学部情報衣環境学科生活情報通信科学コース