Pagina 1 van 2
Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: vr 05 jul 2013, 10:32
door Kwintendr
Hallo,
Hoeveel gehele oplossingen m heeft de lineaire congruentie
\(140701\overset{\underset{\mathrm{m}}{}}{=}107041\)
Ik kom 9917 oplossingen uit, maar ik weet niet of dit juist is. Ik doe het zo:
\(140701\overset{\underset{\mathrm{m}}{}}{=}107041\Leftrightarrow 107041+km=140701\Leftrightarrow km=33660\)
Er is nu nog 1 probleem, hoeveel gehele waarden neemt m aan? Daarvoor moet k een deler zijn van 33660. Ik ontbind 33660 in priemgetallen: 2,2,3,3,5,11,17. Dus elk product van deze getallen is een deler (vb 2*3*5*11 is een deler). En nu vraag ik me af of mijn redenering wel nog klopt. Ik wil weten hoeveel delers er zo zijn. Daartoe neem ik eerst alle delers met 1 getal -> dit zijn er 5. Dan neem ik het aantal delers met 2 getallen: dat zijn er 7*6. En zo ga ik verder tot het getal 33660. Alleen zit ik hier met met 7*6*5*4*3*2*1 mogelijkheden. Dat kan niet. Ik weet wat hier fout aan is. Je ziet hier bv 11*17 en 17*11 als een andere mogelijkheid, maar dat wil ik niet. Hoe los je dit dan op?
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: vr 05 jul 2013, 11:08
door Safe
Los dit eens op met eenvoudiger getallen, kies die zelf ...
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 15:34
door Kwintendr
Sorry voor de late reactie. Ik heb het is met dit gedaan:
\(3\overset{\underset{\mathrm{m}}{}}{=}7\)
.
=> 3+k*m=7 <=> K*m=4
aangezien m geheel moet zijn kan k alleen de waarden 1, 2, 4 aannemen waardoor er 3 mogelijke waarden zijn voor m, nl 1, 2, 4.
In dit geval is het gemakkelijk om te weten te komen hoeveel waarden er zijn voor k, maar in mijn vraag is dat niet het geval.
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 15:47
door Safe
Hoe zo wordt het moeilijker? Neem dan eens:
\(12\overset{\underset{\mathrm{m}}{}}{=}24\)
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 15:53
door Kwintendr
Dat kan ik ook, maar ik denk dat mijn werkwijze te omslagtig is. Ik doe het zo:
m=12/k. Aangezien m geheel moet zijn, kan k alleen maar de waarden 1,2,3,4,6,12 aannemen en zijn er dus 6 mogelijke moduli. Maar bij 33660 moet je dan ook alle delers opschrijven. Dat zijn er toch imens veel?
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 16:32
door Safe
Er zijn natuurlijk meer mogelijkheden, maar wat is het probleem ...
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 17:02
door Kwintendr
Hoe je al die mogelijkheden bepaald.
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 17:32
door Drieske
Een vrij "mooie" en "eenvoudige" manier, is zo: stel dat
\(n = p_1^{r_1} p_2^{r_2} \ldots p_k^{r_k}\)
, dan is het aantal delers van n gelijk aan
\((r_1 + 1)(r_2 + 1) \ldots (r_k + 1)\)
. Kun je dat inzien?
Verborgen inhoud
Hint: je weet dat je deler steeds bestaat uit de priemdelers en een exponent. Op hoeveel manieren kan je nu een exponent kiezen?
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 17:48
door Kwintendr
ja, dat snap ik. Je hebt altijd nog een extra mogelijkheid, nl 0. Dan kom ik uit op 72. Ik weet wel niet of dat de juiste oplossing is want ik heb daar geen oplossing van.
Maar bij die combinaties. Dan kom je toch iets anders uit? Je kijkt hoeveel delers je kan vormen met 1 priemgetal, dat zijn er 5. Hoeveel delers kan je vormen met 2 getallen?
\(\binom{n}{k}=\frac{n!}{k!(n-k)!}\)
en daar komt 21 uit. Zo doen we verder tot 7 getallen.
Het eerste probleem waar ik op stuit: Als ik redeneer om een deler te nemen bestaande uit 1 getal, dan heb ik er 5. Doe dat met die formule en je komt uit op 7...
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: zo 07 jul 2013, 21:51
door Drieske
Kwintendr schreef: ↑zo 07 jul 2013, 17:48
Het eerste probleem waar ik op stuit: Als ik redeneer om een deler te nemen bestaande uit 1 getal, dan heb ik er 5. Doe dat met die formule en je komt uit op 7...
Doe wat met die formule? Die formule kan enkel het totaal aantal delers geven hè... Niet het aantal delers uit 1 getal bijvoorbeeld.
Zie btw ook bijv hier:
http://en.wikipedia.org/wiki/Divisor_function
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: ma 08 jul 2013, 08:51
door Kwintendr
Ik snap het niet. Wij hebben nooits zoiets gezien als een "Divisor functie".
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: ma 08 jul 2013, 09:42
door Drieske
Dat moet je niet gezien hebben. Daar staat gewoon ook de formule die ik je gaf... Maar snap je dat die formule je enkel zegt hoeveel het totaal aantal delers is en niet kan gebruikt worden voor het aantal delers bestaande uit 1 getal oid?
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: ma 08 jul 2013, 10:23
door Kwintendr
ik snap het
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: ma 08 jul 2013, 13:33
door Drieske
Prima
. En je snapt de formule zelf ook nu?
Re: Aantal gehele oplossingen m van een lineaire congruentie
Geplaatst: ma 08 jul 2013, 13:56
door Kwintendr
Ja, ik snap perfect hoe je er aan komt. Maar dat is de mooie en eenvoudige manier, kan het ook op een andere manier?
