Största gemensamma delare

Kan man säga något om a (mod 91) om man vet att sgd(a, 91) är 1?

Jag kan säga att sdg (a,91)=1 medför att a och 91 är relativt prima men det kanske inte är det du är ute efter?

har du löst uppgiften

Nej är inte säker på att jag förstår den, kan du förklara? :)

Hur gick det med detta?

Jag kommer inte ihåg vad jag menade med mitt tips, men det här fungerar: anta att sgd(b,91) inte är 1. Vad innebär det för b?

Tjena kingen! Antagligen så är du inte behövandes av lösningen, men jag tänker jag delar ändå. Kan oxå vara till hjälp för andra som ser detta!

Själv hade jag problem, och använde ChatGPT för att förstå och komma fram till svaret. Jag hade rätt tanke och idé i alla fall, och jag rekommenderar alla som läser detta att försöka själva och tänka ordentligt innan ni försöker hitta någons lösning eller använda GPT. Här är iaf lösningen (OBS! Lösningen är samma oavsett vad ni har för [mod n]):

Direkt kan man inse ekvivalensen att: b ≡ a (mod 91) <=> a ≡ b (mod 91)

För att komma vidare använder jag indirekt bevis, där du genom att anta det motsatta till vad du ska bevisa, får sambandet att bli falskt, därför måste uppgiftens antagande stämma:

Antag att SGD(b, 91) = d och att d > 1. Vi får då att d | b och d | 91. 

d | 91 => d | 91k där k är ett heltal

b ≡ a (mod 91) <=> a ≡ b (mod 91) <=> a = b - 91k

Eftersom d | b och d | 91k så måste därför d | b - 91k och d | 91k - b

b - 91k vet vi är = a vilket ger oss: d | a

Nu har vi att d | a och d | 91 vilket ger att SGD(a, 91) = d

Enligt VÅRT antagande så är d > 1 vilket ger att SGD(a, 91) > 1 vilket enligt instruktioner är falskt, eftersom:
SGD(a, 91) = 1

Därför är vårt antagande att d > 1 falskt, vilket medför att SGD(b, 91) = d = 1 (varför vi vet att SGD inte är mindre än 1 är eftersom SGD alltid kommer att vara 1 eller högre, för alla heltal är delbara med 1)

Om någon har frågor elr inte fattar så skriv en kommentar, så hoppas jag att jag ser det och kan svara!
Peace!