Re: Congruentie met deling

Dit is een reactie op vraag 28911

Bedankt voor uw reactie,

Ik snap echter de uitkomst niet volledig, omdat niet alle waarden uit uw antwoord een correcte deling opleveren. Deze antwoorden zijn dan “op papier” correct, maar geen oplossing voor het gedefinieerde probleem.

De vraag heeft namelijk inderdaad niet veel van doen met modulo rekenen maar wel alles met gehele getallen en dus deling zonder remainder. Mijn programmaatje was inderdaad niet goed geprogrammeerd. Ik had de vergelijking (9802190a-1)/(5107-a) met integers geprogrammeerd, waarbij een eventuele niet gehele uitkomst naar beneden werd afgerond. Aangezien ik uitging van een geheel getal, klopt het antwoord 866 wel, maar alleen nadat ik dit getal heb nagerekend. Het programma leverde namelijk ook hele antwoorden voor een deling die in principe niet op een geheel getal uitkomt. Hierbij was er een kleine kans dat een waarde dan modulo 1919 wel 62 leverde, maar dat gebeurde in dit geval (toevallig) niet.

Ik heb daarom ook een aanpassing verricht en het programma rekent nu als eerste uit met welk getal voor a je op een geheel getal uitkomt. Dit is echter weinig professioneel. Het programma rekent gewoon voor elk getal (dus voor 2 miljard getallen in dit geval) de vergelijking uit ((9802190a-1) mod (5107-a)=0). Daarnaast berekent het dit resultaat (indien geheel getal) modulo 1919, indien voorgaande deling een geheel getal oplevert.

De antwoorden 5106 en 5108 zijn logisch omdat elk geheel getal deelbaar is door 1.

Voor a geldt: -1.000.000.000=a=1.000.000.000, a5107. De uitvoer is:

1. (9802190a-1)=0 mod (5107-a)
2. (6482011a+2)=0 mod (5107-a)

