次: 7章 上: 解答 前: 5章

6章

解答 21   問題21    

(1)

15と互いに素な15以下の数は

$$1,\ 2,\ 4,\ 7,\ 8,\ 11,\ 13,\ 14$$

である．よって$f(15)=8$．

(2)

$1\le m \le pq$の範囲にある$pq$と互いに素でない数は $p$の倍数と$q$の倍数でありそれぞれ，

$$\{p,\ 2p,\ \cdots,\ pq\},\ \{q,\ 2q,\ \cdots,\ pq\}$$

である．$pq$が共通なので，互いに素でない数が

$$q+p-1$$

よって

$$f(pq)=pq-(q+p-1)=(p-1)(q-1)$$

(3)

1から $p^e$ までの数のなかで $p^e$ と互いに素では ないものは， $p$ で割り切れるものに他ならず，それは

$$1\cdot p,\ 2\cdot p,\ \cdots,\ p^{e-1}\cdot p$$

の $p^{e-1}$ 個だけある．よって

$$f(p^e)=p^e-p^{e-1}=p^e \left(1-\dfrac{1}{p} \right)$$

である．

解答 22   問題22    

1. 1. $gcd(N,\ n)\ne 1$となるものは，$p$または$q$の倍数である． したがって$N$より小さい自然数$n$では
      
      $$\begin{array}{l} p,\ 2p,\ 3p,\ \cdots,\ (q-1)p\\ q,\ 2q,\ 3q,\ \cdots,\ (p-1)q \end{array}$$
      
      である．
   2. $1\le n<N$の範囲で $gcd(N,\ n)\ne 1$となるものが(i)より
      
      $$(q-1)+(p-1)\ 個$$
      
      ある．同じ範囲で$gcd(N,\ n)=1$となるものはそれらを除いたものである．
      
      $$∴\quad \phi(N)=pq-1-(q-1)-(p-1)=(p-1)(q-1)$$
      
      
2. $N=pq$なので(ii)から
   
   $$\phi(N)=N-(p+q)+1$$
   
   つまり，
   
   $$p+q=N+1-\phi(N),\ pq=N$$
   
   よって， $p$と$q$を解としてもつ二次方程式は未知数を$x$とすれば次のようになる．
   
   $$x^2-\{N+1-\phi(N)\}x+N=0$$
   
   
3. 
   
   $$N+1-\phi(N)=18426=2\cdot 9213$$
   
   である．よって
   
   $$p,\ q=9213\pm\sqrt{9213^2-84754668}=9213\pm\sqrt{106276}=9539,\ 8887$$
   
   

解答 23   問題23    

(1)

自然数 $m,\ n$ を7で割った商をそれぞれ $m',\ n'$, 余りをそれぞれ $i,\ j$ とおくと, $m=7m'+i,\ n=7n'+j$ と書けて

$$mn=(7m'+i)(7n'+j)=7(7m'n'+m'j+n'i)+ij$$

より, $f(mn)=f(ij)$ を得る. そこで, これを用いて, 自然数 $n$ を7で割った余りで分類し, $n^2,\ n^3,\ \cdots,\ n^7$ を7で割った余りを順に求めていくと, 下表のようになる.

