=== 読者が配色を変更したい場合 ===
◎外側の色を変えるには,次の色をクリック
◎内側の色を変えるには,次の色をクリック
標準文字色を変えるには,次の色をクリック

== 整数問題(入試問題) ==

[素数と因数分解]
【中学校数学の復習】
1よりも大きい整数のうちで,1とその数p自身の他に約数をもたない数p素数という.
1は素数に含めない.
• 例えば,2, 3, 5, 7, 11, 13, 17, 19, ・・・などが素数である.
• 偶数の素数は2だけである.それ以外の素数3, 5, 7, 11, 13, 17, 19, ・・・などはすべて奇数である.
• 多項式が次の形に因数分解できるとき
(式1)×(式2)=素数p
ただし,(式1)<(式2)
   ならば
(式1)=1,(式2)=p
と言える.これは,素数には1とその数p自身の他に約数がないからである.
【例題1】
(1) n3+1=pをみたす自然数nと素数pの組をすべて求めよ.
(2) n3+1=p2をみたす自然数nと素数pの組をすべて求めよ.
(3) n3+1=p3をみたす自然数nと素数pの組は存在しないことを証明せよ.
(2000年度千葉大)
(解答)
(1)
 (n+1)(n2−n+1)=p
と因数分解でき,nは自然数だからn+1≧2が成り立つ.したがって,
n2−n+1=1・・・@
n+1=p・・・A
@からn2−n=0
n(n−1)=0
nは自然数(≧1)だから
n=1
Aから
p=2
結局,(n, p)=(1, 2)・・・(答)

(2)
 (n+1)(n2−n+1)=p2
と因数分解でき,nは自然数だからn+1≧2が成り立つ.したがって,
ア)
n2−n+1=1 (n≧1)・・・@
n+1=p2・・・A
または
イ)
n2−n+1=p (n≧1)・・・B
n+1=p・・・C
ア)のとき,@からn=1
 これをAに代入するとp2=2
 このような素数はないから,ア)からは解は求まらない
イ)のとき,CをBに代入してpを消去すると
n2−n+1=n+1
n2−2n=0
n(n−2)=0
n≧1だから
n=2
Cに代入
p=3
結局,(n, p)=(2, 3)・・・(答)
(3)
 n3+1=p3 (n≧1)
を変形すると
 p3−n3=1
 (p−n)(p2+pn+n2)=1
ここでp2+pn+n2>0だから
p2+pn+n2=1・・・B
p−n=1・・・A
Aを@に代入してnを消去すると
 p2+p(p−1)+(p−1)2=1
 p2+p2−p+p2−2p+1=1
 3p2−3p=0
 3p(p−1)=0
 p=0, 1
しかしpは素数であるから,解なし
以上により,与えられた条件をみたす自然数nと素数pの組は存在しない ■証明終わり■
(別解)
(1)(2)の解と同様にn3+1を因数分解して示してもよいが,その方法の場合は,n+1≧2も考えると,次のように場合分けが多くなる
 ア)n2−n+1=1, n+1=p3
 イ)n2−n+1=p, n+1=p2
 ウ)n2−n+1=p2, n+1=p
いずれも解は求まらない

【問題1.1】
 次の問いに答えよ.
f(n)=n4−2n2−3
(1) f(n)nの2次式の積で表せ.
(2) nが自然数のとき,f(n)が素数となるnは1つだけ存在する.このときのnと素数f(n)を求めよ.
(2021年度北星学園大)
[解答を見る]
【問題1.2】
 x, yを自然数,p3以上の素数とするとき,次の各問に答えよ.ただし,(1),(3)は答のみ記せ.
(1) x2−y2=pが成り立つとき,x, ypで表せ.
(2) x3−y3=pが成り立つとき,p6で割った余りが1となることを証明せよ.
(3) x3−y3=pが自然数の解の組(x, y)をもつようなpを,小さい数から順にp1, p2, p3, ・・・とするとき,p5の値を求めよ.
(2014年度早稲田大学.政治経済学部)
[解答を見る]

【剰余類】
 例えば,すべての整数n
