Vraag m.b.t. rest bij deling

[PhilipVoets]

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!

[Xilvo]

Tegenvoorbeeld:
55 = 5 x 11
55 mod 3 = 1
5 mod 3 = 2
11 mod 3 = 2

[PhilipVoets]

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?

[Xilvo]

Anyway, dank voor tegenvoorbeeld. Ik heb nog geen tegrnvoorbeeld gevonden als geldt dat Y > product der resten. Jij wel?

In ieder geval niet voor X<1.000.000 waarbij X precies twee delers heeft.

[PhilipVoets]

Apart/interessant, toch?

[Xilvo]

Apart/interessant, toch?

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.

[PhilipVoets]

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.

[Xilvo]

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.

[PhilipVoets]

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

[Xilvo]

Is dit overigens een al lang bekend fenomeen in de wiskunde of “nieuw”?

Voor mensen die zich regelmatig met dit soort wiskunde (geheeltallig, modulo) bezighouden is dit zonder twijfel gesneden koek.

[PhilipVoets]

Het is inderdaad niet denderend complex, maar ik kon het nergens terugvinden, misschien gemist, haha? Iemand die dit al “kent” als bekende stelling?

[wnvl1]

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.

[Xilvo]

Wat je hebt uitgevonden komt volgens mij neer op

a*b (mod c) = a (mod c) * b (mod c)

Dan toch
a*b (mod c) = (a (mod c) * b (mod c)) (mod c)

[wnvl1]

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.

[PhilipVoets]

Dank, helder! Leuke vondst toch voor een eenvoudige arts zonder “formele” wiskunde-achtergrond, behoudens de wiskunde B1,2 van het gymnasium