[getaltheorie] modulorekenen

Moderators: dirkwb, Xilvo

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

Bericht 30-11-'08, 17:49

Klintersaas

Berichten: 8.614

[getaltheorie] modulorekenen

Ik ben geïnteresseerd geraakt in de getaltheorie en verdiep me momenteel in het modulorekenen. Ik ben reeds vertrouwd met de basisbegrippen en -rekenregels, dus wilde ik me aan enkele opgaven wagen. De meeste waren van de strekking "Bepaal de rest bij deling door ... van ...". Over het algemeen gingen die opgaven erg goed, maar toen stootte ik op het volgende prachtexemplaar:

Vind
\(\forall\ n \in \nn\)
de resten van
\(\frac{(7n)!}{7^n \cdot (n!)}\)
na deling door 7.[/i] (VWO 2005 / Finale vraag 1)

Mijn oplossing: (of beter: poging tot oplossing)

We werken dus in het veld (voor de Nederlanders onder ons: het lichaam)
\(\zz / 7\zz\)
, aangezien 7 een priemgetal is.

Ik redeneerde als volgt:
  • \(7^n\)
    is steeds een veelvoud van 7 (behalve wanneer n=0), dus valt weg aangezien we modulo 7 werken;
  • Uit
    \((7n)!\)
    valt de 7 steeds weg aangezien we modulo 7 werken.
    \((7n)!\)
    wordt dus herleid naar
    \(n!\)
    .
We krijgen
\(\forall\ n \in \nn\)
iets van de vorm
\(\frac{n!}{n!} = 1\)
. De rest is dus steeds 1.

Klopt dit antwoord en trekt de redenering ergens op?
Geloof niet alles wat je leest.


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

Bericht 30-11-'08, 18:17

Safe

Gebruikersavatar
Pluimdrager
Berichten: 10.058

Re: [getaltheorie] modulorekenen

Wat krijg je voor n=1?
Omhoog

Bericht 30-11-'08, 18:55

Klintersaas

Berichten: 8.614

Re: [getaltheorie] modulorekenen

\(\frac{(7 \cdot 1)!}{7^1 \cdot (1!)} = \frac{7!}{7 \cdot 1} = 6! = 720\)
en
\(720 \equiv 6 \pmod{7}\)
Wat ik zei klopt dus toch niet.

Voor n=2 klopt het wel, maar dat zegt natuurlijk niets:
\(\frac{(7 \cdot 2)!}{7^2 \cdot (2!)} = \frac{14!}{49 \cdot 2} = 889574400\)
en
\(889574400 \equiv 1 \pmod{7}\)
Geloof niet alles wat je leest.


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

Bericht 30-11-'08, 19:49

Klintersaas

Berichten: 8.614

Re: [getaltheorie] modulorekenen

Even snel een programmaatje geschreven:
  • Voor n=1 is de rest 6;
  • Voor n=2 is de rest 1;
  • Voor n=3 is de rest 6;
  • Voor n=4 is de rest 0;
  • Voor n=5 is de rest 0;
  • Voor n=6 is de rest 0;
  • Voor n=7 is de rest 0;
  • Voor n=8 is de rest 0;
  • ...
Maar nu wil ik uiteraard een wiskundige verantwoording. Kan iemand me op weg helpen?
Geloof niet alles wat je leest.


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

Bericht 30-11-'08, 20:51

Burgie

Berichten: 582

Re: [getaltheorie] modulorekenen

Leuk, een doordenkertje!

Schrijf eens voor een aantal waarden van n bovenstaande formule uit... bvb. n = 1, 2 en 3. Je zal merken dat de noemer
\( 7^n \cdot n! \)
ervoor zorgt dat alle veelvouden van 7 uit de teller 'weggefilterd' worden. Eenmaal je dit weet en kan aantonen (!!!), wordt het een stuk eenvoudiger. Dit laat ik even aan jou over :D .

Als ik me niet vergis zal je uiteindelijk kunnen aantonen dat
\(\frac{(7n)!}{7^n \cdot (n!)}\)
mod
\(7\)
equivalent is met
\(6^n\)
mod
\(7\)
.

EDIT: Ik denk overigens dat jouw waarden hierboven niet kloppen. Ik vind 6 voor alle oneven waarden van n en 1 voor alle even waarden van n.
Omhoog

Bericht 01-12-'08, 17:14

Safe

Gebruikersavatar
Pluimdrager
Berichten: 10.058

Re: [getaltheorie] modulorekenen

Burgie schreef:Leuk, een doordenkertje!