ア)「3で割ったとき割り切れる」
イ)「3で割ったとき1余る」
ウ)「3で割ったとき2余る」
のいずれかに分類される.アイウは,3をとする剰余類と呼ばれる.(剰余類の全体は剰余系と呼ばれる.)
 すべての整数nは,次のいずれかの形に書けると言ってもよい.kは整数とする.
ア) n=3k
イ) n=3k+1
ウ) n=3k+2n=3k−1でもよい)
 高校の教科書には「合同式」や「mod」の記号や用語は,登場しないが,大学入試問題の解説ではよく使われる.高校生が答案に書くのは構わない.
 すべての整数nは,次のいずれかの形に書けると言ってもよい.
ア) n≡0 (mod 3)
イ) n≡1 (mod 3)
ウ) n≡2 (mod 3)
【例題2】
(1) 正の整数a, b, cが,a2+b2=c2を満たすとき,a, b, cのうち少なくとも1つは3の倍数であることを証明せよ.
(2) 正の整数a, b, cが,a2+b2=c2を満たすとき,a, b, cのうち少なくとも1つは5の倍数であることを証明せよ.
(3) 正の整数a, b, cが,a2+b2=c2を満たすとき,a, b, cのうち少なくとも1つは4の倍数であることを証明せよ.
(解答)
(1)
 k, K, L, M, Nは整数とする.
 正の整数は,3k, 3k±1のいずれかの形に書けるから,その2乗は9k2=3K, (3k±1)2=9k2±6k+1=3K+1の形に書ける.
 もし,a, b, cがいずれも3の倍数でなければ,
a2+b2=(3K+1)+(3L+1)=3M+2
c2=3N+1
となって,a2+b2c2は,3で割ったときの余りが一致しないから,a2+b2=c2は成り立たない.
 背理法により,a2+b2=c2を満たすとき,a, b, cのうち少なくとも1つは3の倍数でなければならないことが示された.
(2)
 k, K, L, M, Nは整数とする.
 正の整数は,5k, 5k±1, 5k±2のいずれかの形に書けるから,その2乗は
25k2=5K
(5k±1)2=25k2±10k+1=5K+1
(5k±2)2=25k2+20k+4=5K+4

の形に書ける.
 もし,a, b, cがいずれも5の倍数でなければ,
a2+b2=(5K+1)+(5L+1)=5M+2
または
(5K+1)+(5L+4)=5M
または
(5K+4)+(5L+4)=5M+3
となって,5で割ったときの余りが,2,0,3のいずれかになる.
他方で,
c2=5N+1, 5N+4
となって,5で割ったときの余りが,1または4になる.
 このように,a2+b2c2は,5で割ったときの余りが一致しないから,a2+b2=c2は成り立たない.
 背理法により,a2+b2=c2を満たすとき,a, b, cのうち少なくとも1つは5の倍数でなければならないことが示された.

(3)
 k, K, L, M, Nは整数とする.
 正の整数は,4k, 4k+1, 4k+2, 4k+3のいずれかの形に書けるから,その2乗は
(4k)2=16k2=8K
(4k+1)2=16k2+8k+1=8K+1
(4k+2)2=16k2+16k+4=8K+4
(4k+3)2=16k2+24k+9=8K+1
の形に書ける.
 もし,a, b, cがいずれも4の倍数でなければ,
a2+b2=(8K+1)+(8L+1)=8M+2
または
(8K+1)+(8L+4)=8M+5
または
(8K+4)+(8L+4)=8M
となって,8で割ったときの余りが,0,2,5のいずれかになる.
他方で,
c2=8N+1, 8N+4
となって,8で割ったときの余りが,1または4になる.
 このように,a2+b2c2は,8で割ったときの余りが一致しないから,a2+b2=c2は成り立たない.
 背理法により,a2+b2=c2を満たすとき,a, b, cのうち少なくとも1つは4の倍数でなければならないことが示された.
