スポンサーリンク

【2021奈良県医(後)】互いに素なm,nで、(m+n-1)!はm!n!で割り切れる証明

整数問題

【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 )\)

2000 大阪市立大学|整数問題(互いに素・ユークリッド互除法)
入試問題(整数)演習。互いに素であることの証明について、考え方、また複数の解法を紹介。

(1)解答

\(m+n=1\times n+m\) より、ユークリッドの互除法から

\(m+n\) と \(n\) の最大公約数は、\(n\) と \(m\) の最大公約数に等しい.

よって、\(( m+n , n ) = ( m , n )\) が成り立つ

ユークリッドの互除法を用いると、当たり前すぎる証明であるため、念のためにユークリッドの互除法の証明をする流れを使って別解として証明を与えておきます。

(1)別解はこれはこれで有名な解法になりますので、しっかりと身につけておきましょう!

(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}\):二項係数

\(_{n}\rm{C}_{r}= \displaystyle\frac {n!}{r!(n-r)!}\)
nCrに関する性質まとめ|二項定理・係数・組合せ
場合の数・確率の組合せで用いるCについての性質まとめ。 Cに関する公式(おさえておきたい3つの公式、二項定理など)のまとめ

(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!\) によって割り切れる.

コメント

タイトルとURLをコピーしました