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

問題.

自作問題の17番です.

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

問題. 

整数定数 が を満たす．このとき，任意の整数 に対して

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

を満たす，互いに素な整数 の組が存在することを示せ．

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

実際に となる をつくることができれば OK です．

解答例.

まず，与えられた関係式

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

を の右辺に代入してみましょう．

\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*}

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

問題(改). 

が整数の定数のとき

任意の整数 に対して，

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

を満たす互いに素な整数 の組が存在することを示せ．

さて, と を掛けて になればよいのですが, は任意の整数なので，試しに

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

としてみます．

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

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

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

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

が互いに素でないと仮定すると，

( は でない整数， も整数)と書けます.

に代入すると，

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

が でない整数で， も整数なので，

を満たすことはなく，矛盾が生じます．

したがって, は互いに素となります．

これで，条件を満たす の例を 1 つ挙げられたので，証明終了となります．

互いに素について

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

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

とか

「 と の最大公約数が 1」

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

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

(1) 1 と 6

(2) 0 と 12

(3) 0 と 1

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

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

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

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

「分数 が約分できない(既約分数), (」

と考えてみましょう.

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

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

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

この考え方をすると,

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

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

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

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