(参考1)
 (3)の証明において,なぜ8の倍数の話が登場するのか?
 これは,初めから分かっていたのではなく,4の倍数で分類すると,4k+2の場合にうまく証明できないことから,4の剰余類で証明しようと考えていた方針を変更して「8の剰余類で分類することにした」ということです.
 一般に法を大きくすると剰余類も多くなるので,答案の場合分けが増える.だから,安易に法を大きくとるのは避けた方がよいが,やむを得ない場合もあるということは覚えておくとよい.
(参考2)
 上記の証明(1)(2)(3)によって,正の整数a, b, cが,a2+b2=c2を満たすのは
32+42=52
のように,1つずつ3,4,5の倍数に分かれてるということではない.
 少なくとも1つが3の倍数,4の倍数,5の倍数であるという条件を満たす組は
52+122=132
のように,1つの数12が3と4の倍数になっている場合や
112+602=612
のように,1つの数60が3,4,5の倍数になっていて,残り2つはどの倍数にもなっていないということもある.

【問題2.1】
 a, bを正の整数とする.aを6で割ると5余り,a2+bを6で割ると4余る.このとき,bを6で割ったときの余りは 7 であり,a2−b2を6で割ったときの余りは 8 である.
7 に関する選択肢]
(ア) 1  (イ) 2  (ウ) 3  (エ) 4  (オ) 5
8 に関する選択肢]
(ア) 1  (イ) 2  (ウ) 3  (エ) 4  (オ) 5
(2021年度獨協大)
[解答を見る]
【問題2.2】
 自然数aを3で割った余りをr=0, 1, 2とする.以下の問いに答えよ.
(1) 以下を求めよ.
(ア)r=0のとき,a3+4を3で割った余り.
(イ)r=1のとき,a3+4を3で割った余り.
(ウ)r=2のとき,a3+4を3で割った余り.
(2) 3つの自然数a, a3+4, a5+8のうちいずれか1つは3の倍数であることを示せ.
(3) 3つの自然数a, a3+4, a5+8が同時に素数となるaをすべて求めよ.
(2021年度中央大.理工学部)
[解答を見る]

【問題2.3】
 3333の1の位の数を求めよ.
(名古屋大)
[解答を見る]
【問題2.4】
 77777の1の位の数を求めよ.
(類題)
[解答を見る]
【問題2.5】
 自然数x, yに対して,それぞれを100で割った余りが等しいとき,x≡yと書くことにする.
(1) 自然数mに対して,76m≡76を証明せよ.
(2) 2n≡76を満たす最小の自然数nを求めよ.
(3) 21001を100で割った余りを求めよ.
(2000年度名古屋大)
[解答を見る]

【問題2.6】
 pが素数ならばp4+14は素数でないことを証明せよ.
(2021年度京都大.文系)
[解答を見る]
[解答を見る]

【対偶証明の復習】
 元の命題とその対偶とは真偽が一致すること(*)を利用して,対偶が真であることを示して,元の命題の証明とする方法
(*)の解説  (1は真, 0は偽を表すものとする)
p⇒qの真偽(定義)
pqp⇒q
111
100
011
001
• 仮定pが真(1)で結論qが偽(0)の場合だけ,p⇒qは偽(0)と決める.それ以外の場合,p⇒qは真(1)
の真偽
10101
10010
01101
01011
• 仮定が真(1)で結論が偽(0)の場合だけ,は偽(0)になる.それ以外の場合,は真(1)


• 上記の2つの表を見比べると,元の命題とその対偶とは真偽が一致することが分かる.
【対偶証明の例】
 x+y>0のとき,x, yの少なくとも1つは正の数であることを証明せよ.
 pが複合的な形をしていて,qが単純な形をしているとき,を証明するよりも,その対偶を証明する方が考えやすいことが多い.
(解答)
 x≦0かつy≦0のとき,x+y≦0となるから,対偶によって示される.
【背理法の復習】
 元の命題をそのまま証明するのが難しいとき,かつを仮定すると矛盾を生ずることを示して,の証明とする方法.
 対偶証明との相違点は,
