次: 剰余類 上: 数論の基礎 前: 素因数分解

演習問題

練習問題 1 (解答1)       

$n$ を整数とするとき，次のことを示せ．

(1)

$n(n+1)(n+2)(n+3)$ は24の倍数である．

(2)

$n$ が奇数ならば， $n^3-n$ は24の倍数である．

(3)

$n$ が2でも3でも割り切れないならば， $n^2-1$ は24の倍数である．

(4)

$n(n+1)(2n+1)$ は6の倍数である．

(5)

$n^3-3n^2+8n$ は6の倍数である．

練習問題 2 (解答2)       

$a,\ b$ は互いに素な正の整数とするとき，次の問に答えよ．

(1)

分数 $\dfrac{7a+2b}{3a+b}$ は既約分数である．

(2)

$ps-qr=1$ なる正の整数 $p,q,r,s$ に対して， 分数 $\dfrac{pa+qb}{ra+sb}$ は既約分数である．

(3)

$\dfrac{11n-42}{3n-13}$が既約分数にならないような 自然数 $n$ を，小さい方から順に三つ求めよ．

練習問題 3 (解答3)        次の不定方程式の一般解を求めよ．

(1)

$25x+13y+15z=1$

(2)

$2x+6y+5z+7w=1$

練習問題 4 (解答4)  

$a=p^{\alpha}q^{\beta}r^{\gamma}\cdots$ を $a$ の素因数べきへの分解とする． 以下の命題を示せ．

(1)

$a$ のすべての約数は

$$p^xq^yr^z\cdots$$

において $0\le x \le\alpha$ , $0\le y \le\beta$ , $0\le z \le\gamma,\ \cdots$ を動くことで漏れなくまた重複なく得られる．

(2)

$a$ の約数の個数 $T(a)$ は

$$T(a)=(1+\alpha)(1+\beta)(1+\gamma)\cdots$$

で与えられる．

(3)

$a$ のすべての約数の和$S(a)$は

$$S(a)=\dfrac{p^{\alpha+1}-1}{p-1}\cdot \dfrac{q^{\beta+1}-1}{q-1} \cdot \dfrac{r^{\gamma+1}-1}{r-1}\cdot \cdots$$

で与えられる．

(4)

$a,\ b，c$ ，が互いに素なとき，

$$T(abc)=T(a)T(b)T(c)$$

また

$$S(abc)=S(a)S(b)S(c)$$

(5)

$a$ のすべての約数の積は

$$a^{\frac{T(a)}{2}}$$

に等しい．

練習問題 5 (解答5)  

古代ギリシアの数学では整数 $a$ の約数(1を入れて$a$自身を入れない)の和が $a$ に等しいとき $a$ を 完全数 と称していた．すなわち練習問題4 の記号では

$$S(a)=2a$$

のとき $a$ を完全数という．

(1)

$n>1$ に対して $a=2^{n-1}(2^n-1)$とおく．$2^n-1$ が素数になるとき，$a$ は完全数であることを示せ．

(2)

逆に偶数の完全数はこのような形の数しかないことを示せ．

練習問題 6 (解答6)  

次のことを示せ．

(1)

$a,\ a',\ a'',\ \cdots$ がおのおの $b,\ b',\ b'',\ \cdots$ と互いに素なら $aa'a''\cdots$ と $bb'b''\cdots$ も互いに素である． とくに $(a,\ b)=1$ なら $(a^n,\ b^n)=1$

(2)

$$(a_1,\ a_2,\ \cdots,\ a_m)(b_1,\ b_2,\ \cdots,\ b_n) =(a_1b_1,\ a_1b_2,\ \cdots,\ a_2b_1,\ \cdots,\ a_mb_n\ )$$

(3)

$a_1,\ a_2,\ \cdots ,\ a_n$ のなかの少なくとも一つの素因数分解に 現れる素数を $p,\ q,\ \cdots$とし， 現れたすべての素数に関する積を

$$a_k=\prod_pp^{\alpha_k(p)} \ (\alpha_k(p) \ge 0)$$

とおく． $a_1,\ a_2,\ \cdots ,\ a_n$ の最大公約数を $m$ ， 最小公倍数を $l$ とするとき，

$$\begin{array}{l} \displaystyle m =\prod_pp^{\mathrm{M... ...1(p),\ \alpha_2(p),\ \cdots,\ \alpha_n(p))}\\ \end{array}$$

ただし Min はいずれより大きくない数，Max はいずれより小さくない数，を表す．