Geheel getal met vergelijking 2. a=-704327450; -6481964 mod 1269=-1181
Geheel getal met vergelijking 1. a=-495636322; -9802089 mod 1919=-1756
Geheel getal met vergelijking 2. a=-234772412; -6481870 mod 1269=-1087
Geheel getal met vergelijking 2. a=-78254066; -6481588 mod 1269=-805
Geheel getal met vergelijking 1. a=-26081284; -9800271 mod 1919=-1857
Geheel getal met vergelijking 2. a=-26081284; -6480742 mod 1269=-1228
Geheel getal met vergelijking 1. a=-11798662; -9797949 mod 1919=-1454
Geheel getal met vergelijking 1. a=-8133372; -9796039 mod 1919=-1463
Geheel getal met vergelijking 2. a=-7800512; -6477770 mod 1269=-794
Geheel getal met vergelijking 2. a=-5376722; -6475860 mod 1269=-153
Geheel getal met vergelijking 2. a=-2596766; -6469288 mod 1269=-1195
Geheel getal met vergelijking 2. a=-1788836; -6463558 mod 1269=-541
Geheel getal met vergelijking 2. a=-862184; -6443842 mod 1269=-1129
Geheel getal met vergelijking 1. a=-616144; -9721611 mod 1919=-1876
Geheel getal met vergelijking 2. a=-592874; -6426652 mod 1269=-436
Geheel getal met vergelijking 1. a=-423234; -9685321 mod 1919=-128
Geheel getal met vergelijking 2. a=-283990; -6367504 mod 1269=-931
Geheel getal met vergelijking 2. a=-194220; -6315934 mod 1269=-121
Geheel getal met vergelijking 2. a=-160970; -6282684 mod 1269=-1134
Geheel getal met vergelijking 1. a=-111762; -9373849 mod 1919=-1453
Geheel getal met vergelijking 2. a=-109400; -6192914 mod 1269=-194
Geheel getal met vergelijking 1. a=-75472; -9180939 mod 1919=-443
Geheel getal met vergelijking 2. a=-50252; -5884030 mod 1269=-946
Geheel getal met vergelijking 2. a=-33062; -5614720 mod 1269=-664
Geheel getal met vergelijking 2. a=-13346; -4688068 mod 1269=-382
Geheel getal met vergelijking 2. a=-7616; -3880138 mod 1269=-805
Geheel getal met vergelijking 1. a=-1044; -1663711 mod 1919=-1857
Geheel getal met vergelijking 2. a=-1044; -1100182 mod 1269=-1228
Geheel getal met vergelijking 1. a=866; 2001579 mod 1919=62
866=antwoord op totale vergelijking!
Geheel getal met vergelijking 2. a=866; 1323608 mod 1269=41
866=antwoord op totale vergelijking!
Geheel getal met vergelijking 1. a=3188; 16284201 mod 1919=1486
Geheel getal met vergelijking 2. a=3838; 19604380 mod 1269=868
Geheel getal met vergelijking 2. a=4684; 71777162 mod 1269=1253
Geheel getal met vergelijking 2. a=4966; 228295508 mod 1269=1139
Geheel getal met vergelijking 1. a=5006; 485839239 mod 1919=252
Geheel getal met vergelijking 2. a=5060; 697850546 mod 1269=797
Geheel getal met vergelijking 2. a=5080; 1219578366 mod 1269=840
Geheel getal met vergelijking 1. a=5088; 2624923301 mod 1919=1880
Geheel getal met vergelijking 2. a=5098; 3671699120 mod 1269=1169
Geheel getal met vergelijking 2. a=5104; 11028061382 mod 1269=887
Geheel getal met vergelijking 1. a=5106; 50049982139 mod 1919=62
5106=antwoord op totale vergelijking!
Geheel getal met vergelijking 2. a=5106; 33097148168 mod 1269=41
5106=antwoord op totale vergelijking!
Geheel getal met vergelijking 1. a=5108; -50069586519 mod 1919=-1857
Geheel getal met vergelijking 2. a=5108; -33110112190 mod 1269=-1228
Geheel getal met vergelijking 2. a=5110; -11041025404 mod 1269=-805
Geheel getal met vergelijking 2. a=5116; -3684663142 mod 1269=-1087
Geheel getal met vergelijking 1. a=5126; -2644527681 mod 1919=-1756
Geheel getal met vergelijking 2. a=5134; -1232542388 mod 1269=-758
Geheel getal met vergelijking 2. a=5154; -710814568 mod 1269=-715
Geheel getal met vergelijking 1. a=5208; -505443619 mod 1919=-128
Geheel getal met vergelijking 2. a=5248; -241259530 mod 1269=-1057
Geheel getal met vergelijking 2. a=5530; -84741184 mod 1269=-1171
Geheel getal met vergelijking 2. a=6376; -32568402 mod 1269=-786
Geheel getal met vergelijking 1. a=7026; -35888581 mod 1919=-1362
Geheel getal met vergelijking 1. a=9348; -21605959 mod 1919=-1857
Geheel getal met vergelijking 2. a=9348; -14287630 mod 1269=-1228
Geheel getal met vergelijking 1. a=11258; -17940669 mod 1919=-1857
Geheel getal met vergelijking 2. a=11258; -11863840 mod 1269=-1228
Geheel getal met vergelijking 2. a=17830; -9083884 mod 1269=-382
Geheel getal met vergelijking 2. a=23560; -8275954 mod 1269=-805
Geheel getal met vergelijking 2. a=43276; -7349302 mod 1269=-523
Geheel getal met vergelijking 2. a=60466; -7079992 mod 1269=-241
Geheel getal met vergelijking 1. a=85686; -10423441 mod 1919=-1352
Geheel getal met vergelijking 2. a=119614; -6771108 mod 1269=-993
Geheel getal met vergelijking 1. a=121976; -10230531 mod 1919=-342
Geheel getal met vergelijking 2. a=171184; -6681338 mod 1269=-53
Geheel getal met vergelijking 2. a=204434; -6648088 mod 1269=-1066
Geheel getal met vergelijking 2. a=294204; -6596518 mod 1269=-256
Geheel getal met vergelijking 1. a=433448; -9919059 mod 1919=-1667
Geheel getal met vergelijking 2. a=603088; -6537370 mod 1269=-751
Geheel getal met vergelijking 1. a=626358; -9882769 mod 1919=-1838
Geheel getal met vergelijking 2. a=872398; -6520180 mod 1269=-58
Geheel getal met vergelijking 2. a=1799050; -6500464 mod 1269=-646
Geheel getal met vergelijking 2. a=2606980; -6494734 mod 1269=-1261
Geheel getal met vergelijking 2. a=5386936; -6488162 mod 1269=-1034
Geheel getal met vergelijking 2. a=7810726; -6486252 mod 1269=-393
Geheel getal met vergelijking 1. a=8143586; -9808341 mod 1919=-332
Geheel getal met vergelijking 1. a=11808876; -9806431 mod 1919=-341
Geheel getal met vergelijking 1. a=26091498; -9804109 mod 1919=-1857
Geheel getal met vergelijking 2. a=26091498; -6483280 mod 1269=-1228
Geheel getal met vergelijking 2. a=78264280; -6482434 mod 1269=-382
Geheel getal met vergelijking 2. a=234782626; -6482152 mod 1269=-100
Geheel getal met vergelijking 1. a=495646536; -9802291 mod 1919=-39
Geheel getal met vergelijking 2. a=704337664; -6482058 mod 1269=-6

