Kortare väg till moduliräkning (Matematik/Universitet)

Blir det enklare om man går via 125-2?

Fermats lilla sats kan tillhandahålla en genväg i moduloproblem eftersom de omvandlar problemet från ett faktoriseringsproblem till ett restberäkningsproblem

Dock så är det viktigt att påminna oss om att Fermats lilla sats endast gäller när talet man beräknar resten med avseende på (delaren om man så vill) är ett primtal

$a^{p - 1} \equiv_p 1$

så

$42342^6 \equiv_7 1$ , men däremot $42342^7 \equiv_8 0$ (inte 1)

När vi beräknar rester med avseende på primtal p så kan vi börja med att finna resten av exponenten med avseende på $p - 1$

$a^m = a^{q(p - 1) + r} = (a^{p - 1})^q a^r \equiv p = 1^q a^r \equiv a^r$

Exempelvis i ett fall med $p = 7$

$432^{5789} = 432^{964 \cdot 6 + 5} \equiv_7 432^5$

vilket systematiserar vägen till en mindre potens. Effektivt

$a^m \equiv_p a^{m{\pmod{p - 1}}}, \quad (\forall m \in \mathbb{N}, p \in \mathbb{P})$

Notera dock att detta endast är relevant när talet man tar fram resten med avseende på är ett primtal och inte fungerar för 100 som inte är ett primtal.

Det är dock möjligt att utveckla en modifikation av denna process även för tal som inte är primtal genom att använda generaliseringen av Fermats lilla sats, Eulers sats, vilken gäller för alla divisorer och inte bara primtal

$a^{\phi(n)} \equiv_n 1$

Men iochmed att man då måste beräkna $\phi(n)$ (Eulers fifunktion) så är jag inte säker på att processen verkligen besparar en så mycket tid.

(Lämnar detaljerna till den intresserade)

Tack SeriousC för din jätteseriöst svar! Eulers sats har jag inte hunnit till.

Men du menar att Lilla Fermat kommer inte att fungera här pga att 100 är ingen primtal?

Går min problem att lösa?

PeBo, hur menar du med 125? Det är en division med 100, hur menar du?

Men du menar att Lilla Fermat kommer inte att fungera här pga att 100 är ingen primtal?

Ja. Eftersom 100 inte är ett primtal så fungerar inte Fermats sats och är inte användbart här alls.

Går min problem att lösa?

Jag skulle säga att din lösning redan är en bra lösning; där särskillt systematiken att alltid dela upp potensen i 2q + r-form garanterar att algoritmen når sitt mål inom förhållandevis kort tid. Det här är ju fortfarande ett enormt tal vi har att göra medSå att det tar några steg att blir klar är kanske inte så konstigt.

Sedan kan man naturligtvis finna bättre metoder att lösa problemet som är lite snabbare eller lite elegantare. Dessa faller väl i två kategorier

1. Systematiska algoritmer som alltid fungerar. Använder man Euler-fi-metoden jag antyder i mitt inlägg så besparar man sig några enstaka steg men ärligt talat är det knappt värt det i detta fall. Lösningen upptar fortfarande ungefär lika många steg som din: https://imgur.com/iQoToZm (behöver inte förstå, bara illustrerar att denna lösning också tar tid)

2. Trick som fungerar för specifika problem men inte alla. Det PeBo antyder är en sådan lösning. Om du tar

$123^{456} = (125 - 2)^{456} = (5^3 - 2)^{456}$

och sedan expanderar parentesen med binomialsatsen så kanske du ser något som du kan utnyttja.

(När jag väl tänker efter kanske detta faktiskt faller in i kategori 1 ändå då det går att utveckla en systematisk metod från detta trick)

Det intressanta är att man får hjälp av $125^{x} \equiv 25 (m o d 100)$ för alla x, men sen behöver man visa $2^{456} \equiv 36 (m o d 100)$ , vilket jag inte ser något smidigt sätt att göra. Jag föreställer mig ju att $2^{10} = 1024 \equiv (25 - 1) (m o d 100)$ kunde vara till hjälp, men jag har inte riktigt hittat fram den vägen. Jag har också provat fiska efter 36 i formen av -64 genom en kvadrat på 8 från 2 som (10-8) och dess binomialutveckling. Kanske att bryta ut 4 först för att få alla 25:or att bli noll i binomialutvecklingen.

Oki. Men ni har inte sett något självklart som jag borde ha gjort i alla fall.

Tack för allt hjälp!💕❤️

Jag missade en lågt hängande frukt här: Använd Kinesiska restklassatsen!

Eftersom 4 och 25 är relativt prima så kan vi leta efter något tal som finns i båda dessa restklasser. Om vi hittar något tal som är rest för båda dessa moduler så är det också rest för produkten 100. Man ser direkt att eftersom $123 \equiv - 1 (m o d 4)$ så är $123^{456} \equiv 1 (m o d 4)$ , dvs alla tal 1, 5, 9 ... är rest vid division med med 4. Om man tittar på 25 så är $123 \equiv - 2 (m o d 25)$ , dvs vi har igen att processa $(- 2)^{456}$ , men vi kan använda att $2^{10} = 1024 \equiv - 1 (m o d 25)$ , vilket gör att $(- 2)^{456} \equiv ((- 2)^{10})^{45} (- 2)^{6} \equiv (- 1)^{45} \times 64 \equiv 11 (m o d 25)$ , där det sista kommer av att $- 64 = - 2 * 25 - 14 = - 3 * 25 + 11$ . Det tal som finns i restklassen 1 vid division med 4 och i restklassen 11 vid division med 25 är 61. 15*4+1 = 2*25+11=61.

