Modulär aritmetik: varför ges antalet lösningar till modulära ekvationer av nedanstående formel?

Påståendet är inte sant bara så där, det finns mer kontext som du utelämnar. 

Antalet lösningar är inte oberoende av b, kan vara 0 och kan vara oändligt så påståendet taget bara så där är falskt på många grunder.

Smutsmunnen skrev:

Påståendet är inte sant bara så där, det finns mer kontext som du utelämnar. 

Antalet lösningar är inte oberoende av b, kan vara 0 och kan vara oändligt så påståendet taget bara så där är falskt på många grunder.

Hmm, okej, lösbar, utlämnade jag. Sorry. Annars är uppgiften tagen i princip direkt från min bok (Diskret matematik och diskreta modeller, 2a upplagan)

Övning 3.40  Förklara varför en lösbar ekvation av typ $ax\equiv b \pmod n$ alltid har lika många lösningar som $gcd(a,n)$.

(facit saknas, by the way)

x här får då antas vara en ekvivalensklass, alternativt kan vi begränsa x till 0<=x<n.

Låt x_0 vara en lösning till ax=b mod n

Då är x_k=x_0 + k*n/SGD(a,n) också en lösning. Bara plugga in i ekvationen. 

Det finns precis SGD(a,n) sådana lösningar i intervallet 0<=x<n.

Återstår att visa att det inte finns andra lösningar.

Antag att z =x_0 + y är en lösning.

Då är a(z-x_0)=0 mod n så ay= 0 mod n så n|ay så y=nk/a för något k. Skriv om a som a=a'*SGD(a,n) så är saken biff.

coffeshot skrev:

Smutsmunnen skrev:

Påståendet är inte sant bara så där, det finns mer kontext som du utelämnar. 

Antalet lösningar är inte oberoende av b, kan vara 0 och kan vara oändligt så påståendet taget bara så där är falskt på många grunder.

Hmm, okej, lösbar, utlämnade jag. Sorry. Annars är uppgiften tagen i princip direkt från min bok (Diskret matematik och diskreta modeller, 2a upplagan)

Övning 3.40  Förklara varför en lösbar ekvation av typ $ax\equiv b \pmod n$ alltid har lika många lösningar som $gcd(a,n)$.

(facit saknas, by the way)

 

En helt avgörande detalj...

Tack för svaret!

Jag ber också om ursäkt för informationen jag utelämnade.

Jag förstår däremot inte riktigt hur man kan se nedanstående:

Det finns precis SGD(a,n) sådana lösningar i intervallet 0<=x<n.

Skulle du kunna hjälpa mig med det? Tack!

coffeshot skrev:

Tack för svaret!

Jag ber också om ursäkt för informationen jag utelämnade.

Jag förstår däremot inte riktigt hur man kan se nedanstående:

Det finns precis SGD(a,n) sådana lösningar i intervallet 0<=x<n.

Skulle du kunna hjälpa mig med det? Tack!

 

Säg att n/SGD(a,n)=d.

Vi har då en lösning x_0

Sedan x_0+d

Sedan x_0 + 2d

Sedan x_0 + 3d

...

Sedan x_0+(SGD(a,n)-1)d

det blir SGD(a,n) lösningar.

Fortsätter vi ett steg till har vi x_0+SGD(a,n)*d=x_0+SGD(a,n)*n/SGD(a,n)=x_0 +n och vi har gått ett helt varv runt.

Annorlunda uttryckt: av x_0+kd där k är godtyckligt heltal ligger precis n/d=SGD(a,n) inom ett intervall av längd n, så precis SGD(a,n) lösningar mellan 0 och n.

Tack! Nu förstår jag - tror jag... Jag är fortfande lite osäker på $x_0$. Om $x_0$ är *en* partikulärlösning, vet vi väl egentligen inte vart inom intervallet det ligger. Hur kan vi då veta att $x_0+\frac n {sgd(a,n)}(sgd(a,n)-1)$ säkert ligger inom intervallet?

Jo, du har rätt men det var bara en illustration, alltså mellan x_0  och x_0 +n/sgd(a,n) * (sgd(a,n)-1) har vi sgd(a,n) lösningar i ett intervall av längd n men inte nödvändigtvis i intervallet 0 till n. 

Men titta vad jag skrev sen ("Annorlunda uttryckt..."), vi kan välja k som ett godtyckligt heltal, även negativt, så det spelar ingen roll vilket x_0 vi råkar börja med. Även x_0-d, x_0-2d osv är lösningar. Det finns sgd(a,n) lösningar i VARJE intervall av längd n.