次: 相互法則 上: 剰余類 前: 指数

演習問題

練習問題 10 (解答10)  

$a$ を十進法で表して

$$a=a_n10^n+a_{n-1}10^{n-1}+\cdots+a_110+a_0$$

となるとする．このとき，

$$\begin{array}{l} a\equiv a_0+a_1+\cdots+a_n\quad (\bmod\... ...uiv a_0-a_1+\cdots+(-1)^{n}a_n\quad (\bmod\ 11) \end{array}$$

練習問題 11 (解答11)  

今日が金曜日であるとする． $10^6$ , $10^{100}$ , $3^{100}$ 日後はそれぞれ何曜日か．

練習問題 12 (解答12)  

3で割れば1余り，5で割れば2余り，7で割れば3余る正で最小の整数を求めよ．

練習問題 13 (解答13)  

(1)

$2^{65}+1$は11で割り切れることを示せ．

(2)

$n$ が正の整数のとき, $13^{2n}+6$ は7で割り切れることを示せ．

(3)

$3^{15}$ および $(3^{15})^{15}$ の $1$ の位の数を求めよ.

(4)

$(2^{100}-1)^{99}$ を100で割ったときの余りを求めよ．

練習問題 14 (解答14)  

$n$ を整数とする．

(1)

$n^2$ を7で割るとあまりは $0,\ 1,\ 2,\ 4$ のいずれかである．

(2)

$n^5-n$ は10の倍数である．

(3)

$n$ が奇数なら $n^2-1$ は8で割り切れる．

(4)

$n^4+2n^3+11n^2+10n$ は、$24$ の倍数である．

練習問題 15 (解答15)       

(1)

整数 $a,\ b$ に対して，$a^2+b^2=c^2$ となる整数 $c$ が存在するとき， $a,\ b$ の少なくとも一方は $3$ の倍数であることを示せ．

(2)

整数 $a,\ b,\ c$ が $a^2+b^2=c^2$を満たすとき，$a,\ b,\ c$ のうち少なくとも $1$ つは $5$ の倍数であることを示せ．

練習問題 16 (解答16)  

$a,\ b$ は正の整数で，$a$ を $11$ で割ると余りが $3$，$a^3+b$ を $11$ で割ると 余りが $4$ であるという．このとき $b$ を $11$ で割ると，余りはいくらか．

練習問題 17 (解答17)  

$$26x\equiv 1\quad (\bmod.\ 57)$$

を解け．

練習問題 18 (解答18)  

法 $m,\ n$ の最大公約数を $d$ ，最小公倍数を $l$ とする．

$$\left\{ \begin{array}{l} x\equiv a\quad (\bmod.\ m),\\ x\equiv b\quad (\bmod.\ n). \end{array} \right.$$

が解を持つ必要十分条件は

$$a\equiv b\quad (\bmod.\ d)$$

であることを示せ． またこのとき，解は $l$ を法としてただ一つであることを示せ．

練習問題 19 (解答19)  

$n$ 個の合同方程式

$$x\equiv a_i\quad (\bmod.\ m_i),\ i=1,\ 2,\ \cdots,\ n$$

が解を持つための必要十分条件は

$$a_i\equiv a_j\quad (\bmod.\ (m_i,\ m_j)),\ i,\ j=1,\ 2,\ \cdots,\ n$$

であることを示せ． このとき解は $m_1,\ m_2,\ \cdots,\ m_n$ の最小公倍数を法としてただ一つであることを示せ．

練習問題 20 (解答20)  

次の合同方程式を解け．

(1)

$x^2+x+1\equiv 3\quad (\bmod.\ 25)$

(2)

$x^2\equiv 1\quad (\bmod.\ 39)$

練習問題 21 (解答21)   『初等整数論講義』（高木貞治著），39ページ〔問題1〕より．

$\alpha\equiv 1\,(\bmod.\ 8)$ であるとする．このとき $e\ge 3$ に対して

$$x^2\equiv \alpha\,(\bmod.\ 2^e)$$

の$2^e$を法とする解は四つあり，その一つを$x_0$とすれば4解は

$$\pm x_0,\ \pm x_0 +2^{e-1}$$

と表されることを示せ．

練習問題 22 (解答22)  

(1)

1 から 1512 までの自然数で 1512 と互いに素なものはいくつあるか．

(2)

それらの和はいくらか．

練習問題 23 (解答23)  

$xy$ 平面上，不等式$0<x\le 12$，$0<y\le 12$で定まる領域にある格子点を考える．

原点とこれらの格子点を結ぶ線分で，両端以外に格子点が乗っていないものは 何本あるか．

練習問題 24 (解答24)  

$a,\ b,\ c,\ \cdots$ は二つずつ互いに素であるとし， $\Phi (x)$は実数 $x$ を超えない自然数のなかで $aでも,\ bでも,\ cでも,\ \cdots$ 割り切れないものの個数を表すとする．

$$\begin{eqnarray*} \Phi (x)&=&[x] - \left[\dfrac{x}{a} \right]- \left[\dfrac{... ...]+ \cdots \\ &&\quad - \left[ \dfrac{x}{abc}\right]- \cdots \end{eqnarray*}$$

を示せ．ただし $[x]$ は $x$ を超えない最大の整数を表す．

練習問題 25       (解答25)

整数で定義された関数$F(n)$が乗法的関数のとき $$G(n)=\sum_{d\vert n}F(d)$$ で定義された関数$G(n)$も乗法的関数であることを示せ． また，この事実を用いて補題2の別証を考えよ．

練習問題 26       (解答26)

正の実数 $x$ を超えない自然数のうちで $n$ と互いに素であるものの 個数を $\varphi(n,\ x)$ とおく． $\varphi(n,\ n)=\varphi(n)$ である． $[x]$ で $x$ を超えない整数を表すと定理19，定理20の一般化として

$$\begin{eqnarray*} \sum_{d\vert n}\varphi(d,\ dx)&=&[nx]\\ \varphi(n,\ x)&=&\sum_{d\vert n}\mu (d)\left[ \dfrac{x}{d} \right] \end{eqnarray*}$$

が成り立つことを示せ．

練習問題 27 (解答27)  

$F_n(x)$ の定数項は $n=1$ の場合以外 $+1$ であることを示せ．

練習問題 28 (解答28)  

$F_n(x)$ の第二項($\varphi(n)-1$次の項)の係数は $-\mu(n)$ に等しいことを示せ． つまり1の原始 $n$ 乗根の和は $\mu (n)$ である．

練習問題 29 (解答29)  

$\alpha$ を1の原始 $n$ 乗根とすれば

$$\alpha^k\ (k=0,\ 1,\ \cdots,\ n-1)$$

がすべての $n$ 乗根で，そのうち $(k,\ n)=1$ なる $k$ に対する ものがちょうど原始 $n$ 乗根になることを示せ．

練習問題 30 (解答30)  

次のことを示せ．

(1)

互いに素な二つの整数 $a,\ b$ に対し，1の $a$ 乗根と $b$ 乗根を すべての組合せについて掛けて得られる $ab$ 個の積が1の $ab$ 乗根の全部になる．

(2)

1の 原始$a$ 乗根と 原始$b$ 乗根を すべての組合せについて掛けるなら1の 原始$ab$ 乗根の全部が得られる．

以下の練習問題は,『めざせ，数学オリンピック』(J.コフマン，現代数学社)に教えられた．

練習問題 31 (解答31)  

$a$ の法 $m$ に関する指数を $e$ とする．整数 $a^k$ の指数は $\dfrac{e}{(k,\ e)}$ である．

練習問題 32 (解答32)  

歴史的に有名なウイルソンの定理，ライプニッツの定理を次の順に証明せよ．

(1)

$f(x)$ を整数係数の $n$ 次多項式とし $p$ を素数とする． このとき， $f(x)$ の最高次の係数が $p$ の倍数でないとすると，

$$f(0),\ f(1),\ \cdots,\ f(p-1)$$

のうちで， $p$ の倍数となるものは， $n$ 個以下であることを $n$ に関する数学的帰納法で示せ．

(2)

$f(x)$ を整数係数の $n$ 次多項式とし $p$ を素数とする． このとき，

$$f(0),\ f(1),\ \cdots,\ f(p-1)$$

のうちに， $p$ の倍数となるものが $n+1$ 個以上あれば $f(x)$ の係数はすべて $p$ の倍数であることを示せ．

(3)

任意の素数 $p$ について，$(p-1)!+1$は $p$ で割り切れることを示せ．

[ヒント] 必要なら $f(x)=(x-1)(x-2)\cdots(x-p+1)-x^{p-1}+1$ を用いよ．

(4)

自然数 $p>2$ について，

$$p が素数\quad \iff\quad (p-2)!-1 が p の倍数$$

を示せ．

練習問題 33 (解答33)  

因数分解

$$x^{2k+1}+1=(x+1)(x^{2k}-x^{2k-1}+x^{2k-2}-\cdots-x+1)$$

を活用して，任意の自然数 $m$ に対して $(m!)^2+1$ の素因数はすべて $4n+1$ 型の素数であることを示せ． これから$4n+1$ 型の素数が無数にあることを示せ．

練習問題 34 (解答34)  

$n=91=7\cdot13$のとき, $\dfrac{1}{91}$ から $\dfrac{90}{91}$ を循環節が同じもので分類せよ．

練習問題 35 (解答35)  

$p=41$法とする原始根を一つ求めよ．

練習問題 36 (解答36)  

例2.5.2の表を活用して $p=13,\ r=2$ のとき．次のものを求めよ．

(1)

$\Ind.\,100$ の値

(2)

$\Ind.\,(-1)$ の値

(3)

$\Ind.\,x=9$ となる $x$ の値

(4)

$\Ind.\,x=-1$ となる $x$ の値

練習問題 37 (解答37)  

例2.5.2の表を活用して $x$ を求めよ．

(1)

$11x\equiv 5\quad (\bmod.\ 13)$

(2)

$x^3\equiv 5\quad (\bmod.\ 13)$

(3)

$5x^2+3x-10\equiv 0\quad (\bmod.\ 13)$

練習問題 38 (解答38)  

$p\ne 2$ とする．底の取り方に関係なく，

$$\Ind.\,(-1)=\dfrac{p-1}{2}$$

練習問題 39 (解答39)  

$p\ne 2$ とする． $a+b=p$ ならば

$$\Ind.\,a-\Ind.\,b\equiv \dfrac{p-1}{2}\quad (\bmod.\ p-1)$$

練習問題 40 (解答40)  

$$\Ind_r\,a\equiv \dfrac{\Ind_{r'}\,a}{\Ind_{r'}\,r}\quad (\bmod.\ p-1)$$

練習問題 41 (解答41)  

$k$ が $p-1$ で割りきれないならば

$$1^k+2^k+\cdots+(p-1)^k\equiv 0\quad (\bmod.\ p)$$

練習問題 42 (解答42)  

$p$ が素数ならば

$$(p-1)!\equiv -1\quad (\bmod.\ p)$$

(ウイルソンの定理の別証明)

関連入試問題

入試問題 22 (解答22)   ［82名古屋市大］

$n$ を自然数とするとき， $3^{n+1}+4^{2n-1}$ は13で割りきれることを証明せよ．

入試問題 23 (解答23)   ［東工大］

$n$ を正の整数とするとき、 $19^n+(-1)^{n-1}2^{4n-3}$ は、 $7$ の倍数であることを示せ．

入試問題 24 (解答24)   ［82九大］

整数を係数とする $n$ 次の多項式

$$f(x)=x^n+a_1x^{n-1}+ \cdots +a_{n-1}x+a_n \,\,(n>1)$$

について次のことを証明せよ．

(1)

有理数 $\alpha$ が方程式$f(x)=0$の１つの解ならば，$\alpha$ は整数である．

(2)

ある自然数 $k(>1)$ に対して， $k$ 個の整数 $f(1),\ f(2),\ \cdots,\ f(k)$ のどれもが $k$ で割り切れなければ方程式 $f(x)=0$ は有理数の解をもたない．

入試問題 25 (解答25)   ［01京大文系前期］

任意の整数 $n$ に対し， $n^9-n^3$ は9で割り切れることを示せ．

入試問題 26 (解答26)   ［06横浜市大2番］

$N$を自然数とし，$\phi(N)$を$N$より小さくかつ$N$と互いに素な自然数の総数とする．すなわち

$$\phi(N)=♯\{n\ \vert\ n は自然数，1\le n <N，gcd(N,\ n)=1\ \}$$

で，オイラー関数と呼ばれている．ここに$gcd(a,\ b)$は$a$と$b$の最大公約数を，$♯A$は集合$A$の要素の総数を意味する．例えば，

$$\phi(6)=♯\{1,5\}=2,\ \phi(15)=♯\{1,2,4,7,8,11,13,14\}=8$$

である．このとき以下の問いに答えよ．

1. $p$と$q$を互いに異なる素数とし$N=pq$とおく．
   1. $N$より小さい自然数$n$で， $gcd(N,\ n)\ne 1$となるものを全て求めよ．
   2. $\phi(N)$を求めよ．
2. $p$と$q$を互いに異なる素数とし$N=pq$とおく． 今$N$と$\phi(N)$があらかじめわかつているとき， $p$と$q$を解としてもつ二次方程式を$N$や$\phi(N)$等を用いて 表せ．
3. $N=84773093$および $\phi(N)=84754668$であるとき，$N=pq\ (p>q)$となる素数$p$および$q$を求めよ(求めた$p$および$q$が素数であることを示さなくてよい)．

   ただし,必要に応じて以下の数表を使つてもよい．
   

   $$\begin{array}{l} 320^2=102400\,； 322^2=103684\,； 324... ...6^2=106276\,； 328^2=107584\,； 330^2=108900 \end{array}$$
   
   

入試問題 27 (解答27)   ［70東大理系］

$i$ を虚数単位とし $\alpha=\cos \dfrac{\pi}{3}+i\sin \dfrac{\pi}{3}$ とおく．また $n$ はすべての自然数にわたって動くとする．このとき

(1)

$\alpha^n$ は何個の異なる値をとりうるか．

(2)

$$\dfrac{(1-\alpha^n)(1-\alpha^{2n})(1-\alpha^{3n}) (1-\al... ...-\alpha)(1-\alpha^2)(1-\alpha^3) (1-\alpha^4)(1-\alpha^5)}$$

の値を求めよ．

入試問題 28 (解答28)   ［01京大理系］

$p$ を2以上の整数とする．2以上の整数 $n$ に対し，次の条件(イ)，(ロ)を みたす複素数の組 $(z_1,\ z_2,\ \cdots,\ z_n)$ の個数を $a_n$ とする．

$$\begin{eqnarray*} (イ)&&k=1,\ 2,\ \cdots,\ n\ に対し， {z_k}^p=1 かつ，z_k\ne 1\\ (ロ)&&z_1z_2\cdots z_n=1 \end{eqnarray*}$$

このとき次の問いに答えよ．

(1)

$a_3$ を求めよ．

(2)

$a_{n+2}$ を $a_n$ ， $a_{n+1}$ の一方または両方を用いて 表せ．

(3)

$a_n$ を求めよ．

入試問題 29 (解答29)   ［01京都府立医大］

0でない複素数からなる集合 $G$ は次を満たしているとする．

$$G\ の任意の元\ z,\ w の積\ zw\ は再び\ G\ の元である．$$

(1)

ちょうど $n$ 個の複素数からなる $G$ の例をあげよ．

(2)

ちょうど $n$ 個の複素数からなる $G$ は (1) の例以外にないことを示せ．

入試問題 30 (解答30)   ［奈良女子大改題］

(1)

素数$p$と$1\le r\le p-1$なる整数 $r$に対して, 二項係数についての等式 $r{}_p\mathrm{C}_r=p{}_{p-1}\mathrm{C}_{r-1}$ を証明し, ${}_p\mathrm{C}_r$ は $p$ の倍数であることを示せ.

(2)

素数 $p$ に対して $2^p$ を $p$ で割った余りを求めよ.

(3)

自然数 $n$ に対して $n^p$ を $p$ で割った余りを推測し, 数学的帰納法で証明せよ.

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

自然数 $n$ の関数 $f(n),\ g(n)$ を

$$\begin{eqnarray*} &&f(n)=n\mbox{を}7\mbox{で割った余り}\\ &&g(n)=3f\left(\sum_{k=1}^7k^n\right) \end{eqnarray*}$$

によって定める.

(1)

すべての自然数 $n$ に対して $f(n^7)=f(n)$ を示せ.

(2)

あなたの好きな自然数 $n$ を一つ決めて $g(n)$ を求めよ. その $g(n)$ の値をこの設問(2)におけるあなたの得点とする．

次: 相互法則 上: 剰余類 前: 指数