Vraag m.b.t. rest bij deling
Forumregels
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
(Middelbare) school-achtige vragen naar het forum "Huiswerk en Practica" a.u.b.
Zie eerst de Huiswerkbijsluiter
-
- Berichten: 303
Vraag m.b.t. rest bij deling
Dag,
Ik vroeg mij het volgende af: bestaat er een bekende stelling in de wiskunde die zegt dat de rest van de deling van een niet-priemgetal X door een zeker getal Y gelijk is aan het product van de resten van de delingen van de delers van X door Y, op voorwaarde dat het product van deze resten zelf niet door Y deelbaar is? En, zo ja, hoe is dit te bewijzen?
Bijvoorbeeld:
156/10 (12 x 13 = 156 = X, 10 = Y) = 15 R.6
12/10 = 1 R.2 en 13/10 = 3 R.3
2 x 3 = 6
Of
81/7 (9 x 9 = 81 = X, 7 = Y) = 11 R.4
9/7 = 1 R.2
9/7 = 1 R.2
2 x 2 = 4
Of
30/4 (6 x 5 = 30 = X, 4 = Y) = 7 R.2
6/4 = 1 R.2
5/1 = 1 R.1
2 x 1 = 2
Etc.
Misschien is dit algemeen bekend onder wiskundigen (wat ik niet ben), maar ik stuitte op dit patroon bij het oplossen van een opgave uit de wiskunde-olympiade “voor de lol”.
Ik hoor graag terug van jullie, dank!
Ik vroeg mij het volgende af: bestaat er een bekende stelling in de wiskunde die zegt dat de rest van de deling van een niet-priemgetal X door een zeker getal Y gelijk is aan het product van de resten van de delingen van de delers van X door Y, op voorwaarde dat het product van deze resten zelf niet door Y deelbaar is? En, zo ja, hoe is dit te bewijzen?
Bijvoorbeeld:
156/10 (12 x 13 = 156 = X, 10 = Y) = 15 R.6
12/10 = 1 R.2 en 13/10 = 3 R.3
2 x 3 = 6
Of
81/7 (9 x 9 = 81 = X, 7 = Y) = 11 R.4
9/7 = 1 R.2
9/7 = 1 R.2
2 x 2 = 4
Of
30/4 (6 x 5 = 30 = X, 4 = Y) = 7 R.2
6/4 = 1 R.2
5/1 = 1 R.1
2 x 1 = 2
Etc.
Misschien is dit algemeen bekend onder wiskundigen (wat ik niet ben), maar ik stuitte op dit patroon bij het oplossen van een opgave uit de wiskunde-olympiade “voor de lol”.
Ik hoor graag terug van jullie, dank!
- Moderator
- Berichten: 9.994
Re: Vraag m.b.t. rest bij deling
Tegenvoorbeeld:
55 = 5 x 11
55 mod 3 = 1
5 mod 3 = 2
11 mod 3 = 2
55 = 5 x 11
55 mod 3 = 1
5 mod 3 = 2
11 mod 3 = 2
-
- Berichten: 303
Re: Vraag m.b.t. rest bij deling
Ik ben sowieso te slordig geweest, zijn paar typo’s in geslopen: 5/1 moet 5/4 zijn, etc.
Anyway, dank voor tegenvoorbeeld. Ik heb nog geen tegrnvoorbeeld gevonden als geldt dat Y > product der resten, dus als product/Y zelf niet A R.B oplevert. Jij wel?
Anyway, dank voor tegenvoorbeeld. Ik heb nog geen tegrnvoorbeeld gevonden als geldt dat Y > product der resten, dus als product/Y zelf niet A R.B oplevert. Jij wel?
Laatst gewijzigd door PhilipVoets op za 16 dec 2023, 22:36, 1 keer totaal gewijzigd.
- Moderator
- Berichten: 9.994
Re: Vraag m.b.t. rest bij deling
In ieder geval niet voor X<1.000.000 waarbij X precies twee delers heeft.PhilipVoets schreef: ↑za 16 dec 2023, 22:32 Anyway, dank voor tegenvoorbeeld. Ik heb nog geen tegrnvoorbeeld gevonden als geldt dat Y > product der resten. Jij wel?
- Moderator
- Berichten: 9.994
Re: Vraag m.b.t. rest bij deling
Ik ga er nog eens naar kijken, als anderen intussen niet al met een goed antwoord gekomen zijn.
Ik neem aan dat je bij de vorige vraag bedoelt dat de rest bij deling van X door Y groter is dan het product van de resten bij deling van de factoren van X door Y.
-
- Berichten: 303
Re: Vraag m.b.t. rest bij deling
Misschien is het handig dat ik even een opgeschoonde versie plaats i.p.v deze. Ik heb te snel e.e.a willen opschrijven en er glippen dan veel typfouten en rekenfouten in bij een leek als ik.
- Moderator
- Berichten: 9.994
Re: Vraag m.b.t. rest bij deling
Jouw idee klopt natuurlijk, al moet je het product van de resten ook weer modulo deler nemen.
\(X=A.B\)
en \(A=a+r_a\),
\(B=b+r_b\)
met \(a\) en \(b\) deelbaar door \(Y\), \(r\) de resten.
\(X=A.B=a.b+a.r_b+b.r_a+r_a.r_b\)
Alleen de laatste term is niet deelbaar door Y, de rest wordt dan \(r_X=r_a.r_b\ mod\ Y\)
In het "tegenvoorbeeld", met 5 en 11, waren de resten twee maal 2. Het product 4. Modulo deler (dat was 3) houd je 1 over.
\(X=A.B\)
en \(A=a+r_a\),
\(B=b+r_b\)
met \(a\) en \(b\) deelbaar door \(Y\), \(r\) de resten.
\(X=A.B=a.b+a.r_b+b.r_a+r_a.r_b\)
Alleen de laatste term is niet deelbaar door Y, de rest wordt dan \(r_X=r_a.r_b\ mod\ Y\)
In het "tegenvoorbeeld", met 5 en 11, waren de resten twee maal 2. Het product 4. Modulo deler (dat was 3) houd je 1 over.
-
- Berichten: 303
Re: Vraag m.b.t. rest bij deling
Precies, dat was ook een beetje waar ik wat ongelukkig in lekentermen op doelde in mijn eerdere post.
Is dit overigens een al lang bekend fenomeen in de wiskunde of “nieuw”?
Ik wilde ergens vandaag nog een opgeschoonde, meer to-the-point-formulering posten, maar je bent me al deels voor. Dank voor de kritische blik
Is dit overigens een al lang bekend fenomeen in de wiskunde of “nieuw”?
Ik wilde ergens vandaag nog een opgeschoonde, meer to-the-point-formulering posten, maar je bent me al deels voor. Dank voor de kritische blik
- Moderator
- Berichten: 9.994
Re: Vraag m.b.t. rest bij deling
Voor mensen die zich regelmatig met dit soort wiskunde (geheeltallig, modulo) bezighouden is dit zonder twijfel gesneden koek.PhilipVoets schreef: ↑zo 17 dec 2023, 09:25 Is dit overigens een al lang bekend fenomeen in de wiskunde of “nieuw”?
-
- Berichten: 303
Re: Vraag m.b.t. rest bij deling
Het is inderdaad niet denderend complex, maar ik kon het nergens terugvinden, misschien gemist, haha? Iemand die dit al “kent” als bekende stelling?
- Berichten: 2.351
Re: Vraag m.b.t. rest bij deling
Wat je hebt uitgevonden komt volgens mij neer op
a*b (mod c) = a (mod c) * b (mod c)
Dat is een veelgebruikte rekenregel met bijvoorbeeld toepassingen in crypto.
a*b (mod c) = a (mod c) * b (mod c)
Dat is een veelgebruikte rekenregel met bijvoorbeeld toepassingen in crypto.
- Moderator
- Berichten: 9.994
- Berichten: 2.351
Re: Vraag m.b.t. rest bij deling
Klopt. Dat moet erbij. Eenmaal je modulo aan het rekenen bent dan laat je die (mod c)'s uiteraard al snel vallen om het leesbaar te houden.
-
- Berichten: 303
Re: Vraag m.b.t. rest bij deling
Dank, helder! Leuke vondst toch voor een eenvoudige arts zonder “formele” wiskunde-achtergrond, behoudens de wiskunde B1,2 van het gymnasium