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

演習問題

練習問題 10 (解答10)  

$a$ を十進法で表して

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

となるとする.このとき,

\begin{displaymath}
\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}
\end{displaymath}

練習問題 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)  

\begin{displaymath}
26x\equiv 1\quad (\bmod.\ 57)
\end{displaymath}

を解け.

練習問題 18 (解答18)  

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

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

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

\begin{displaymath}
a\equiv b\quad (\bmod.\ d)
\end{displaymath}

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

練習問題 19 (解答19)  

$n$ 個の合同方程式

\begin{displaymath}
x\equiv a_i\quad (\bmod.\ m_i),\ i=1,\ 2,\ \cdots,\ n
\end{displaymath}

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

\begin{displaymath}
a_i\equiv a_j\quad (\bmod.\ (m_i,\ m_j)),\ i,\ j=1,\ 2,\ \cdots,\ n
\end{displaymath}

であることを示せ. このとき解は $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$ に対して

\begin{displaymath}
x^2\equiv \alpha\,(\bmod.\ 2^e)
\end{displaymath}

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

\begin{displaymath}
\pm x_0,\ \pm x_0 +2^{e-1}
\end{displaymath}

と表されることを示せ.

練習問題 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)$が乗法的関数のとき $\displaystyle 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$ 乗根とすれば

\begin{displaymath}
\alpha^k\ (k=0,\ 1,\ \cdots,\ n-1)
\end{displaymath}

がすべての $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$ の倍数でないとすると,

\begin{displaymath}
f(0),\ f(1),\ \cdots,\ f(p-1)
\end{displaymath}

のうちで, $p$ の倍数となるものは, $n$ 個以下であることを $n$ に関する数学的帰納法で示せ.
(2)
$f(x)$ を整数係数の $n$ 次多項式とし $p$ を素数とする. このとき,

\begin{displaymath}
f(0),\ f(1),\ \cdots,\ f(p-1)
\end{displaymath}

のうちに, $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$ について,

\begin{displaymath}
p が素数\quad \iff\quad (p-2)!-1 が p の倍数
\end{displaymath}

を示せ.

練習問題 33 (解答33)  

因数分解

\begin{displaymath}
x^{2k+1}+1=(x+1)(x^{2k}-x^{2k-1}+x^{2k-2}-\cdots-x+1)
\end{displaymath}

を活用して,任意の自然数 $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$ とする.底の取り方に関係なく,

\begin{displaymath}
\Ind.\,(-1)=\dfrac{p-1}{2}
\end{displaymath}

練習問題 39 (解答39)  

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

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

練習問題 40 (解答40)  

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

練習問題 41 (解答41)  

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

\begin{displaymath}
1^k+2^k+\cdots+(p-1)^k\equiv 0\quad (\bmod.\ p)
\end{displaymath}

練習問題 42 (解答42)  

$p$ が素数ならば

\begin{displaymath}
(p-1)!\equiv -1\quad (\bmod.\ p)
\end{displaymath}

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

関連入試問題

入試問題 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$ 次の多項式

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

について次のことを証明せよ.
(1)
有理数 $\alpha$ が方程式$f(x)=0$の1つの解ならば,$\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$と互いに素な自然数の総数とする.すなわち

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

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

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

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

  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{displaymath}
\begin{array}{l}
320^2=102400\,; 322^2=103684\,; 324...
...6^2=106276\,; 328^2=107584\,; 330^2=108900
\end{array}
\end{displaymath}

入試問題 27 (解答27)   [70東大理系]

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

(1)
$\alpha^n$ は何個の異なる値をとりうるか.
(2)

\begin{displaymath}
\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)}
\end{displaymath}

の値を求めよ.

入試問題 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$ は次を満たしているとする.

\begin{displaymath}
G\ の任意の元\ z,\ w の積\ zw\ は再び\ G\ の元である.
\end{displaymath}

(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)におけるあなたの得点とする.

next up previous 次: 相互法則 上: 剰余類 前: 指数
Aozora Gakuen