も仮定する点」にある.
 証明の進め方によっては,という対偶を一部として使用することも多いが,その場合は対偶によって証明できたと考えているのではなく,が矛盾であることから,仮定が間違っていると述べるのが背理法.
 背理法の場合は,に行き着く場合だけでなく,一般の数学的常識に反することに行き着けば何でもよい.例えば,1=2が導かれたり,2が奇数になったり,1>2が導かれるような場合はすべて矛盾であるから,対偶証明よりも背理法の方ができることが多い.
(別の見方)
 という命題が成り立つ集合をで表し,という命題が成り立つ集合をで表すとき,命題には,集合の包含関係が対応する.
 であるとは,(図の印の部分)が空集合になること.
 したがって,を示すには,となるような要素が存在すると仮定すると矛盾になるということを示せばよい.
 これが「を背理法によって示す」ということを集合に対応させて考えたときの意味になる.
【背理法の例】
 自然数a, b, ca2+b2=c2をみたすとき,a, bのうち少なくとも1つは3の倍数であることを証明せよ.
(解答)
 a2+b2=c2・・・(1)
 abも3の倍数でない・・・(2)
と仮定する
(2)より,a=3k±1, b=3m±1k, mは整数)とおける
このとき,a2+b2=(3k±1)2+(3m±1)2
 =9k2±6k+1+9m2±6m+1
 =3N+2Nは整数)・・・(3)
ところが,どんな自然数c=3p, 3p+1, 3p+2pは整数)を持ってきても
 =c2=3N, 3N+1, 3N+1Nは整数)
となって,(3)は成り立たない.
 以上により,(1)のときabも3の倍数でないと仮定すると矛盾を生ずる.
 背理法により,a, b, ca2+b2=c2をみたすとき,a, bのうち少なくとも1つは3の倍数であることが証明された.

【例題3】
 a, b, ca2−3b2=c2を満たす整数とするとき,次のことを証明せよ.
(1) a, bの少なくとも一方は偶数である.
(2) a, bが共に偶数なら,少なくとも一方は4の倍数である.
(3) aが奇数ならbは4の倍数である.
(2000年度東北大)
(解答)
(1)
a, bとも奇数と仮定すると,
a=2k+1, b=2m+1k, mは整数)とおける.
このとき
a2−3b2=(2k+1)2−3(2m+1)2
=4k2+4k+1−3(4m2+4m+1)
=4k2+4k+1−12m2−12m−3
=4(k2+k−3m2−3m)−2
=4K−2・・・(*1)
この値とc2が等しいのだからcは偶数になる
そこで,c=2kkは整数)と仮定すると
c2=4k2=4L・・・(*2)(Lは整数)
(*1)は左辺が4の倍数でないことを示しており,(*2)は右辺が4の倍数であることを示しているから,矛盾.
 背理法により,a, bの少なくとも一方は偶数であることが示された.
(2)
a2−3b2=c2・・・(*3)
a, bが共に偶数・・・(*4)
 (*4)により,a=2k, b=2mk, mは整数)とおける.
 このとき,a2−3b2=4k2−12m2=4(k2−3m2)
 (*3)の右辺から,cは偶数でなければならない.
 そこで,c=2nnは整数)とおくと右辺は
4n2となるから
4(k2−3m2)=4n2
k2−3m2=n2・・・(*5)
 (*5)に(1)の結果を適用すると,k, mの少なくとも一方は偶数になるから,a, bの少なくとも一方は4の倍数である.
(3)
(1)の結果を使って,aは奇数,bは偶数とすると,a2−3b2=c2により,cは奇数になる.
a=2k+1, b=2m, c=2n+1k, m, nは整数)とおくと
(2k+1)2−3(2m)2=(2n+1)2
4k2+4k+1−3(4m2)=4n2+4n+1
4(k2+k−3m2)=4(n2+n)
k2+k−3m2=n2+n
k(k+1)−n(n+1)=3m2
ここで連続2整数の積は2の倍数だから,左辺のk(k+1), n(n+1)はいずれも2の倍数になり,その差も2の倍数
これが右辺の3m2に等しいのだから,mは偶数
よって,b=4ppは整数)となり,bは4の倍数である.