Schrijf eens voor een aantal waarden van n bovenstaande formule uit... bvb. n = 1, 2 en 3. Je zal merken dat de noemer
\( 7^n \cdot n! \)
ervoor zorgt dat alle veelvouden van 7 uit de teller 'weggefilterd' worden. Eenmaal je dit weet en kan aantonen (!!!), wordt het een stuk eenvoudiger. Dit laat ik even aan jou over :D .

Als ik me niet vergis zal je uiteindelijk kunnen aantonen dat
\(\frac{(7n)!}{7^n \cdot (n!)}\)
mod
\(7\)
equivalent is met
\(6^n\)
mod
\(7\)
.

EDIT: Ik denk overigens dat jouw waarden hierboven niet kloppen. Ik vind 6 voor alle oneven waarden van n en 1 voor alle even waarden van n.
n=1 is eenvoudig, geeft 6!=6 (mod 7)

n=2 zal ik voordoen:

Teller: 6!(7*1)*8*...*13*(7*2)

Noemer: 7²*2! (let hierbij op de haakjes in de teller: hier wees Burgie op)

Na deling: 6!(14-6)(14-2)...(14-1)=6!6! (mod 7) (waarom?)=6*6 (mod 7)=1 (mod 7)

jij verder.
Omhoog

Bericht 02-12-'08, 22:12

Klintersaas

Berichten: 8.614

Re: [getaltheorie] modulorekenen

EDIT: Ik denk overigens dat jouw waarden hierboven niet kloppen. Ik vind 6 voor alle oneven waarden van n en 1 voor alle even waarden van n.
Inderdaad, ik heb het foutje al gevonden.
Na deling: 6!(14-6)(14-2)...(14-1)=6!6! (mod 7) (waarom?)=6*6 (mod 7)=1 (mod 7)
Ik zie niet onmiddellijk hoe je die deling uitvoert. Daarna valt de 14 weg vanwege de mod 7 en vormt wat overblijft een tweede keer 6! Verder is het inderdaad eenvoudig.
Geloof niet alles wat je leest.


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

Bericht 02-12-'08, 23:23

Burgie

Berichten: 582

Re: [getaltheorie] modulorekenen

Ik zie niet onmiddellijk hoe je die deling uitvoert.
Heel eenvoudig schrijf voor het geval n=2 alles eens uit.

Teller:
\(14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot 7 \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\)
=
\(\left( 7 \cdot 2 \right) \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8 \cdot \left( 7 \right) \cdot 6 \cdot 5 \cdot 4 \cdot 3 \cdot 2 \cdot 1\)
.

Noemer:
\( 7^2 \cdot 2! \)
=
\( \left( 7 \cdot 2 \right) \cdot \left( 7 \right) \)
.

Wat valt er weg? Dat is trouwens precies wat ik bedoelde toen ik vermeldde dat de noemer ervoor zorgt dat alle veelvouden van 7 uit de teller 'weggefilterd' worden.
Omhoog

Bericht 03-12-'08, 11:53

Klintersaas

Berichten: 8.614

Re: [getaltheorie] modulorekenen

Natuurlijk! Bedankt, ik ben eruit.
Geloof niet alles wat je leest.


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

Bericht 05-01-'11, 12:51

SjorsGC

Berichten: 16

Re: [getaltheorie] modulorekenen

Hoi, ik wilde deze opgave (of een soort gelijke opgave) graag gebruiken voor een PO modulo rekenen.

Weet iemand misschien waar deze opdracht vandaan komt of heeft iemand redelijk ingewikkeld opdrachten (6 VWO-niveau) over modulo rekenen.

Alvast bedankt!

Marijke
Omhoog

Bericht 05-01-'11, 18:23

tuure

Berichten: 11

Re: [getaltheorie] modulorekenen

SjorsGC schreef:Hoi, ik wilde deze opgave (of een soort gelijke opgave) graag gebruiken voor een PO modulo rekenen.

Weet iemand misschien waar deze opdracht vandaan komt of heeft iemand redelijk ingewikkeld opdrachten (6 VWO-niveau) over modulo rekenen.

Alvast bedankt!

Marijke
Deze vraag komt van de Vlaamse Wiskunde Olympiade (VWO; dus niet voorbereidend wetenschappelijk onderwijs zoals in Nederland). De vragen zijn te vinden op http://www.vwo.be/vwo/vorige-edities/alle-vragen , maar enkel de vragen van de 1e en 2e ronde. De vraag van dit topic is dus niet te vinden aangezien die uit de finale kwam.
Omhoog
Reageer

Terug naar “Wiskunde”