次: 整式の整数論 上: フェルマの小定理 前: フェルマの小定理

演習問題

問題 21   解答21    ［03名大改題(3)追加］

$n$を自然数とするとき，$m\le n$で$m$と$n$の最大公約数が1となる自然数$m$の個数を$f(n)$とする．

(1)

$f(15)$を求めよ．

(2)

$p,\ q$を互いに素な素数とする．このとき$f(pq)$を求めよ．

(3)

$p$を素数，$e$を自然数とする．このとき$f(p^e)$を求めよ．

問題 22   解答22     ［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}$$
   
   

問題 23   解答23     ［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)におけるあなたの得点とする．

問題 24   解答24     ［東京農大］

$p$を素数，$n$を$p$で割り切れない自然数とし，1から$p-1$までの自然数の集合を$A$とおく．

(1)

任意の$k\in A$に対し，$nk$を$p$で割った余りを$r_k$とする． このとき，集合 $\{r_k\ \vert\ k \in A\}$は$A$と一致することを示せ．

(2)

$n^{p-1}-1$は$p$で割り切れることを示せ．

問題 25   解答25     ［奈良女子大改題］

(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$ で割った余りを推測し, 数学的帰納法で証明せよ.

問題 26   解答26     ［10阪大後期］

$p$は素数，$r$は正の整数とする．以下の問いに答えよ.

1. $x_1,\ x_2,\ \cdots,\ x_r$についての式 $(x_1+x_2+\cdots+x_r)^p$を展開したときの単項式 ${x_1}^{p_1}{x_2}^{p_2}\cdots{x_r}^{p_r}$の係数を求めよ． ここで， $p_1,\ p_2,\ \cdots,\ p_r$は0または正の整数で $p_1+p_2+\cdots+p_r=p$をみたすとする.
2. $x_1,\ x_2,\ \cdots,\ x_r$が正の整数のとき，
   
   $$(x_1+x_2+\cdots+x_r)^p-({x_1}^p+{x_2}^p+\cdots+{x_r}^p)$$
   
   は$p$で割り切れることを示せ．
3. $r$は$p$で割り切れないとする． このとき，$r^{p-1}-1$は$p$で割り切れることを示せ．

次: 整式の整数論 上: フェルマの小定理 前: フェルマの小定理