Uit deze opsomming blijkt dat 866 en 5106 de enige 2 antwoorden zijn waarbij geldt voor a (-1.000.000.000=a=1.000.000.000).

De bedoeling is dus (waarschijnlijk?) dat de vergelijking (9802190a-1)/(5107-a=62 (mod 1919) wordt gesplitst.

De vraag is dan ook misschien een nieuw probleem, namelijk.

De oude vraag was, of ik de antwoorden 866 en 5106 direct kan uitrekenen. Mijn inschatting is dat dit onmogelijk is (alleen 5106 is wel mogelijk, tenminste gemakkelijker te berekenen). Daarom ben ik op zoek naar het berekenen van de bovenstaande getallen.

Hoe kan ik de getallen van de huidige formule berekenen zonder de bijzonder inefficiënte berekeningen die mijn programma uitvoert? Als ik namelijk de bovenstaande lijst m.b.v. een formule kan berekenen ben ik al een flink stuk verder dan wanneer ik 2 miljard getallen, of meer moet proberen. De uitkomst 866 (en 5106) is toevallig, (alleen niet bij deze berekening blijkbaar) deze had ook veel groter kunnen zijn.

Ik kan me namelijk dezelfde vergelijking voorstellen met een oplossing die bestaat uit 100 cijfers. Hierbij is het vrijwel onmogelijk om een antwoord te vinden, omdat dit dan inderdaad vrijwel een oneindig aantal berekeningen betekent.

Verder is het opmerkelijk te zien, dat er maar 2 kleine oplossingen zijn. Graag zou ik weten of ik ergens een fout maak, of indien er gehele oplossingen zijn m.b.v. een modulo formule. Mijn huidige inschatting is (maar die kan onjuist zijn), dat de gevonden 2 oplossingen de enige zijn. Het lijkt me erg onwaarschijnlijk, dat er na 2 miljard getallen narekenen ineens een radicale verandering optreedt. Daarnaast dunt het aantal oplossingen waarvoor de deling een gehele waarde oplevert ook snel uit.

Vr Gr,

c.p.

c.p.
Iets anders - woensdag 27 oktober 2004

Antwoord

Ik heb begrepen dat aan beide vergelijkingen tegelijk moet voldaan zijn. Dan vind je echter nog erg veel oplossingen voor a met mijn berekening, en die is volgens mij correct.

De clou van hetgeen ik in mijn vorig antwoord gaf, is dat de deling niet geheel moet zijn om oplossingen te kunnen hebben. Ik zei dat je delen als vermenigvuldigen met het invers moet opvatten. Een niet-gehele uitkomst is onmogelijk bij modulorekenen. (Zie mijn voorbeeld 7/5 mod 9=5). Je programma laat al die oplossingen over.

Mijn berekening is wel niet helemaal correct. Er zijn nog een (klein) aantal "oplossingen" voor a die wegvallen omdat de deling gewoon niet altijd te berekenen is (omdat mod 1919 of 1269 geen veld vormt) (nl een deel van de gevallen waar ggd(5107-a, 1919 of 1269) niet gelijk is aan 1).

Wat je wil weten is niet het antwoord op de vraag. Je zoekt in eerste instantie naar gehele oplossing a waarbij LL geheel uitkomt. Een vergelijking waarbij je gehele oplossingen zoekt heet een diophantische vergelijking. Die is soms algemeen oplosbaar. In dit specifiek geval weet ik echter niet direct hoe je deze vergelijking kunt oplossen. Op gebied van diophantische vergelijkingen is veel vindingrijkheid nodig (getuige de laatste stelling van Fermat).

Joeri
donderdag 28 oktober 2004

©2001-2024 WisFaq