Question

For all m, n positive integers, with \(n \leq m\) prove \(\dfrac{gcd(m,n)}{m}\left(\begin{matrix}m\\n\end{matrix}right)\in \mathbb Z\)
PLease, help

Answer 1

\(\dfrac{gcd(m, n)}{m}\left(\begin{matrix}m\\n\end{matrix}\right)\) \(\in \mathbb Z\)

Answer 2

hint
\[\large \left(\begin{matrix}m\\n\end{matrix}\right) = \frac{m!}{n!(m-n)!}\]

\[\large \left(\begin{matrix}m\\n\end{matrix}\right) = \frac{m*(m-1)!}{n!(m-n)!}\]

Answer 3

the whole combination is an integer, when we expand and cancel m with the m on the first element, what guarantee that the whole number is integer?

Answer 4

I meant : \(\dfrac{gcd(m,n)}{\cancel m}\dfrac{\cancel {m}(m-1)!}{n! (m-n)!}\)

Answer 5

then \(\dfrac{gcd(m, n)(m-1)! }{n!(m-n)!}\) must be an integer. But I don't know how to prove it.

Answer 6

Since \(n\leq m\) we can cancel (m-n)! also, then it becomes
\(\dfrac{gcd(m,n) (m-1) (m-2)*\cdots *(m-n+1)}{n!}\)

Answer 7

looks good

so we just have to show that n! is a factor of the numerator somehow

Answer 8

n <= m

so I'd think that n! = n*(n-1)*...*3*2*1 has factors that go into (m-1)*(m-2)*...*(m-n+1) somehow

Answer 9

your paper says "hint: linear combination" but idk how to go that route

I'm guessing maybe GCD(m,n) = mx + ny and use that in some way

Answer 10

Yes, I am thinking of it. :)

Answer 11

not to butt in , but yes, that is what you are going to use

Answer 12

Maybe like this?


\[\large \frac{gcd(m, n)}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)=\frac{mx+ny}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)\]

\[\large \frac{gcd(m, n)}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)=\left(\frac{mx}{m}+\frac{ny}{m}\right)*\left(\begin{matrix}m\\n\end{matrix}\right)\]

\[\large \frac{gcd(m, n)}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)=\left(x+\frac{ny}{m}\right)*\left(\begin{matrix}m\\n\end{matrix}\right)\]

\[\large \frac{gcd(m, n)}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)=x*\left(\begin{matrix}m\\n\end{matrix}\right)+\frac{ny}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)\]

\[\large \frac{gcd(m, n)}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)=x*\left(\begin{matrix}m\\n\end{matrix}\right)+\frac{ny}{m}*\frac{m!}{n!(m-n)!}\]

\[\large \frac{gcd(m, n)}{m}*\left(\begin{matrix}m\\n\end{matrix}\right)=x*\left(\begin{matrix}m\\n\end{matrix}\right)+\frac{ny}{m}*\frac{m*(m-1)!}{n!(m-n)!}\]

Answer 13

that n! is still an issue though, hmm

Answer 14

\(gcd=xm+yn\)

Answer 15

so \(\frac{gdc}{m}=x+\frac{yn}{m}\)

Answer 16

\[x\binom{m}{n}\] is an integer for sure
you need \[\frac{yn}{m}\binom{m}{n}\]is an integer

Answer 17

which i think is more or less obvious unless i screwed up somewhere
i mean the last part is obvious

Answer 18

lol sorry, it is the same thing @jim_thompson5910 wrote !!

Answer 19

:)

Answer 20

oh but there is no problem with it being an integer right?

Answer 21

@ganeshie8 then?

Answer 22

ofcourse we're using the fact that the binomial coefficient is an integer

Answer 23

how? it is \(\dfrac{1}{m'}\) and how it is an integer? unless m' = 1 but then it back to case 1.

Answer 24

One more thing, if binomial coefficient does nothing there, so, why is it there?

Answer 25

i think i see the issue, and i think i see how to fix it

Answer 26

i think

Answer 27

the issue is showing that \[\frac{yn}{m}\binom{m}{n}\] is an integer right?

Answer 28

yup

Answer 29

For a prime, \(p\), you must be knowing that \(p\mid \dbinom{p}{k}\) for \(0\le k\le p-1\), yes ?

Answer 30

i will let @ganeshie8 finish, then i think i can show that \[\frac{yn}{m}\binom{m}{n}\] is an integer

Answer 31

@ganeshie8 then?

Answer 32

here i am tired

Answer 33

\[\frac{n}{m}\binom{m}{n}=\frac{(m-1)!}{(n-1)!(m-n)!}=\binom{m-1}{n}\]

Answer 34

yeah please go with that
i can't find easy justification for case 2

Answer 35

i am deleting it as it has few errors..

Answer 36

\[\frac{n}{m}\binom{m}{n}=\frac{(m-1)!}{(n-1)!(m-n)!}=\binom{m-1}{\color{red}{n-1}}\]

Answer 37

I am tired also. But still not see how it is right
the first term: \(\dfrac{n}{m }\dfrac{m(m-1)! }{(m-n)! n(n-1)!}=\dfrac{(m-1)!}{(n-1)!(m-n)!}\)
to get the middle term. I am ok with that
but the last term: \(\dfrac{(m-1)!}{(m-n-1)! n!}=\dfrac{(m-1)! }{(m-n-1)! n!}\) which is not the middle term.

Answer 38

oh, you correct @satelite73 stuff. and it makes sense now. Thank you so much.