WisFaq!

Delers van een faculteit

Bereken de kleinste waarde van n waarvoor n! deelbaar is door 2002.

Hiervoor ontbind ik 2002 in factoren, en stel dit gelijk aan de uitgeschreven vorm van n!. Vervolgens schrap ik wat, maar dan blijf ik zitten met de factoren uit n! die geen delers zijn van 2002.

Kan iemand me aub helpen door een algemene en gestructureerde methode te geven? Op deze manier is het namelijk maar wat 'geprobeer'.

Alvast bedankt!

Brent
4-6-2008

Antwoord

Je begint goed door 2002 te ontbinden in factoren. Maar waarom zou je dat willen gelijkstellen aan n! ? 2002 moet n! delen, niet eraan gelijk zijn! De oplossing is dus: 2002 = 2·7·11·13, en aangezien 13 priem is, moet zeker al n = 13 (anders zou 13 wel 2002 delen, maar niet n!). Voor n = 13 vinden we 13! = 2·7·11·13·iets en dus is 13! deelbaar door 2002.

Wat betreft je "algemene methode": natuurlijk kan je een echte methodiek geven om zo'n problemen op te lossen, maar het zal altijd wat lijken op hetgeen hierboven staat. Merk hierbij wel op dat 2002 een eenvoudig getal is: alle priemexponenten zijn 1. Stel bijvoorbeeld dat je 2002 vervangt door 16. Dan moet n! minstens 4 factoren 2 bevatten. We overlopen de even getallen: 2 geeft 1 factor, 4 geeft 2 factoren (dus in totaal 3), 6 geeft 1 factoren (dus in totaal 4), en dus is n = 6.

Als je echt een algemene aanpak wil, dan definieer je bijvoorbeeld best de p-orde van een natuurlijk getal n: dit is de hoogste macht van p die n deelt. Zo is ord₂(12) = ord₂(2²·3) = 2. Met deze notatie vind je dus dat a = Õ p^ord_p(a), waarbij dit product wordt genomen over alle priemgetallen p. Nu is natuurlijk ord_p(n!) = å₁ⁿ ord_p(n). Opdat n! deelbaar zou zijn door a, moet dus ord_p(a) å₁ⁿ ord_p(n) voor alle priemgetallen p. Voor elke p die a deelt (voor alle priemen die a niet delen, is de p-orde van a gelijk aan 0 en is dus steeds aan de ongelijkheid voldaan), ga je een n groot genoeg nemen zodat aan de ongelijkheid voldaan is. (Dit is eigenlijk precies wat we daarnet deden voor de deelbaarheid door 16: we moesten genoeg factoren 2 hebben, en dus gingen we n groot genoeg zoeken zodat de som van de 2-ordes groter werd dan 4.) Neem dan het maximum van al die n'etjes (voor alle p's doe je dit!) en dat maximum is het minimum dat we zoeken!

cd
5-6-2008