【問題3.1】
(1) 任意の自然数aに対し,a2を3で割った余りは0か1であることを証明せよ.
(2) 自然数a, b, ca2+b2=3c2を満たすと仮定すると,a, b, cはすべて3で割り切れなければならないことを証明せよ.
(3) a2+b2=3c2を満たす自然数a, b, cは存在しないことを証明せよ.
(2014年度九州大)
[解答を見る]
(参考)・・・無限降下法
例えば,が無理数であることの証明を,通常は次のように行う.(受験生には必須の内容)
が無理数であることを証明せよ.
(解答)
は正整数で互いに素)とおく.

両辺を2乗する
・・・(1)
左辺は2の倍数であるから,右辺のも2の倍数でなければならないが,そのためにはが2の倍数でなければならない.
は正整数)とおく・・・(2)
(1)に代入すると

両辺を2で割る
・・・(3)
(3)は,も2の倍数であることを示している.
 以上から,とも2の倍数であることになり「互いに素」という仮定に反する.
 は正整数で互いに素)という仮定から矛盾が導かれた.背理法により,が無理数である.
 以上のように,が無理数であることを示す背理法による標準的な証明は,初めの段階で「互いに素」という仮定を置くことにより,共通因数が1回登場した段階で証明を終ることができる.
 これに対して,「互いに素」という仮定を置かなければ,次のような記述になる.この論法は「無限降下法」と呼ばれ,フェルマーが大定理を証明するために用いた方法だと言われている(ただし,当時のフェルマーが実際に証明に成功していたかどうかは疑問とされている)
は正整数)とおく.

・・・(1)
(は正整数,)とおく・・・(1’)
(1)に代入すると

両辺を2で割る
・・・(2)
(は正整数,)とおく・・・(2’)
(2)に代入すると

両辺を2で割る
・・・(3)
(は正整数,)とおく・・・(3’)
以上のように,(1)(1'),(2)(2'),(3)(3'),・・・のように変形していく作業は,限りなく繰り返すことができて,有限確定の正整数について次の不等式が成り立つことになる.


 これらは,有限確定の正整数と1の間に無限個の整数が存在するという矛盾になっている.
 が有理数という仮定は間違っていることになり,背理法により,は無理数であることが証明された.
 2014年度九州大の問題(3)において,「は正整数で互いに素」と仮定することができれば,上記のような無限降下法によらず,共通因数が1回登場すれば矛盾とすることができるはずであるが,(2)(3)の問題の組み立ての都合上,とも3の倍数であるから「互いに素」と仮定することはできない.

【問題3.2】
(1) x2+4y2=9z2をみたす自然数x, y, zがあれば,xyはいずれも3の倍数であることを示し,x2+4y2=9z2をみたす自然数x, y, zの例を挙げよ.
(2) x3+4y3=9z3をみたす自然数x, y, zは存在しないことを示せ.
(2014年度東京海洋大)
[解答を見る]
[解答を見る]
[解答を見る]

【問題3.3】
 a−b−8b−c−8が素数となるような素数の組
(a, b, c)をすべて求めよ.
(2014年度一橋大)
[解答を見る]
[解答を見る]

【定着度チェック問題】・・・このページの振り返りです
【問題4.1】・・・受験では基礎のレベル
 整数a, bについて,aは13で割ると2余り,bは13で割ると7余る.このとき,4a+3bは13で割ると余り,abは13で割ると余る.
(2021年度金沢工大)
[解答を見る]
【問題4.2】・・・ちょうど良いレベルの良問
(1) k2+2が素数となるような素数kをすべてみつけよ.また,それ以外にないことを示せ.
(2) 整数lが5で割り切れないとき,l4−1が5で割り切れることを示せ.
(3) m4+4が素数となるような素数mは存在しないことを示せ.
(2021年度お茶の水女子大)
[解答を見る]

[解答を見る]
[解答を見る]

【問題4.3】・・・チャレンジしてみよう
 素数p, qを用いて pq+qp と表される素数をすべて求めよ.
(2016年度京都大)
[解答を見る]
【問題4.4】
 nを2以上の整数とする.3n−2nが素数ならばnも素数であることを示せ.
(2021年度京都大)
[解答を見る]
...(PC版)メニューに戻る