%2007/04/22 06:10
%Copyright 2007 WATANABE,Masayuki
\documentclass[a4j,10pt,fleqn]{jsarticle}
\mathindent=4zw
\parindent=0zw
\topmargin=0zw
\headheight=0zw
\headsep=0zw
\oddsidemargin=0zw
\evensidemargin=0zw
\setlength{\textheight}{0.9\paperheight}
\addtolength{\textheight}{-\topskip}
\addtolength{\textheight}{-\headsep}
\addtolength{\textheight}{-\footskip}
\addtolength{\textheight}{-\topskip}
\usepackage{amsmath,amssymb,graphicx}
\pagestyle{plain}

\def\dsum{\displaystyle\sum}
\def\dlim{\displaystyle\lim}
\def\dint{\displaystyle\int}
\def\dprod{\displaystyle\prod}
\def\tvec#1{\overrightarrow{\text{#1}}}
\def\dvec#1{\overrightarrow{#1}}
\def\MARU#1{{\ooalign{\hfil#1\/\hfil\crcr\raise.167ex\hbox{\mathhexbox20D}}}}
\begin{document}
{\large 京都大学　1997年　入学試験　前期理系数学　問題2}\\
\\
{\large 問題}\\
\\
　$n$が相異なる素数$p$，$q$の積，$n=pq$ ，であるとき，$(n-1)$個の数 ${}_n\mathrm{C}_k\;(1\leqq k\leqq n-1)$ の最大公約数は1であることを示せ．\\
\\
{\large 解答}\\
\\
$$t_k={}_n\mathrm{C}_k=\frac{n!}{k!(n-k)!}$$
とおく\\
$k=1$の時\\
$$t_1=\frac{n!}{1!(n-1)!}=n$$
$k=n-1$の時\\
$$t_{n-1}=\frac{n!}{(n-1)!(n-n+1)!}=n$$
$n$は素数$p,q$の積なので$n$の約数は$n,p,q,1$\\
したがって、$t_k$の最大公約数は$n,p,q,1$のいずれかである。\\
$$t_p=\frac{n!}{p!(n-p)!}=\frac{n(n-1)\cdots(n-p+1)}{p!}$$
$n$は$pq$なので$n$より小さい最大の$p$の倍数は$p(q-1)=pq-p=n-p$
したがって、
$n$から始まって連続する$p$個の積$n(n-1)\cdots(n-p+1)$の中には
$p$の倍数は$n$のみしか存在しない。\\
また$n$の約数には$p$は１個のみ含まれる。\\
しかし$p!$には当然$p$が１個含まれるので\\
$$t_p=\frac{n(n-1)\cdots(n-p+1)}{p!}$$
は$p$で割り切れない\\
同様に
$$t_q=\frac{n(n-1)\cdots(n-q+1)}{q!}$$
は$q$で割り切れない\\
$t_k$の最大公約数は$t_1,t_p,t_q$の約数なので\\
$(t_1,t_p,t_q)$の約数\\
$t_p$は$t_1$の約数$n,p,q,1$のうち$n,p$を含まない\\
同様に
$t_q$は$t_1$の約数$n,p,q,1$のうち$n,q$を含まない\\
したがって$t_1,t_p,t_q$に共通に含まれる約数は$1$のみ\\
つまり$(t_1,t_p,t_q)=1$\\
よって$t_k$の最大公約数は$1$
\end{document}
