【2021奈良県立医科大学・後期】
正整数 \(a\)、\(b\) の最大公約数を \(( a , b )\) で表す.
(1) 任意の正整数 \(m\)、\(n\) に対して、等式
\(( m+n , n ) = ( m , n )\) が成り立つことを証明せよ.
(2) 互いに素な正整数 \(m\)、\(n\) に対して、\((m+n-1)!\) は \(m!n!\) によって割り切れることを証明せよ.
ユークリッド互除法の利用
【ユークリッドの互除法】
\(2\) つの自然数 \(a\) 、\(b\) において、\(a\) を \(b\) で割ったときの商を \(q\)、余りを \(r\) とすると
\(a\) と \(b\) の最大公約数は、\(b\) と \(r\) の最大公約数に等しい
つまり、\(( a , b ) = ( b , r )\)
(1)解答
\(m+n=1\times n+m\) より、ユークリッドの互除法から
\(m+n\) と \(n\) の最大公約数は、\(n\) と \(m\) の最大公約数に等しい.
よって、\(( m+n , n ) = ( m , n )\) が成り立つ
(1)別解
\((m+n,n)=d_{1}\) ,\((m,n)=d_{2}\) とおく.
整数 \(k_{1}\) ,\(l_{1}\) を用いて、
\(\begin{cases}m+n=k_{1}d_{1}\\n=l_{1}d_{1}\end{cases}\) とおける.
\(\iff\) \(\begin{cases}m=(k_{1}-l_{1})d_{1}\\n=l_{1}d_{1}\end{cases}\) であるから,
\(d_{1}\) は \(m\) と \(n\) の公約数であり,\(d_{1}≦d_{2}\) ・・・①
次に、整数 \(k_{2}\) ,\(l_{2}\) を用いて、
\(\begin{cases}m=k_{2}d_{2}\\n=l_{2}d_{2}\end{cases}\) とおける.
\(\iff\) \(\begin{cases}m+n=(k_{2}+l_{2})d_{2}\\n=l_{2}d_{2}\end{cases}\) であるから,
\(d_{2}\) は \(m+n\) と \(n\) の公約数であり,\(d_{2}≦d_{1}\) ・・・②
①,②より,\(d_{1}=d_{2}\) が成り立つ.
\(_{n}C_{r}\):二項係数
(2)解答
\(_{m+n}C_{n}=\displaystyle\frac{(m+n)!}{n!m!}\) であるから、
\(_{m+n}C_{n}=\displaystyle\frac{m+n}{n}\cdot \displaystyle\frac{(m+n-1)!}{(n-1)!m!}=\displaystyle\frac{m+n}{n}\cdot _{m+n-1}C_{n-1}\)
よって、\(n\cdot _{m+n}C_{n}=(m+n)_{m+n-1}C_{n-1}\) ・・・③
条件より \(m\) ,\(n\) は互いに素であり,また(1)の結果から,
\(m+n\) と \(n\) は互いに素であるから,③より \(_{m+n}C_{n}\) は \(m+n\) の倍数である.
したがって,
\(\displaystyle\frac{_{m+n}C_{n}}{m+n}=\displaystyle\frac{(m+n-1)!}{n!m!}\)
は整数となる.ゆえに,\((m+n-1)!\) は \(m!n!\) によって割り切れる.
コメント