Het bepalen van de rest bij deling door ... van ...

[Klintersaas]

In de Vlaamse Wiskunde-Olympiade komen dikwijls vragen terug in de aard van "bepaal de rest bij deling door ... van ...", waarbij op de plaats van het eerste beletselteken normaliter een reusachtig getal staat. Een eenvoudige manier om dergelijke vragen op te lossen is bijna steeds het gebruik van modulorekening. Hoewel me dit bij eenvoudige opgaven wel lukt, heb ik moeite om hetzelfde principe van modulorekening toe te passen op de vragen gesteld in de VWO.

In deze topic had ik graag een aantal van die opgaven doorgenomen om tot een (algemene) oplossingsstrategie voor dergelijke problemen aan te leren. Om te beginnen:

De rest van de deling van

\((1! + 2! + 3! + 4! + 5! + 6! + 7! + 8! + 9!)^2\)

door 5 is:

1. 0
2. 1
3. 2
4. 3
5. 4

(Vlaamse Wiskunde Olympiade 2003, tweede ronde, vraag 20)[/i]

Ik kan dit uiteraard vlug uitrekenen om het antwoord te vinden, maar dat is vanzelfsprekend niet de bedoeling. Ik zoek een eenvoudige, korte, elegante manier om de oplossing te vinden en hoop dat jullie me daarbij kunnen helpen.

Zelf heb ik helaas nog niet zoveel kunnen proberen, omdat ik niet zo onderlegd ben in de modulorekening en enkel de basisprincipes ken.

[stoker]

je bent hier meer met de eigenschappen van faculteiten dan met modulorekenen lijkt me.

alle faculteiten groter dan 4! zijn deelbaar door 5, die kan je dus als het ware schrappen. Maar hier staat er nog een kwadraat bij.

neem dus iets van de vorm (met b deelbaar door 5 ) :

\((a+b)^2=a^2+2ab+b^2 \rightarrow a^2\)

want 2ab en b² zijn deelbaar door 5.

reken a explicitiet uit ...

dan kom ik rest 4 uit

[Klintersaas]

je bent hier meer met de eigenschappen van faculteiten dan met modulorekenen lijkt me.

alle faculteiten groter dan 4! zijn deelbaar door 5, die kan je dus als het ware schrappen.

Daar had ik aan moeten denken, bedankt.

Maar hier staat er nog een kwadraat bij.

neem dus iets van de vorm (met b deelbaar door 5 ) :

\((a+b)^2=a^2+2ab+b^2 \rightarrow a^2\)

dan kom ik rest 4 uit

Dat bekwam ik ook (eerst door alles even vlug uit te rekenen, vervolgens ook na het schrappen van alle faculteiten groter dan 4!), dus dat lijkt me juist.

Maar goed, eigenlijk doet deze opgave dus niet echt ter zake. Ik zal er een andere zoeken.

[stoker]

Ik vrees dat ik je hier niet goed begrijp.

Als je de termen groter dan 4! binnen het kwadraat zomaar schrapt, is het nogal kort door de bocht vind ik. Uiteindelijk klopt het wel dat je die zomaar mag schrappen. Dat heb ik in die stap dus min of meer aangetoond. Maar zó logisch is dat niet.

[eendavid]

Ik vrees dat ik je hier niet goed begrijp.

Hij bedoelt dat

\(a^2\mod 5 = (a\mod 5)^2\mod 5\)

[Klintersaas]

Bedankt.

Tweede poging:

Als we 1991! delen door 1992, dan geldt voor de rest r:

1. \(r = 0\)
2. \(1 \leq r \leq 191\)
3. \(191 \leq r \leq 591\)
4. \(591 \leq r \leq 1291\)
5. \(1291 \leq r \leq 1991\)

[/i]Mijn excuses mocht dit opnieuw geen geschikte opgave zijn.

[EvilBro]

(Dit is nog een bijdrage gerelateerd aan de eerste vraag.)

\((5\cdot m + r)^2 = 5 \cdot 5 \cdot m^2 + 2 \cdot 5 \cdot m \cdot r + r^2 = 5 \cdot (5 \cdot m + 2 \cdot m \cdot r) + r^2 = r^2 \mod 5\)

voor de tweede vraag:

\(2 \cdot 996 = 1992\)

[stoker]

die tweede is ook niet gebaseerd op modulorekenen (en dat ligt volgens mij niet in het leerplan voor het middelbaar in Vlaanderen, dus vind je dan wel echt mod-vragen in een vwo?)

1992=1.2.3.4.83

1991!=1.2.3.4. ... .83. ... .1991

dus rest nul, wat niet raar is, als je zo'n gigantisch getal door zo'n klein getal deelt.

[Klintersaas]

(Dit is nog een bijdrage gerelateerd aan de eerste vraag.)

\((5\cdot m + r)^2 = 5 \cdot 5 \cdot m^2 + 2 \cdot 5 \cdot m \cdot r + r^2 = 5 \cdot (5 \cdot m + 2 \cdot m \cdot r) + r^2 = r^2 \mod 5\)

die tweede is ook niet gebaseerd op modulorekenen (en dat ligt volgens mij niet in het leerplan voor het middelbaar in Vlaanderen, dus vind je dan wel echt mod-vragen in een vwo?)

Dat is toch wat ik me heb laten wijsmaken, en blijkbaar zit in deze vragen toch een kern van modulorekening.

voor de tweede vraag:

\(2 \cdot 996 = 1992\)

1992=1.2.3.4.83

1991!=1.2.3.4. ... .83. ... .1991

dus rest nul, wat niet raar is, als je zo'n gigantisch getal door zo'n klein getal deelt.

Zo ver was ik ook al gekomen, maar mijn frank was niet gevallen. Nogmaals bedankt allebei en ik laat dit maar even rusten.

[EvilBro]

..., wat niet raar is, als je zo'n gigantisch getal door zo'n klein getal deelt.

\(10^{1525}\)

(=gigantisch getal) gedeeld door 3?

[Drieske]

Hey, bij vraag 1, is het niet simpelder te berekenen, maar mss mag wat iik doe niet zomaar?

Ik dacht dat er geldde: (a+b) mod n = (a mod n + b mod n) mod n

en

c² mod m = (c mod m)²

Deze 2 combineren levert mij ook wel rest 4... mar lijkt wel iets rapper geteld

[thermo1945]

5! en elke grotere term is deelbaar door 5 en dus rest nul.

De vraag beperkt zich dus tot

wat is de als je 1! + 2! + 3! + 4! deelt door 5?

1! + 2! + 3! + 4! = 33.

33 : 5 = 6 rest 3

33 = 6 x 5 + 3

33² = 30² = 2 x 3 x 30 + 3² = vijfvoud + 4

De gevraagde rest is dan 4.

[kotje]

Bedankt.

Tweede poging:

Als we 1991! delen door 1992, dan geldt voor de rest r:

1. \(r = 0\)
2. \(1 \leq r \leq 191\)
3. \(191 \leq r \leq 591\)
4. \(591 \leq r \leq 1291\)
5. \(1291 \leq r \leq 1991\)

[/i]Mijn excuses mocht dit opnieuw geen geschikte opgave zijn.

Als axb (mod m)=(a (mod m)x(b (mod m)) (mod m) dan kies ik voor A.

[EvilBro]

Als axb (mod m)=(a (mod m)x(b (mod m)) (mod m) dan kies ik voor A.

Zou je kunnen voordoen hoe je deze regel wilt toepassen op dit vraagstuk?

[kotje]

1991!=1.2.3...1991.

Mod 1992 van al de factoren is 0; hiervan mod 1992 is 0 dus r=0.