(4)

$a_1,\ a_2,\ \cdots ,\ a_n$ の最大公約数を$d_1$， これら$n$個の数から2数を選ぶと ${}_n \mathrm{C}_2$組みできるが， 各組の数の積 $a_1a_2,\ a_1a_3,\ \cdots,\ a_{n-1}a_n$ の最大公約数を $d_2$とする． 一般に $a_1,\ a_2,\ \cdots ,\ a_n$ のなかから$k$数選ぶと ${}_n \mathrm{C}_k$組できるが， 各組の数の積をとりそれらの数の最大公約数を $d_k$とする． 特に $a_1a_2\cdots a_n=d_n$である．

(i)

$k=2,\ \cdots n$ に対して$d_k$ は $d_{k-1}$ で割りきれる．

(ii)

$\dfrac{d_k}{d_{k-1}}=e_k$ (ただし $e_1=d_1$）とおくと$e_k$ は $e_{k-1}$ で割りきれる．

(iii)

また

$$e_1 e_2\cdots e_n=a_1 a_2 \cdots a_n$$

(iv)

$e_n$ は $a_1,\ a_2,\ \cdots ,\ a_n$ の最小公倍数に等しい．

(5)

仮に $a,\ b,\ c,\ \cdots$ の最小公倍数を $\{a,\ b,\ c,\ \cdots\}$ で表すことにする．

$$\{(a_1,\ m),\ (a_2,\ m),\ \cdots,\ (a_n,\ m)\} =(\{a_1,\ a_2,\ \cdots,\ a_n\},\ m)$$

(6)

$l$を $a,\ b,\ c,\ \cdots$の最小公倍数とする． $a,\ b,\ c,\ \cdots$ の約数で二つずつ互いに素であるような $a_0,\ b_0,\ c_0,\ \cdots$で

$$l=a_0b_0c_0\cdots$$

となるものが存在する．

練習問題 7 (解答7)  

(1)

$p$ が素数ならば 二項係数 ${}_p \mathrm{C}_k\ (p>k>0)$ は $p$ で割り切れることを示せ．

(2)

$k$ がちょうど $p$ の $l$ 乗で割りきれる ならば, ${}_{p^n} \mathrm{C}_k\ (p^n>k>0)$ は$p^{n-l}$ で割り切れることを示せ．

練習問題 8       解答8     $n!$ の因数分解に含まれる素因数 $p$ の最高べきの指数は，

$$\left[\dfrac{n}{p}\right]+\left[\dfrac{n}{p^2}\right]+\cdots =\sum_{k=1}^{\infty}\left[\dfrac{n}{p^k}\right]$$

であることを示せ．ただし $\left[x \right]$ は実数 $x$ を超えない最大の整数を表す．

練習問題 9 (解答9)  

$\dfrac{m}{n}\ (m>0,\ n>1)$ を既約分数とする． 分母$n$ の素因数分解を $n=p^{\alpha}q^{\beta}\cdots$とすれば， 分数 $\dfrac{m}{n}$は， $0<x<p^{\alpha},\ 0<y<q^{\beta},\ \cdots,\ s\ge 0$ である整数 $x,\ y,\ \cdots,\ s$を用いて

$$\dfrac{m}{n}=\dfrac{x}{p^{\alpha}}+\dfrac{y}{q^{\beta}}+\cdots \pm s$$

と一通りに部分分数に分解されることを示せ．

関連入試問題

入試問題 1 (解答1)   ［98お茶の水女子大］

正の数 $k,\ l\ (k \ge l)$ に対して 数列 $\{ a_n \},\ \{b_n\}$ を次のように定義する．
$a_1=k,\ b_1=l$
$n \ge 1$ について

$$a_{n+1}=\left\{ \begin{array}{ll} b_n&(b_n\ne0のと... ...とき)\\ b_n&(b_n=0のとき) \end{array} \right.$$

(1)

$k=1998,\ l=185$ について， $\{ a_n \},\ \{b_n\}$ を それぞれ第5項まで計算せよ．

(2)

任意の $k,\ l,\ n$ について $b_n\ge b_{n+1}$ (等号は $b_n=0$ のときに限る) を示せ．

(3)

任意の $k,\ l$ について $b_n=0$ となる $n$ が存在することを示せ．

(4)

$b_n=0$ となる $n$ について $a_n$ が $k$ と $l$ の最大公約数になっていることを示せ．

入試問題 2 (解答2)   ［91阪大理系後期］

条件 $a \ge b$ を満たす正の整数 $a,\,b$ から数列 $\{ r_n \}$ を $r_1=a,\,r_2=b,$

$$n \ge 3 に対して， r_n = \cases{ r_{n-2} を r_{n... ...>0$\ のとき) \cr 0 & ( $r_{n-1} =0$\ のとき) \cr }$$

によって定める．

また，数列 $\{ f_n \}$ を $f_1=0,\,f_2=1,\,f_n=f_{n-1}+f_{n-2} (n \ge 3 のとき)$ に よって定める．このとき，以下のことがらを示せ．

(1)

$r_N>0, \, r_{N+1}=0$ となる整数 $N$ が存在する．以下， $N$ はこの整数を表す．

(2)

$r_{N+2-k} \ge f_k \,\,(k=1,2, \cdots , N+1)$

(3)

$f_{n+1} \ge \left( \dfrac{3}{2} \right) ^{n-2} \,\,\,(n=1,2,\cdots )$

(4)

$N \le 2+ \log _{\frac{3}{2}} a$

入試問題 3   解答3     ［80京大文系］

互いに異なる $n$ 個（$n\ge 3$）の正の数の集合 $S=\{a_1,\ a_2,\ \cdots,\ a_n\}$ が次の性質をもつという．

「$S$ から相異なる要素 $a_i,\ a_j$ をとれば $a_i-a_j,\ a_j-a_i$ の少な くとも一方は必ず $S$ に属する」

このとき， $a_1,\ a_2,\ \cdots ,\ a_n$ の順序を適当に変えれば等差数列 になることを示せ．

入試問題 4   解答4     ［80京大理系］

互いに異なる $n$ 個（$n\ge 3$）の実数の集合 $S=\{a_1,\ a_2,\ \cdots,\ a_n\}$ が次の性質をもつという．

「$S$ から相異なる要素 $a_i$，$a_j$ をとれば $a_i-a_j$，$a_j-a_i$ の少な くとも一方は必ず $S$ に属する」

このとき，

(1)

次の2つのうちのいずれか一方が成り立つことを示せ．
（イ） $a_i\ge 0\ (i=1,\ 2,\ \cdots,\ n)$
（ロ） $a_i\le 0\ (i=1,\ 2,\ \cdots,\ n)$

(2)

$a_1,\ a_2,\ \cdots ,\ a_n$ の順序を適当に変えれば 等差数列になることを示せ．

入試問題 5   解答5 ［85お茶の水女子大］

自然数を要素とする空集合でない集合$G$が次の条件(i),(ii)を満たしているとする．

(i)

$m,\ n$が$G$の要素ならば，$m+n$は$G$の要素である．

(ii)

$m,\ n$が$G$の要素で$m>n$ならば，$m-n$は$G$の要素である．

このとき$G$の最小の要素を$d$とすると $G=\{kd\ \vert\ k\ は自然数\ \}$であることを証明せよ．

入試問題 6 (解答6)   ［08奈良県立医大］

$p,\ q$を互いに素な正整数とする．

(1)

任意の整数$x$に対して，$p$個の整数 $x-q$，$x-2q$，$\cdots$，$x-pq$を$p$で割った余りはすべて相異なることを証明せよ．

(2)

$x>pq$なる任意の整数$x$は，適当な正整数$a,\ b$を用いて$x=pa+qb$と表せることを証明せよ．

入試問題 7 (解答7)   ［00大阪女子大］

$a,\ b$ は互いに素な正の整数とする．

(1)

$4m+6n=7$を満たす整数 $m,\ n$ は存在しないことを示せ．

(2)

$3m+5n=2$を満たすすべての整数の組 $(m,\ n)$ を求めよ．

(3)

$k$ を整数とするとき， $ak$ を $b$ で割った余りを $r(k)$ で表す． $k,\ l$ を $b-1$ 以下の正の整数とするとき， $k\ne l$ ならば $r(k)\ne r(l)$ であることを示せ．

(4)

$am+bn=1$ を満たす整数 $m,\ n$ が存在することを示せ．

入試問題 8 (解答8)   ［立命改題］

$a,\ b,\ c$ は正の整数とし $a,\ b$ は互いに素であるとする． $x_0,\ y_0$ は整数で， $ax_0+by_0=c$ を満たすものとする．このとき次のことを証明せよ．

(1)

整数 $l$ ， $m$ が $al+bm=c$ を満たすとき

$$l=x_0+bu,\ m=y_0-au$$

を満たす整数 $u$ が存在する．

(2)

$c=ab$ のとき $ax+by=c$ を満たす正の整数の組 $(x,\ y)$ は存在しない．

(3)

$c>ab$ のとき $ax+by=c$ を満たす正の整数の組 $(x,\ y)$ が存在する．

(4)

$ax+by=k,\ 0<k\le ab$ を満たす正の整数の組 $(x,\ y)$ が存在しない $k$ はいくつあるか．

入試問題 9 (解答9)   ［02金沢後期理系］

$p,\ q$ は互いに素な整数とし， $1<p<q$ とする．座標平面内の集合 $L$ を

$$L=\{\ (m,\ n)\ \vert\ m,\ n は整数で0 \le m <q-1,\ 0 \le n <p-1\ \}$$

とし，$L$ の各元 $\mathrm{A}(m,\ n)$ に対し $N(\mathrm{A})=mp+nq$ とおく．

(1)

$L$ の各元 $\mathrm{A},\ \mathrm{B}$ について， $N(\mathrm{A})=N(\mathrm{B})$ ならば $\mathrm{A}=\mathrm{B}$ であることを示せ．

(2)

$L$ の各元 $\mathrm{A}(m,\ n)$ に対し，$L$ の元 $\mathrm{A}^{\char93 }(q-2-m,\ p-2-n)$ を対応させる． $\mathrm{A}^{\char93 } \ne \mathrm{A}$ を示せ．

(3)

$N(\mathrm{A})\le pq-(p+q)$ となるためには， $N(\mathrm{A}^{\char93 })\ge pq-(p+q)$ であることが必要十分条件であることを示せ．

(4)

$N(\mathrm{A})\le pq-(p+q)$ を満たす $L$ の元 $\mathrm{A}$ の個数を求めよ．

入試問題 10 (解答10)   ［00阪大］

どのような負でない二つの整数 $m$ と $n$ をもちいても

$$x=3m+5n$$

とは表すことができない正の整数 $x$ をすべて求めよ．

入試問題 11 (解答11)   ［00京大理系後期］

$xy$ 平面上の点で $x$ 座標， $y$ 座標がともに整数である点を格子点という．

$a,\ k$ は整数で $a\ge 2$ とし，直線

$$L\ :\ ax+(a^2+1)y=k$$

を考える．

(1)

直線 $L$ 上の格子点を一つ求めよ．

(2)

$k=a(a^2+1)$ のとき， $x>0,\ y>0$ の領域に直線 $L$ 上の格子点は 存在しないことを示せ．

(3)

$k>a(a^2+1)$ ならば， $x>0,\ y>0$ の領域に直線 $L$ 上の格子点が 存在することを示せ．

入試問題 12 (解答12)   ［89京大］

座標平面において，$x$ 座標，$y$ 座標がともに整数である点を格子点と呼ぶ．

四つの格子点 $\mathrm{O}(0,\ 0),\ \mathrm{A}(a,\ b),\ \mathrm{B}(a,\ b+1),\ \mathrm{C}(0,\ 1)$ を考える．ただし，$a,\ b$ は正の整数で，その最大公約数は1である．

(1)

平行四辺形OABCの内部(辺，頂点は含めない)に格子点はいくつあるか.

(2)

(1)の格子点の全体を $\mathrm{P}_1,\ \mathrm{P}_2,\ \cdots,\ \mathrm{P}_t$ とするとき， $\bigtriangleup\mathrm{OP}_i\mathrm{A}\ \ (i=1,\ 2,\ \cdots,\ t)$ の面積のうちの 最小値を求めよ．ただし $a>1$ とする．

入試問題 13 (解答13)   ［91東大］

$xy$ 平面上， $x$ 座標， $y$ 座標がともに整数であるような点 $(m,\ n)$ を格子点と呼ぶ．

各格子点を中心として半径 $r$ の円がえがかれており， 傾き $$\frac{2}{5}$$ の任意の直線はこれらの円のどれかと共有点をもつという． このような性質をもつ実数 $r$ の最小値を求めよ．

入試問題 14 (解答14)   ［90京大後期］

$n$ を奇数とし， $$f(x)=\left\vert \sin \frac{ 2 \pi x}{n} \right\vert$$ とする．

1. 集合 $\{f(k) \vert k は整数 \}$ は何個の元をもつか．
2. $m$ を $n$ と素な整数とする．

   集合
   

   $$\left\{f(mk) \Big\vert k は 0 \le k \le \dfrac{n-1}{2} なる整数 \right\}$$
   
   
   は $m$ によらず一定であることを示せ．

入試問題 15 (解答15)   ［08名大理系］

次の問いに答えよ．

(1)

$3x+2y\le 2008$ を満たす0以上の整数の組$(x,\ y)$の個数を求めよ．

(2)

$\dfrac{x}{2}+\dfrac{y}{3}+\dfrac{z}{6}\le 10$ を満たす0以上の整数の組$(x,\ y,\ z)$の個数を求めよ．

入試問題 16 (解答16)   ［88群馬大］

自然数 $k$ を2の累乗と奇数の積として $k=2^am\ (a は 2の累乗の指数,\ m は奇数)$ と表すとき, $f(k)=a$ と定める.

$$S_n=\sum_{k=1}^nf(k)$$

とするとき,

(1)

$S_{50}$ を求めよ.

(2)

$n$ が2の累乗のとき $S_n$ を $n$ の式で表せ.

(3)

$\dfrac{n-1}{2}\le S_n<n$ であることを示せ．

入試問題 17 (解答17)   ［97京大文］

自然数 $n$ の約数の個数を $d$ とする． $n$ の約数をすべて並べて得られる 数列を $a_k\ (1 \le k \le d)$ とする．したがって， $a_1=1$ ， $a_d=n$ ， $a_k<a_{k+1}\ (1 \le k < d)$ である．このとき， $n$ に対する次の二つの条件(イ)，(ロ)は互いに同値((イ) $\iff$ (ロ))であることを示せ．

    (イ)    $n$ は60の倍数である．
    (ロ)    $n$ は6個以上の約数を持ち， $\dfrac{1}{a_3}+\dfrac{1}{a_6}=\dfrac{1}{a_2}$ となる．

入試問題 18 (解答18)   ［98上智大］

(1)

81 のすべての正の約数1,…,81の和を求めよ．

(2)

378の正の約数の個数と，それらの和を求めよ．

(3)

自然数 $N$ のすべての正の約数の和は60であるという． このような $N$ はいくつあるか．そのうち2と3のみの積で表せるものは何か．

入試問題 19 (解答19)   ［98京大後期文系］

$a,\ b,\ p,\ q$ はすべて自然数で，

$$\dfrac{p^2+q^2}{a}= \dfrac{pq}{b}$$

を満たしている． $a$ と $b$ の最大公約数が1のとき以下の問いに答えよ．

(1)

$pq$ は $b$ で割り切れることを示せ．

(2)

$\sqrt{a+2b}$ は自然数であることを示せ．

入試問題 20 (解答20)   ［99京大文後期］

自然数$a,\ b,\ c$について，等式$a^2+b^2=c^2$が成り立ち， かつ$a,\ b$は互いに素とする．このとき，次のことを証明せよ．

(1)

$a$が奇数ならば，$b$は偶数であり，したがって$c$は奇数である．

(2)

$a$が奇数のとき，

$$a+c=2d^2$$

となる自然数$d$が存在する．

入試問題 21 (解答21)   ［02九大前期理系］

正の整数 $a$ に対し, $a$ の正の約数全体の和を $f(a)$ で表す． ただし，1および $a$ 自身も約数とする．たとえば $f(1)=1$であり， $a=15$ ならば15の正の約数は1,3,5,15なので$f(15)=24$となる．次の問いに答えよ．

(1)

$a$ が正の奇数 $b$ と正の整数 $m$ を用いて$a=2^mb$と表されるとする． このとき

$$f(a)=(2^{m+l}-1)f(b)$$

が成り立つことを示せ．

(2)

$a$ が2以上の整数 $p$ と正の整数 $q$ を用いて$a=pq$と表されるとする． このとき

$$f(a)\ge (p+1)q$$

が成りたつことを示せ．また，等号が成り立つのは，$q=1$かつ$p$が素数であるときに 限ることを示せ．

(3)

正の偶数 $a,\ b$ は，ある整数$m,\ n$とある奇数 $r,\ s$ を用いて $a=2^mr,\ b=2^ns$のように表すことができる．このとき $a,\ b$ が

$$\left\{ \begin{array}{l} f(a)=2b\\ f(b)=2a \end{array} \right.$$

をみたせば，$r,\ s$は素数であり，かつ $r=2^{n+1}-1,\ s=2^{m+1}-1$ となることを示せ．

次: 剰余類 上: 数論の基礎 前: 素因数分解