自作問題17 (条件を満たす整数の存在, 互いに素の証明)

この記事の所要時間: 52

問題.

自作問題の17番です.

この問題は比較的簡単です.

問題. 

整数定数 p, q, r, cp = rc^2+c, q = 2rc+1 を満たす. このとき, 任意の整数 n に対して

\begin{align*} px^2+qxy+ry^2 = n \end{align*}

を満たす, 互いに素な整数 (x, y) の組が存在することを示せ.

x, y が互いに素とは, x, y の両方を割り切る自然数が 1 だけであるという意味です.

実際に px^2+qxy+ry^2=n となる (x, y) をつくることができれば OK です.

解答例.

まず, 与えられた関係式

\begin{align*} p &= rc^2+c\\ q &= 2rc + 1 \end{align*}

を, px^2+qxy+ry^2=n の右辺に代入してみましょう.

\begin{align*} px^2+qxy+ry^2 &= (rc^2+c)x^2+(2rc+1)xy+ry^2\\ &= (rc+1)cx^2+(2rc+1)xy+ry^2\\ &= \{(rc+1)x+ry\}(cx+y) \end{align*}

代入してみると, 上のように因数分解ができました. よって, 次のような問題を考えればよいことになります.

問題(改). 

r, c が整数の定数のとき

任意の整数 n に対して,

\begin{align*} \{(rc+1)x+ry\}(cx+y)=n \end{align*}

を満たす互いに素な整数 (x, y) の組が存在することを示せ.

さて, (rc+1)x+rycx+y を掛けて n になればよいのですが, n は任意の整数なので, 試しに

\begin{align*} (rc+1)x+ry &= n\\ cx+y &= 1 \end{align*}

としてみます.

これを x, y についての連立 1 次方程式とみなして解くと,

\begin{align*} (x, y) = (n-r, 1-c(n-r)) \end{align*}

後は, これらが互いに素であることを示せば OK です.

背理法を使っていきます.

x=n-r, y=1-c(n-r) が互いに素でないと仮定すると,

x = kX, y = kY

(k0, \pm 1 でない整数, X, Y も整数)

と書けます.

cx+y=1 に代入すると,

\begin{align*} ckX+kY&=1\\ k(cX+Y) &= 1 \end{align*}

k0, \pm 1 でない整数で, cX+Y も整数なので,

k(cX+Y) =1 を満たすことはなく, 矛盾が生じます.

したがって, x=n-r, y=1-c(n-r) は互いに素となります.

これで, 条件を満たす (x, y) の例を 1 つ挙げられたので, 証明終了です.

互いに素について

2 つの自然数 x, y が互いに素, というと,

xy の両方を割り切る自然数が 1 のみ」

とか

xy の最大公約数が 1」

などを思い浮かべると思います.

3 と 10 が互いに素, 14 と45 は互いに素, なら問題はないのですが, では, 次のような場合は互いに素かそうでないか, どちらだと思いますか?

(1) 1 と 6

(2) 0 と 12

(3) 0 と 1

正解は, (1) と (3) は互いに素, (2) は互いに素ではない, となります.

(1) は上に書いた 「最大公約数が 1 」 で判断できますが

(2), (3) のように 0 があるとそもそも最大公約数を考えることができません.

そこで, 「x, y が互いに素」を

「分数 \dfrac{x}{y} が約分できない(既約分数), (y\neq0)

と考えてみましょう.

(1) は \dfrac{1}{6} は既約分数なので 1 と 6 は互いに素です.

(2) では \dfrac{0}{12}\dfrac{0}{1} と約分ができるので, 0 と 12 は互いに素ではありません.

(3) では \dfrac{0}{1} は既約分数なので 0 と 1 は互いに素です.

この考え方をすると,

(i) 1 はどんな整数とも互いに素

(ii) 0 は 1 とだけ互いに素

であることが分かります.

個人的には分数にして考える方法が分かりやすいと感じています.

スポンサーリンク
sub2
sub2
  • このエントリーをはてなブックマークに追加