[Løst] Fermats lille teorem

[Lillekrek]

Hei,

 

Noen som vet hvordan man kan bruke fermats lille teorem for å forkorte tall, slik at jeg kan regne ut svaret? Jeg skal forkorte 243^(10^10) mod 547. Jeg har bare brukt det til primtallstestning og er egentlig lost på hvordan jeg kan gå frem. All hjelp hadde vært verdisatt.

 

Så vidt jeg kan forstå(til nå); siden 547 er primtall, kan jeg utrykke dette som 243^(546*k+r)=243^r for alle k?

Endret 30. oktober 2011 av Lillekrek

[wingeer]

Det står at det er løst, men det er et åpent spørsmål i posten så jeg tar ingen sjanser. Du har nesten forstått rett. Vi har, siden gcd(547,243)=1 (det holder altså ikke kun at 547 er et primtall!) at:

, og siden 10^10=18315018*546+172 har vi at:

. Her kan du videre redusere ved å se på hva 243^2 er kongruent med modulo 547, osv.