Tack... denna kinesiska restklassatsen måste jag processera lite till...

God morgon!

Nu har jag processerat lite grand! Väldigt användbar!

PeBo skrev :
Jag missade en lågt hängande frukt här: Använd Kinesiska restklassatsen!
Det tal som finns i restklassen 1 vid division med 4 och i restklassen 11 vid division med 25 är 61.
15*4+1 = 2*25+11=61.

Saken jag inte är med är sista raden. Hur kommer du fram till 61? Har du testat helt random eller är det Eulers-fi satsen?

En till fråga, kunde använda den negativa resten $-14$ från $(-2)\cdot 25 -14 = -64$ , eller blir det krångligt att modulera negativa tal?

Jag har försökt att läsa Wikipedia sidan du länkade (blev lite svårt :)!) och leta på Youtube men det gav mig inget som jag kunde använda-alla restsatserna är från matte 3c.

Vad gäller just det här talet så vet jag ju att det handlar om att det finns ett tal mellan 0 och 99, så det vore inte lika lätt att dra den där ur hatten om det vore enormt stora tal det handlade om. Då vore det inte heller lätt att hitta relativt prima faktorer till talet (i det här fallet 4 och 25 som är relativt prima och faktoriserar 100). Mycket (men inte all!) modern kryptografi bygger på att primtalsfaktorisering är svår för väldigt stora tal. Nu ser man liksom direkt att 61 dyker upp som genensamt element i klasserna 1 mod 4 och 11 mod 25. Annars blir det ju precis en diofantisk ekvation som du ju redan är expert på.

Jag är lite osäker på vad din fråga om -14 innehåller, men du ser ju att man landar på -64, och det känner man lätt igen som samma klass som 11 modulo 25. Moduler av negativa tal (och negativa rester) är inte krångliga alls, och de förekommer i massor. Jag tror att det generellt är rätt ofta man har nytta av söka negativa kongruenser till tal eftersom det helt enkelt utökar antalet "enkla" lösningar man kan hitta. Att gå via 1024 som är -1 modulo 25 löser mycket av problemen i det här fallet. Man kan förstås söka negativa rester också, och man vet ju att -39 (-14-25 och -10*4+1 eller -9*4-3) är samma tal som 61. Tänk där på att 1 och -3 är samma klass modulo 4 på samma sätt som 11 och -14 är samma klass modulo 25. Alla tal vars skillnad är en multipel av modulen ligger i samma klass. Du kan också se 61 som 15*4+1 = 2*25+11 = 3*25-14 = 61. Det kanske var det du tänkte på med att använda den negativa resten. Jag valde den positiva 11:an för att jag tänkte att det var enklare att se. Bytet är liksom trivialt -- åtminstone när man förstått det. ;)

Jag kan hålla med om att wiki-sidan tyvärr inte är till någon hjälp för att illustrera den här tekniken, men det räcker att veta att om p och q är relativt prima, dvs SGD(p,q)=1 (och det här gäller för en större mängd faktorer också) och resten vid division med den modulen för någon tal N är känt för p och q vardera, då innehåller restklassen vid division med produkten pq de element som finns i båda faktorernas restklasser.

Ett exempel till som inte är så råddigt. Antag att vi vill veta vilken resten är vid division av 123456789 med 30. Vi ser direkt att summan av siffrorna är 45, så talet är delbart med 3, dvs resten vid division med 6 är 3. Lägg märke till att det inte kan vara 0, för om talet varit delbart med 6 så hade det varit jämnt (2:an i 6 du vet). Vi ser också att resten vid division med 5 är 4. Det betyder att resten vid division med 30 ligger i restklasserna 3 mod 6 och 4 mod 5. I den senare har vi 4, 9, 14, 19, 24, 29 och där är det liksom slut upp till 30. För faktorn 6 har man resten 3, så vi letar efter 3, 9, ... ja, där kan vi sluta leta, och där ser vi att 9 ligger i båda modulernas (5 och 6) restklasser. Alltså, 123456789 = 9 (mod 30).

Jag ska se om jag hittat någon bättre beskrivning av den där tekniken -- säg gärna till om du tycker det är svårt att hänga med så kan jag försöka rensa upp och fixa en bättre beskrivning. Faktum är att det är samma intuition som förklarar varför en SGD() större än 1 låser fast en diofantisk ekvation på en gångertabell, så att talet i högerledet (för den diofantiska ekvationen) måste ligga i samma gångertabell (innehålla SGD) för att det ska finnas en lösning.

Lessen för att det blev så många ord, men hoppas att det förklarar något.

Jo men det faktiskt gör det!

Jag är för trött just nu men jag återkommer vidare till din exempel med 123456789.

Jag ska försöka hitta på en exempel själv.

Nu har jag läst om det, det är faktiskt brilliant.

Jag ska öppna en ny tråd för att skapa en ny tråd och diskutera detta.