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

Moderators: dirkwb, Xilvo

Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
Reageer

Bericht 03-03-'09, 19:19

Klintersaas

Berichten: 8.614

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

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.
Geloof niet alles wat je leest.


Heb jij verstand van PHP? Word Technicus en help mee om Wetenschapsforum nog beter te maken!
Omhoog

Bericht 03-03-'09, 19:32

stoker

Berichten: 2.746

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

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
Omhoog

Bericht 03-03-'09, 19:38

Klintersaas

Berichten: 8.614

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

stoker schreef: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.
stoker schreef: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.
Geloof niet alles wat je leest.


Heb jij verstand van PHP? Word Technicus en help mee om Wetenschapsforum nog beter te maken!
Omhoog

Bericht 03-03-'09, 19:45

stoker

Berichten: 2.746

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

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.
Omhoog

Bericht 03-03-'09, 19:53

eendavid

Gebruikersavatar
Berichten: 3.751

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

Ik vrees dat ik je hier niet goed begrijp.
Hij bedoelt dat
\(a^2\mod 5 = (a\mod 5)^2\mod 5\)
Omhoog

Bericht 03-03-'09, 19:59

Klintersaas

Berichten: 8.614

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

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.
Geloof niet alles wat je leest.


Heb jij verstand van PHP? Word Technicus en help mee om Wetenschapsforum nog beter te maken!
Omhoog

Bericht 03-03-'09, 20:00

EvilBro

Berichten: 7.068

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

(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\)
Omhoog

Bericht 03-03-'09, 20:08

stoker

Berichten: 2.746

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

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.
Omhoog

Bericht 03-03-'09, 20:15

Klintersaas

Berichten: 8.614

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

EvilBro schreef:(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.
EvilBro schreef: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.
Geloof niet alles wat je leest.


Heb jij verstand van PHP? Word Technicus en help mee om Wetenschapsforum nog beter te maken!
Omhoog

Bericht 03-03-'09, 20:16

EvilBro

Berichten: 7.068

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

..., wat niet raar is, als je zo'n gigantisch getal door zo'n klein getal deelt.
\(10^{1525}\)
(=gigantisch getal) gedeeld door 3? :D
Omhoog

Bericht 03-03-'09, 20:37

Drieske

Gebruikersavatar
Berichten: 10.179

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

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 :D
Zoek je graag naar het meest interessante wetenschapsnieuws? Wij zoeken nog een vrijwilliger voor ons nieuwspostteam.
Omhoog

Bericht 03-03-'09, 21:28

thermo1945

Gebruikersavatar
Berichten: 3.112

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

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

332 = 302 = 2 x 3 x 30 + 32 = vijfvoud + 4

De gevraagde rest is dan 4.
Omhoog

Bericht 03-03-'09, 21:42

kotje

Gebruikersavatar
Berichten: 3.330

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

Klintersaas schreef: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.
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
Omhoog

Bericht 03-03-'09, 21:49

EvilBro

Berichten: 7.068

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

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?
Omhoog

Bericht 04-03-'09, 08:09

kotje

Gebruikersavatar
Berichten: 3.330

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

1991!=1.2.3...1991.

Mod 1992 van al de factoren is 0; hiervan mod 1992 is 0 dus r=0.
Volgens mijn verstand kan er niets bestaan en toch bestaat dit alles?
Omhoog
Reageer

Terug naar “Wiskunde”