NTice
Opgave - Putnam 2000 dag 2 vraag 2
Bewijs dat $\frac{\text{ggd}(m, n)}{n}{n\choose m}$ geheel is $\forall m,n \in \mathbb{N}$ als $n \ge m>0.$
- login om te reageren
Olympia
Nederlandstalig olympiadeproject
Zoeken
Random generator
Niveau
Wie is online
Er zijn momenteel 0 gebruikers en 1 gast online.
Oplossing
Volgens de stelling van Bézout-Bachet bestaan er gehele getallen $a$ en $b$ zodanig dat $\text{ggd}(m,n)=an+bm$. Dit invullen in de vergelijking geeft:
\begin{align*}
\frac{\text{ggd}(m,n)}{n}\binom{n}{m}
&=\frac{an+bm}{n}\binom{n}{m}=a\binom{n}{m}+b\frac{m}{n}\binom{n}{m}=a\binom{n}{m}+b\binom{n-1}{m-1}\\
\end{align*}
En dit getal is duidelijk geheel.
Volgens de stelling van Bachet-Bézout, bestaan er $\alpha, \beta \in \mathbb{Z}$ zodat $\text{ggd}(m,n)=\alpha m + \beta n$.
Nu is
\begin{align*}
\frac{\text{ggd}(m,n)}{n}\binom{n}{m}&=\frac{\alpha m + \beta n}{n}\binom{n}{m} \\
&=\frac{\alpha m}{n}\binom{n}{m} + \frac{\beta n}{n}\binom{n}{m} \\
&=\frac{\alpha m}{n}\cdot \frac{n!}{m!(n-m)!} + \beta\binom{n}{m}
\\
&=\frac{\alpha(n-1)!}{(m-1)!(n-m)!}+\beta\binom{n}{m}
\\
&=\alpha\binom{n-1}{m-1}+\beta\binom{n}{m}
\end{align*}
Dit is duidelijk een geheel getal, want het product en de som van gehele getallen is ook geheel, dit bewijst het gevraagde.