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

この記事の所要時間: 56

問題.

自作問題の17番です.

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

問題. 

整数定数 \(p, q, r, c\) が \(p = 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+ry\) と \(cx+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\)

(\(k\) は \(0, \pm 1\) でない整数, \(X, Y\) も整数)

と書けます.

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

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

\(k\) が \(0, \pm 1\) でない整数で, \(cX+Y\) も整数なので,

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

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

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

互いに素について

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

「\(x\) と \(y\) の両方を割り切る自然数が 1 のみ」

とか

「\(x\) と \(y\) の最大公約数が 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
  • このエントリーをはてなブックマークに追加