【入試過去問】整数問題 問題集【合同式、mod、因数分解、素数】

数学

整数問題はとっつきにくくないですか?

解法に慣れて落ち着て解くには、
問題のパターンをあらかじめ経験しておくことが大事です。

この記事では整数問題を集めてみました。

スポンサーリンク

合同式modを使って解く

整数問題

平方数の余りが等しくなることから、
数を絞っていって、因数分解。
整数の掛け算(因数)の組み合わせが
数が限られるので、そこに持っていく。

素数の性質を使った有名な問題

問題
$$p^q+q^pが素数となる素数p,qを全て求めよ$$

別のページで書いています。
こちらにリンクを貼っております。

平方数の余りの性質から

九州大学 整数問題 高校数学 Japanese university entrance exam questions

平方数はmod 3では余りは0 or 1に限られる。
右辺は3の倍数となっている。つまりmod 3で余りは0。

以上から左辺がmod 3 では
$$a^2 \equiv 0 or b^2 \equiv 0(mod 3)$$
の時しか成立しない。

つまりa,bは3の倍数であることがわかります。あとは

$$a=3m,b=3n$$とおいて計算すれば、cも3の倍数となります。

存在しないことを証明するのによく使われる背理法から
実際に等式に代入して矛盾を導いて証明しています。

平方数の余りの性質をそのまま使っています。

式変形が大変な骨の折れる問題

問題
$$a^2+b^2+c^2+d^2=n^2-6$$
$$a+b+c+d\le n$$
$$a\ge b\ge c\ge d$$
を満たす非負整数(a,b,c,d,n)をすべて求めよ。

解答

二乗の項を消したいので、
$$a+b+c+d\le n$$
の両辺を二乗してしましょう。
両辺は正の値なので不等号の向きは変わりません。

$$a^2 + b^2 + c^2 +d^2 +2(ab + ac +ad +bc +bd +cd) \le n^2$$

この式に

$$a^2 + b^2 +c^2 +d^2=n^2 -6$$を代入します。

$$n^2 -6 + 2(ab + ac +ad +bc +bd +cd) \le n^2$$
$$ab + ac +ad +bc +bd +cd \le 3$$
このような不等式になります。

ここから

$$a\ge b\ge c\ge d \ge 0(式⓪)$$

なので、まずはdから適当な値を代入していきましょう。
ためしにd=1を代入します。

$$ab + ac +a +bc +b +c \le 3 (式①)$$

となります。

d=1なのでa,b,cは1以上の整数になります。
ということは、

$$ab + ac +a +bc +b +c \ge 6$$
となり、式①を満たせないので、d=1では満たせない。
よって1より小さいd=0が確定。

式を書き直します。

$$ab + bc + ca \le 3(式②)$$
$$a+ b+c \le n(式③)$$

今度はc=2を代入してみます。

式②はこのようになります。
$$ab + 2b +2a \le 3(式④)$$

式⓪よりa,bは2以上なので

$$ab +2b +2a \ge 12$$
となり式④と矛盾するので、c=2は成り立たない。
ということでcは0または1となります。
ここからはc=0とc=1で場合分けをします。

c=0のとき

式②,③に代入します。
$$ab \le 3(式⑤)$$
$$a+b \le n(式⑥)$$

式⑤と式⓪より、
bが2以上のとき式⑤を満たせないので矛盾。
よって
$$b = 0,1$$
となります。
さらにbについて場合分けしていきます。

b=0の時は
$$a^2=n^2-6$$
$$(n+a)(n-a)=6$$

n,aは非負整数なので
n+a,n-aの組み合わせは(3,2)(6,1)のみ。
しかし、どちらもn,aが整数にならないので、
成立するn,aは存在しない

b=1のとき式⑤と式⓪を満たすa,bの組み合わせは
$$(a,b) = (1,1),(2,1),(3,1)$$
$$(c=d=0)$$

(a,b) = (1,1)のとき
$$1+1+6=n^2$$となり整数解が存在しない

(a,b) = (2,1)のとき
$$4+1+6=n^2$$となり整数解が存在しない

(a,b) = (3,1)のとき
$$9+1+6=n^2$$となりn=4となる。

よって、$$(a,b,c,d,n)=(3,1,0,0,4)$$

今度はc=1の時を調べます。

式①は

$$ab + a+b^\le 3$$
$$(a+1)(b+1)\le 4$$

$$a\ge b \ge c =1$$より
$$b+1 \ge 2$$
つまり(a+1,b+1)の組み合わせは(2,2)のみ
よって(a,b) = (1,1)

$$1+1+1+6 = n^2$$
$$n=3$$

よって

$$(a,b,c,d,n)=(1,1,1,0,3)$$

よって(a,b,c,d,n)の組み合わせは

$$(a,b,c,d,n)=(1,1,1,0,3),(3,1,0,0,4)$$

(終)

自力で解いてみたけれど…

この問題を自分で解いてみましたが、
自力では解けませんでした。

東大 不定方程式不等式

こちらの動画を途中まで見て、不等式の二乗することを拝借いたしました。

この問題のポイントは下記のとおりです。

不等式を二乗することを選択肢に入れているか
小さな値を入れてみて可能性をしぼれるか
因数分解して整数の組を見つけられるか

「不等式を二乗すること」が思いつかず詰まったのですが、
二乗してnを消去したら、そこからは、場合分けが大変でしたが、
自力で解にたどり着けました。

相加平均・相乗平均の関係を使った問題

東大 整数問題 Mathematics Japanese university entrance exam Tokyo University

(1)は$$xyz \le 3z$$に気づけれるかがポイント。
そこからx,yの組み合わせがかぎられるのでそこから解くことができます。

(2)はかなり難しい。
相加平均相乗平均の関係から

$$x^3+y^3+z^3 – 3xyz \ge 0$$

を導き、そこから
$$x^3+y^3+z^3 – xyz \gt 0$$
を証明して存在しないことが示せます。

これは本番の試験でいきなり解くには、
普段からかなりのパターンの問題を解いていないと
着想するのが難しいと思われます。

コメント

  1. […] 【入試過去問】整数問題 問題集整数問題はとっつきにくくないですか?解… […]

  2. […] Twitter Facebook はてブ Pocket LINE コピー […]

タイトルとURLをコピーしました