2元1次2

2018年3月16日

2元1次不定方程式の整数解の理論の問題です。一般的な解の求め方、解の存在条件の問題です。まずはユークリッドの互除法を用いて解く理論から。ややこしく見えますが、前問でやったことを文字に置き換えてやっているだけに過ぎません。

1.C (静岡大)
自然数a_0,~a_1が与えられたとき,数列\{a_n\},~\{q_n\}
(ⅰ) q_na_{n-1}a_nで割った商
(ⅱ) a_{n+1}=a_{n-1}-q_na_n~(n=1,~2,~3,~\cdots)
を満たすものとする.ただし,a_{N+1}=0となる自然数Nが存在すればn>Nに対してq_nおよびa_{n+1}は定義しない.
(1) a_{N+1}=0となる自然数Nが存在することを証明せよ.
(2) a_N=aa_0+ba_1を満たす整数a,~bが存在することを証明せよ.
(3) a_Na_0a_1の最大公約数であることを証明せよ.

解答

次は連分数を用いてやっていますが、やっていることはユークリッドの互除法です。

2.C (早稲田大)
(1) \alpha,~\betaを互いに素な正の整数とする.
[1] \alpha x-\beta y=0の整数解をすべて求めよ.
[2] \dfrac{\alpha}{\beta}=a_1+\dfrac{1}{a_2+\dfrac{1}{a_3+\dfrac{1}{a_4}}} (a_1,~a_2,~a_3,~a_4は正の整数)とかけるとする.a_1+\dfrac{1}{a_2+\dfrac{1}{a_3}}を通分して得られる分子a_1a_2a_3+a_1+a_3p,分母a_2a_3+1qとするとき,\alpha q-\beta pの値を求めよ.
(2) 157x-68y=3の整数解を求めよ.

解答

次は誘導なしでシンプルに出題された時にどうすればよいかという問題です。当然上の方法を再現してもよいですが少し別の方法でやってみます。

3.C (明治大等)
自然数a,~bについて方程式ax+by=1を満たす整数x,~yが存在するための必要十分条件は,abが互いに素であることを証明せよ.

解答

次は完全剰余系の性質を利用し、鳩ノ巣原理を利用して追い込んでいく方法です。

4.C (大阪女子大)
(1) 4m+6n=7を満たす整数m,~nは存在しないことを示せ.
(2) 3m+5n=2を満たすすべての整数の組(m,n)を求めよ.
以下a,~bは互いに素な正の整数とする.
(3) kを整数とするとき,akbで割った余りをr(k)で表す.k,~lb-1以下の正の整数とするとき,k \ne lならばr(k) \ne r(l)であることを示せ.
(4) am+bn=1を満たす整数m,~nが存在することを示せ.

解答

最後に完全剰余系を利用した問題をもう1題。

5.C (京都大)
0以上の整数xに対して,C(x)xの下2桁を表すことにする.たとえば,C(12578)=78,~C(6)=6である.nを2でも5でも割り切れない正の整数とする.
(1) x,~yが0以上の整数のとき,C(nx)=C(ny)ならば,C(x)=C(y)であることを示せ.
(2) C(nx)=1となる0以上の整数xが存在することを示せ.

解答

関連ブログはこちら
にほんブログ村 教育ブログへ にほんブログ村 受験ブログへ