نشان دهید عبارت $\frac{gcd(m,n)}{n}{n\choose{m}} $ یک عددصحیح است.

Question

نشان دهید برای تمام اعداد صحیح $n\geq m\geq 1 $ عبارت: $$\frac{gcd(m,n)}{n}{n\choose{m}} $$ یک عدد صحیح است.( منظور از $ gcd(a,b) $ بزرگترین مقسوم علیه مشترک $a $ و $b $ است.)

Answer 1

یک روش دیگه:

بنابر آنچه erfanmدر پاسخش نوشته داریم: $$ {n\choose {m}} =\frac nm{n-1\choose m-1}$$ و اعدادصحیح $a $ و $ b $ وجود دارند به طوریکه $$ gcd(n, m)=an+bm $$ بنابراین: $$\frac{gcd(m,n)}{n}{n\choose{m}}=\frac{an+bm}{n}{n\choose m}=a{n\choose m}+b{n-1\choose m-1} $$ و چون تمام مقادیر سمت راست اعداد صحیح هستند لذا مقدار مور نظر هم عدد صحیح هستند.

Comments

خلاصه, صریح  و زیبا عالی بود !

Answer 2

میدانیم $\binom{n}{m} $ به ازای هر $ m,n $ همواره عدد صحیحی است. داریم: $$\begin{align} \binom{n}{m} = \frac{n!}{m!(n-m)!}& = \frac{n(n-1)!}{m(m-1)!((n-1)-(m-1))!} \\ &= \frac{n}{m} \binom{n-1}{m-1} \end{align} $$

اگر قرار دهیم $ n=gcd(m,n)n' $ و$ m=gcd(m,n)m' $ عبارت بالا بصورت زیر در می آید: $$ \binom{n}{m} = \frac{n}{m} \binom{n-1}{m-1} = \frac{n'}{m'} \binom{n-1}{m-1}$$ و چون $\binom{n}{m} $ عددی صحیح است لذا باید $ m' $ عبارت $ \binom{n-1}{m-1} $ را عاد کند یعنی در واقع داریم: $$ \binom{n}{m} =n'K$$ که در آن $ K$ عددی صحیح و برابر $ \frac{ \binom{n-1}{m-1} }{m'} $ است.

حال به اثبات حکم مساله بپردازیم داریم: $$\frac{gcd(m,n)}{n}{n\choose{m}} =\frac{gcd(m,n)}{n}n'K= \frac{n}{n} K=K$$لذا عبارت داده شده یک عدد صحیح بوده و مقدار آن هم برابر$ \frac{ \binom{n-1}{m-1} }{m'} $است.

برای اثبات صحیح بودن $\binom{n}{m} $ چندین روش مختلف وجود داره یکیش توجه به اینکه $\binom{n}{m} $ برابر تعداد حالت های انتخاب $ m$ شی از میان $ n $ شی است. یا با استقرا و استفاده از قاعده پاسکال هم میتوان ثابت کرد که این عبارت یک عدد صحیح است.

Comments

خیلی جالب بود.مرسی