Hur kan man bestämma lösningarna till kongruensen?
God kväll!
Jag skrev prov i talteori idag och misslyckades på en av frågorna eftersom jag inte kunde lösa följande kongruens för hand: . Jag söker endast heltalslösningar. Har ni något bra tips?
29m - 81n = 75
Jag vet bara ett generellt sätt.
Först sgf(29, 81). Det är förstås 1, men vi behöver se alla stegen i Euklides algoritm.
81 = 2*29 + 23
29 = 1*23 + 6
23 = 3*6 + 5
6 = 1*5 + 1
Nu går vi åt andra hållet.
1 = 6 - 5 = 6 - (23-3*6) = 4*6 - 23 = 4(29-23)-23 = 4*29 - 5*23 = 4*29 - 5(81-2*29) = 14*29 -5*81.
Nu har vi en lösning till 29m - 81n = 1, nämligen m = 14 och n = 5.
Då får vi samtliga lösningar genom att addera respektive subtrahera multipler av 29 och 81:
m = 14 + 81q
n = 5 - 29q
Man kan säga att vi utnyttjar att 29*81 - 81*29 = 0.
Nu var det inte 1 vi ville ha, utan 75. Då multiplicerar vi bara med 75:
m = 14*75 + 81*75q
n = 5*75 - 29*75q
Skulle m och n uppfylla några speciella kriterier? T.ex. vara positiva? Då får man hitta q så att det blir så.
Tillägg: 31 jan 2024 22:29
Nu multiplicerade jag nog för mycket. Termen med q är giltig även utan 75, så det blir
m = 14*75 + 81q
n = 5*75 - 29q
