Delelighet
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
Påstand: k etterfølgende hele positive tall er alltid delelig på k!
(1) [tex]1! \ | \ n[/tex]
Vi ser at det er sant for s=1, da et tall alltid er delelig på 1.
(2) Anta det er sant for [tex]s \leq k. \Rightarrow s! \ | \ n(n+1)(n+2) \cdot ... \cdot (n+s-1)[/tex].
Anta at ingen av faktorene er delelig på s+1. Siden det er s etterfølgende tall, må de i rekkefølge være kongruent med [tex]1,2,3,...,s[/tex] modulo [tex]s+1[/tex]. Da må et påfølgende tall nødvendigvis være kongruent med [tex]0[/tex] modulo [tex]s+1[/tex]. Det betyr at [tex](s+1)! | n(n+1)(n+2) \cdot ... \cdot (n+s-1)(n+s)[/tex]
Hvis derimot ét av tallene er delelig på [tex]s+1[/tex], må tallene være kongruent med [tex]p, p+1,...,s,s+1,s+2,...,p+s[/tex] modulo [tex]s+1[/tex] for et heltall [tex]p[/tex]. Som igjen er kongruent med [tex]p,p+1,...,s,s+1,...,p+s-1,p-2[/tex] modulo [tex]s+1[/tex]. Det påfølgende tallet [tex]p+s[/tex] er kongruent med [tex]p-1[/tex] modulo [tex]s+1[/tex], og vi har da [tex]s+1[/tex] tall med forskjellige rest i modulo [tex]s+1[/tex], og da må nødvendigvis [tex](s+1)! \ | \ n(n+1)(n+2) \cdot ... \cdot (n+s-1)(n+s)[/tex]
(1) [tex]1! \ | \ n[/tex]
Vi ser at det er sant for s=1, da et tall alltid er delelig på 1.
(2) Anta det er sant for [tex]s \leq k. \Rightarrow s! \ | \ n(n+1)(n+2) \cdot ... \cdot (n+s-1)[/tex].
Anta at ingen av faktorene er delelig på s+1. Siden det er s etterfølgende tall, må de i rekkefølge være kongruent med [tex]1,2,3,...,s[/tex] modulo [tex]s+1[/tex]. Da må et påfølgende tall nødvendigvis være kongruent med [tex]0[/tex] modulo [tex]s+1[/tex]. Det betyr at [tex](s+1)! | n(n+1)(n+2) \cdot ... \cdot (n+s-1)(n+s)[/tex]
Hvis derimot ét av tallene er delelig på [tex]s+1[/tex], må tallene være kongruent med [tex]p, p+1,...,s,s+1,s+2,...,p+s[/tex] modulo [tex]s+1[/tex] for et heltall [tex]p[/tex]. Som igjen er kongruent med [tex]p,p+1,...,s,s+1,...,p+s-1,p-2[/tex] modulo [tex]s+1[/tex]. Det påfølgende tallet [tex]p+s[/tex] er kongruent med [tex]p-1[/tex] modulo [tex]s+1[/tex], og vi har da [tex]s+1[/tex] tall med forskjellige rest i modulo [tex]s+1[/tex], og da må nødvendigvis [tex](s+1)! \ | \ n(n+1)(n+2) \cdot ... \cdot (n+s-1)(n+s)[/tex]
Sist redigert av Charlatan den 08/03-2008 13:35, redigert 1 gang totalt.
Jada, flott. En annen mulighet er å observere at [tex]\frac{m(m-1)(m-2)...(m-k+1)}{k!} = {m \choose k}[/tex], og vi vet jo at binomialkoeffisienter er heltallige 
Sist redigert av daofeishi den 08/03-2008 13:33, redigert 1 gang totalt.
-
Bogfjellmo
- Cantor
- Innlegg: 142
- Registrert: 29/10-2007 22:02
Enklere:
[tex]\frac {n (n-1) (n-2) ... (n-k+1)}{k!} = {n \choose k}[/tex], et heltall.
EDIT: ninja'd
[tex]\frac {n (n-1) (n-2) ... (n-k+1)}{k!} = {n \choose k}[/tex], et heltall.
EDIT: ninja'd