$$\begin{array}{\vert c\vert\vert c\vert c\vert c\vert c\ver... ...ine n^7 & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ \hline \end{array}$$

よって, すべての自然数 $n$ に対して

$$f(n^7)=f(n)$$

注意 7        これは言うまでもなく「フェルマの小定理」そのものである．文系入試問題であるので，実際に7で割った余りの表を作ることで論証した．

他の演習問題にあるように，$n^7-n$ が7の倍数になることを$n$ に関する数学的帰納法で示すことができる．

(2)

(1)の結果より, すべての自然数 $k$ に対して, $k^7-k$ は7の倍数であるから

$$\sum_{k=1}^7 k^{n+6}-\sum_{k=1}^7 k^n= \sum_{k=1}^7 k^{n-1}(k^7-k)=7l\quad (l\ は自然数)$$

$$∴\quad g(n+6)=g(n)$$

よって, $1\le n\le6$ の範囲で考えれば十分である. ここで, (1)の表を利用すると

$$\begin{eqnarray*} &&g(1)=3f(1+2+3+4+5+6+0)=3f(21)=0\\ &&g(2)=3f(1+4+2+2+4+1+0... ...f(1+4+5+2+3+6+0)=3f(21)=0\\ &&g(6)=3f(1+1+1+1+1+1+0)=3f(6)=18 \end{eqnarray*}$$

となるから, $n=6$ をとれば

$$g(6)=18$$

解答 24   問題24    

(1)

集合 $\{r_k\ \vert\ k \in A\}$を$B$とする．$n$と$p$が互いに素なので

$$r_k=0\quad \iff\quad nkがpの倍数 \quad \iff\quad kがpの倍数$$

$1\le k\le p-1$よりこれはない． よって$0 \not\in B$である．従って$B\subset A$．次に$i,\ j\in A$に対して

$$r_i=r_j\quad \iff\quad n(i-j)がpの倍数 \quad \iff\quad i-j がpの倍数$$

$-p+2\le i-j\le p-2$なので$i-j=0$． つまり$i\ne j$なら$r_i\ne r_j$．

よって$B$は$p-1$個の要素からなり， $A$の要素の個数と一致する．よって $B=A$である．

(2)

$k\in A$に対してある整数$q_k$を用いて $nk=pq_k+r_k$とおける．

$$(ni)(nj)=p(pq_iq_j+q_ir_j+q_jr_i)+r_ir_j$$

であるから，

$$n\cdot 2n \cdot\cdots\cdot(p-1)n =pN+r_1r_2\cdots r_{p-1}$$

とある整数$N$を用いて表せる．$B=A$より

$$r_1r_2\cdots r_{p-1}=(p-1)!$$

なので

$$n^{p-1}(p-1)!-(p-1)!=pN$$

$(p-1)!$と$p$は互いに素なので $n^{p-1}-1$は$p$の倍数である．

解答 25   問題25    

(1)

$$r{}_p\mathrm{C}_r=\dfrac{rp!}{r!(p-r)!}=\dfrac{p(p-1)!}{(r-1)!\{(p-1)-(r-1)\}!} =p{}_{p-1}\mathrm{C}_{r-1}$$

上の等式の右辺は $p$ の倍数であるが, $r$ と $p$ は互いに素なので ${}_p\mathrm{C}_r$ が $p$ の倍数である.

(2)

$$2^p=(1+1)^p=1+\sum_{r=1}^{p-1}{}_p\mathrm{C}_r+1$$

(1)より $2^p-2$ は$p$の倍数である．よって余りは$2\ (p>2)$，$0(p=2)$である．

(3)

$n^p-n$ が $p$ の倍数であると推測される. これを, 数学的帰納法で示す.

(i)

$n=1$ は明らか. $n=2$ のときは(2)より成立

(ii)

$n=k$ のとき成立するとする. つまり

$$k^p-k=pMと整数Mを用いて表される.$$

このとき

$$(1+k)^p=1+\sum_{r=1}^{p-1}{}_p\mathrm{C}_rk^r+k^p =1+\sum_{r=1}^{p-1}{}_p\mathrm{C}_rk^r+pM+k$$

ここで, $$\sum_{r=1}^{p-1}{}_p\mathrm{C}_rk^r$$ は $p$ の倍数なのでこれを整数 $N$ を用いて $pN$ とおく.

$$\begin{array}{c} (1+k)^p=1+pN+k\\ ∴\quad (k+1)^p-(k+1)=pN \end{array}$$

よって, $n=k+1$ のときも成立した.

(iii)

したがって, すべての自然数 $n$ に対して, $n^p$ と $n$ を $p$ で割った余りは等しい.

つまり, $n^p$ を $p$ で割った余りは $n$ を $p$ で割った余りである．

解答 26   問題26    

1. $(x_1+x_2+\cdots+x_r)^p$の展開式は，式 $(x_1+x_2+\cdots+x_r)$を$p$個並べ， それぞれから $x_1,\ x_2,\ \cdots,\ x_r$のいずれかを取り出してかけあわせ， 加えたものである． そのうち単項式 ${x_1}^{p_1}{x_2}^{p_2}\cdots{x_r}^{p_r}$ となるものは， $x_1,\ x_2,\ \cdots,\ x_r$がそれぞれ $p_1,\ p_2,\ \cdots,\ p_r$個取り出される場合だけあり，それらを加えた係数$N$は， その取り出し方の場合の数である．

   $N$は $x_1,\ x_2,\ \cdots,\ x_r$をそれぞれ $p_1,\ p_2,\ \cdots,\ p_r$個ずつを並べる場合の数である． その一つの並べ方に対して， $p_1,\ p_2,\ \cdots,\ p_r$個ずつある $x_1,\ x_2,\ \cdots,\ x_r$の一つ一つを区別すると $p_1!p_2!\cdots p_r!$個でき，それらの並べ方の総数が$p!$である．よって
   

   $$p_1!p_2!\cdots p_r!N=p!\ ．$$
   
   つまり ${x_1}^{p_1}{x_2}^{p_2}\cdots{x_r}^{p_r}$の係数$N$は
   
   $$\dfrac{p!}{p_1!p_2!\cdots p_r!} \quad\cdots\maru{1}$$
   
   である． ここでは$p$が素数であることは用いていないので， $p_1+p_2+\cdots+p_r=p$であるような非負整数 $p_1,\ p_2,\ \cdots,\ p_r$に対して$\maru{1}$は 上記の場合の数として整数である．
2. $p_1,\ p_2,\ \cdots,\ p_r$の中に0でないものがある．それを$p_j$とする．
   
   $$\dfrac{p!}{p_1!p_2!\cdots p_r!} =\dfrac{p}{p_j}\cdot\dfrac{(p-1)!}{p_1!\cdots(p_j-1)!\cdots p_r!}$$
   
   より
   
   $$p_j\cdot\dfrac{p!}{p_1!p_2!\cdots p_r!} =p\cdot\dfrac{(p-1)!}{p_1!\cdots(p_j-1)!\cdots p_r!}$$
   
   (1)の注意より両辺整数で右辺は$p$の倍数である． ここで$p$が素数とする．$p_j<p$であるなら$p$と$p_j$は互いに素なので このとき $\dfrac{p!}{p_1!p_2!\cdots p_r!}$は$p$の倍数である．

   式
   

   $$(x_1+x_2+\cdots+x_r)^p-({x_1}^p+{x_2}^p+\cdots+{x_r}^p) \quad\cdots\maru{2}$$
   
   に現れる単項式 ${x_1}^{p_1}{x_2}^{p_2}\cdots{x_r}^{p_r}$は， そのすべての指数$p_j$が$p_j<p$である． よってその係数は$p$の倍数であり， $x_1,\ x_2,\ \cdots,\ x_r$の正の整数を代入したならばその値は $p$の倍数になる．
3. 式$\maru{2}$の $x_1,\ x_2,\ \cdots,\ x_r$にすべて1を代入する． (2)の結論から $r^p-r=r(r^{p-1}-1)$ は$p$の倍数である．$r$が$p$と互いに素なので$r^{p-1}-1$は$p$で割り切れる．

次: 7章 上: 解答 前: 5章