26 svar
110 visningar
Isabella.mattehjälp är nöjd med hjälpen!
Isabella.mattehjälp 18
Postad: 6 jan 2021 Redigerad: 6 jan 2021

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

Hej! jag behöver hjälp med denna uppgift

Bestäm ett x mellan 0 & 103 så att 3^648x (mod 103)

Förstår inte hur jag ska räkna ut detta då det även är en potens. Hur ska jag göra? 

Laguna 12555
Postad: 6 jan 2021

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

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

Isabella.mattehjälp 18
Postad: 6 jan 2021

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

Laguna 12555
Postad: 6 jan 2021

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

Isabella.mattehjälp 18
Postad: 7 jan 2021 Redigerad: 7 jan 2021

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?

Laguna 12555
Postad: 7 jan 2021

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

Isabella.mattehjälp 18
Postad: 7 jan 2021

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?

Laguna 12555
Postad: 7 jan 2021 Redigerad: 7 jan 2021

31033(mod103)3^{103} \equiv 3 (\mod 103)

Isabella.mattehjälp 18
Postad: 7 jan 2021

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.

3648 = 3103.3103.3103.3103.3103.3103.330

Isabella.mattehjälp 18
Postad: 7 jan 2021 Redigerad: 7 jan 2021
Smaragdalena skrev:

3648 = 3103.3103.3103.3103.3103.3103.330

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:/

Laguna 12555
Postad: 8 jan 2021

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:

3648 = (3324)2
3324 = (3162)2
3162 = (381)2
381 = 3 * (340)2

osv.

Isabella.mattehjälp 18
Postad: 8 jan 2021 Redigerad: 8 jan 2021
, men man kan använda den här tekniken, utan Fermats sats:

3648 = (3324)2
3324 = (3162)2
3162 = (381)2
381 = 3 * (340)2

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:

3648 = 3103.3103.3103.3103.3103.3103.330

Om du kombinerar detta med det som Laguna skrev, nämligen 31033(mod 103), så behöver du inga andra krångliga satser. 

Isabella.mattehjälp 18
Postad: 10 jan 2021

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 3103 kongruent med 3. Kommer du vidare härifrån?

Laguna 12555
Postad: 10 jan 2021

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

Isabella.mattehjälp 18
Postad: 10 jan 2021

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. :)

Isabella.mattehjälp 18
Postad: 10 jan 2021
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?

Isabella.mattehjälp 18
Postad: 10 jan 2021 Redigerad: 10 jan 2021
Smaragdalena skrev:

När du räknar modulo 103 så är 3103 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? 

Laguna 12555
Postad: 10 jan 2021

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?

Isabella.mattehjälp 18
Postad: 10 jan 2021 Redigerad: 10 jan 2021
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?  

Laguna 12555
Postad: 10 jan 2021

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

Isabella.mattehjälp 18
Postad: 10 jan 2021 Redigerad: 10 jan 2021

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?

Isabella.mattehjälp 18
Postad: 10 jan 2021

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

Laguna 12555
Postad: 10 jan 2021

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.

Isabella.mattehjälp 18
Postad: 10 jan 2021

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

Svara Avbryt
Close