3^648=x(mod 103) Kongruensräkning

Fermats lilla sats kan vara användbar. Har ni lärt er den? 

https://sv.m.wikipedia.org/wiki/Fermats_lilla_sats

Nej det har vi inte, hur skriver jag in denna uppgift i Fermats sats? 

Vad säger satsen om du sätter in dina värden? 

a^p= a(mod p) 

Så 3^648 = 3(mod 648)

3(mod 648)=x(mod 103) 

eftersom att 103 är ett primtal kan det endast delas med sig själv och ett. När jag delar någonting med 648 ska det ge en rest på 3. 

Hur fortsätter jag nu?

ska jag fortsätta som induktion?

3^648 = 3(mod 648) stämmer inte, för p ska vara ett primtal för att satsen ska gälla.

Okej hur skriver jag då in detta i satsen?

x^103= 3^648? men då kan jag inte se vilken rest det ska bli? eller skriver jag på ett annat sätt, i så fall hur?

$3^{103} \equiv 3 (\mod 103)$

Men i uppgiften står det 3^648 ska jag skriva om det på något sätt? Eftersom vi inte vet vad x är. Förstår inte riktigt hur omskrivningen ska se ut och varför.

3⁶⁴⁸ = 3^103.3^103.3^103.3^103.3^103.3^103.3³⁰

Smaragdalena skrev:

3⁶⁴⁸ = 3^103.3^103.3^103.3^103.3^103.3^103.3³⁰

så 3(mod103) * 3(mod103) * 3(mod103) *3(mod103)* 3 (mod 103) *3(mod 103) * 3(mod 30) = X (mod 103)

Hur kommer man fram till vad X är steg för steg? :) har verkligen försökt att räkna med moduloräkning för att se vilken rest det ger men får inte fram det då jag inte vet hur jag ska fortsätta:/

En hel uträkning görs modulo någonting (eller en hel ekvation betraktas modulo någonting), så du behöver inte skriva (mod 103) så många gånger, och att ha med (mod 30) där är konstigt.

Jag vet inte om det finns något riktigt enkelt sätt att räkna ut svaret (det finns något som heter Eulers sats, men jag ser inte att den går att använda här), men man kan använda den här tekniken, utan Fermats sats:

3⁶⁴⁸ = (3³²⁴)²
3³²⁴ = (3¹⁶²)²
3¹⁶² = (3⁸¹)²
3⁸¹ = 3 * (3⁴⁰)²

osv.

, men man kan använda den här tekniken, utan Fermats sats:

3⁶⁴⁸ = (3³²⁴)²
3³²⁴ = (3¹⁶²)²
3¹⁶² = (3⁸¹)²
3⁸¹ = 3 * (3⁴⁰)²

osv.

Men om man skriver in detta i ekvationen, hur skulle det i så fall se ut? vad är det som är kongruent med x(mod 103)? 

Jag tänkte om man kanske skulle kunna använda räknelagarna a^b(mod c) =a(mod c))^b men 3^648 är ju inte skriven som modulo. Eller att man skriver om det som (3(mod 103))^6 + 30 som är kongruent med X(mod 103)men det kunde jag inte heller fortsätta räkna på. 

Så om man skulle skriva om 3^648, hur ser då ekvationen ut och vad är det som är kongruent med x(mod 103)? Om jag vet hur man skriver om det så skulle det bli mycket lättare att räkna ut :)

Smaragdalena skrev:

3⁶⁴⁸ = 3^103.3^103.3^103.3^103.3^103.3^103.3³⁰

Om du kombinerar detta med det som Laguna skrev, nämligen $3^{103}\equiv 3(mod 103)$, så behöver du inga andra krångliga satser. 

Vad menar du? :).

är det någon som löst denna uppgift för den känns omöjlig att lösa. 

När du räknar modulo 103 så är 3¹⁰³ kongruent med 3. Kommer du vidare härifrån?

Jag har en lösning, men den innehåller några steg, som bygger på det tidigare skrivna.

Jag förstår fortfarande inte hur ni har fått fram att 3^648 är 3^103=3(mod 103). Så det är redan där jag inte kommer vidare.

kan man tänka fermats lilla sats som säger att a^p-1 = 1 (mod p) 

3^102=1(mod 103)? 

3^648=3(6*102+36) =( 3^102) ^6 * 3^36 = 1^36 = 1^6 * 3^36= 3^36 (mod 103)

så 3^36 (mod 103) = X (mod 103)

sedan vet jag inte hur jag ska fortsätta. har jag tänkt rätt? Hur har ni löst uppgiften? Vill verkligen förstå hur man gör och varför. Skulle vara jätte snällt om ni kunde skriva steg för steg då jag nu tappat bort mig helt. :)

Laguna skrev:

Jag har en lösning, men den innehåller några steg, som bygger på det tidigare skrivna.

Om jag vet att 3^103= 3(mod 103) så är detta samma sak som 3^648? 

jag får fram 3^103= 3(mod 103) genom att...? Här är det lite oklart hur. 

om 3^103 ger en rest på 3 när jag delar det med 103. Då borde väll x bli 3? Om det ska vara samma sak?

Smaragdalena skrev:

När du räknar modulo 103 så är 3¹⁰³ kongruent med 3. Kommer du vidare härifrån?

när jag delar 3^103 i 103 får jag en rest på 3. Men hur kombinerar jag 3^103=3(mod103) med 3^648 = 3^103.3^103.3^103.3^103.3^103.3^103.3^30? 

Du har redan skrivit ett bra mellanresultat: 3^36 (mod 103) = X (mod 103)

Men som jag sa tidigare säger man (mod 103) bara en gång, för alla operationer görs modulo 103, inklusive likheten (som helst skrivs med tre streck och heter kongruens i de här sammanhangen).

Så hur får vi fram 3^36 mod 103? Ett sätt är att inse att det är kvadraten av 3^18 mod 103. Kan man komma vidare därifrån?

Laguna skrev:

Så hur får vi fram 3^36 mod 103? Ett sätt är att inse att det är kvadraten av 3^18 mod 103. Kan man komma vidare därifrån? 

 

Okej så jag har gjort början på korrekt sätt? sedan kan man fortsätta så här: 

(3^2)^18= 9^18 (mod 103) sedan kanske man kan skriva om det som (9^2)^9 vilket är 81^9(mod 103). Hur fortsätter jag nu?  

Min tanke är att reducera problemet till nånting man faktiskt kan räkna ut (med penna och papper eller miniräknare).

3^2 = 9

3^4 = 81

3^5 = 243 = 37 (mod 103)

3^6 = 3*37 = 111 = 8 (mod 103)

så 3^36 = (3^6)^6) = 8^6 (mod 103)

Hur skulle ni ha fortsatt nu? Är jag på rätt väg?

Jag har nu räknat och kommit fram till att x är 9. Har ni fått samma svar?

Utmärkt! Det fick jag i alla fall.

Nu är frågan kanske om det fanns något enklare sätt, och det vet jag inte.

okej vad bra. DEt var en svår uppgift, men tack för all hjälp :)