Kongruens

Hej! Jag håller på med en matte uppgift och har fastnat och vet inte vad jag ska göra nu. Det var ett tag sen som jag läste matte så jag är lite rostig!

Uppgiften: Bestäm resten då 3^118 delas med 7

Så har jag gjort: Med hjälp av formel: a^m (mod n) ≡ (a(mod n))^m

3^118 (mod 7) ≡ (3(mod7))^118 ≡ 3^118 (mod 7) = (3^2)^59 (mod 7) = 9^59 (mod 7) ≡(9(mod 7))^59 ≡ (2(mod 7))^59 = 2^59 (mod 7)

Så långt har jag kommit, men jag fastnade här då 59 är ett primtal vilket innebär att jag inte kan förenkla talet vidare. Talet är fortfarande för stort för räkna ut som den är och behöver förenklas mer om jag inte är helt ute och cyklar. Hjälp snälla! Tack!!

2^59=2*2^58=4*2^57... Bryt ut så mkt du behöver framför och fortsätt med det som är kvar

Välkommen till Pluggakuten! Utan att ha kollat om dina beräkningar stämmer, kan jag rekommendera att du delar upp $2^{59}$ i två delar, $2^{2} \cdot 2^{57}$ . Då kan du fortsätta vidare. :)

Micimacko skrev:
2^59=2*2^58=4*2^57... Bryt ut så mkt du behöver framför och fortsätt med det som är kvar

Tack för svar!

Jag har fortsatt men talet under exponenten blir för stort:

2^59 = 2x2^58 = 2x(2^2)^29 = 2x4^29 = 2x4x4^28 = 8x(4^2)^14 = 8x16^14 = 8x(16^2)^7 = 8x256^7

Jag har fastnat här då jag tror att jag tänkt fel eller gjort fel då 256 är för stor speciellt upphöjt till 7. Det klickar inte hos mig än hur jag ska avsluta detta :(

Smutstvätt skrev:
Välkommen till Pluggakuten! Utan att ha kollat om dina beräkningar stämmer, kan jag rekommendera att du delar upp $2^{59}$ i två delar, $2^{2} \cdot 2^{57}$ . Då kan du fortsätta vidare. :)

Tack för hjälpen!

Men vad gör jag av den första faktorn (2^2) som kommer att fortsätta väga desto mer jag bryter?

Den faktorn kan du låta vara vid liv tills den mycket större faktorn kommer ned till något litet tal. Du kanske kommer ned till exempelvis $4 \cdot 6$ , som du kan multiplicera ihop och sedan beräkna modulo 7 av.

2^59 = 2x2^58 = 2x(2^2)^29 = 2x4^29 = 2x4x4^28 = 8x(4^2)^14 = 8x16^14 = 8x(16^2)^7 = 8x256^7

Ett enklare sätt att ta sig vidare från $2^{2} \cdot 2^{57}$ är att skriva om 57 till $19\cdot3$ . Då får du $4 \cdot {(2^{3})}^{19} = 4 \cdot 8^{19}$ . Vad blir det uttrycket lika med om du räknar med modulo 7?

Spoiler och tips i ett!

Ett allmänt tips är att försöka hitta potenser och förenklingar som gör att du kommer till ett uttryck på formen

k \cdot {(t \cdot a \pm 1)}^{n} (\mod a)

, där k är någon konstant (fyra i detta fall) och t är något heltal. Det gör att exponentuttrycket kommer att vara kongruent med

(\pm1)^n

, vilket är ett. Det är ett fantastiskt snabbt sätt att bli av med exponenter, även om det kan kräva att man bryter ut några faktorer för att få en bas på formen

a\pm1

.

I ditt exempel är ett snabbt sätt att använda denna metod att konstatera att

3^3=27=28-1=3\cdot3-1

. :) Din metod fungerar också utmärkt, men det är lätt att tappa bort någon faktor längs vägen.

Smutstvätt skrev:
Den faktorn kan du låta vara vid liv tills den mycket större faktorn kommer ned till något litet tal. Du kanske kommer ned till exempelvis $4 \cdot 6$ , som du kan multiplicera ihop och sedan beräkna modulo 7 av.

2^59 = 2x2^58 = 2x(2^2)^29 = 2x4^29 = 2x4x4^28 = 8x(4^2)^14 = 8x16^14 = 8x(16^2)^7 = 8x256^7
Ett enklare sätt att ta sig vidare från $2^{2} \cdot 2^{57}$ är att skriva om 57 till $19\cdot3$ . Då får du $4 \cdot {(2^{3})}^{19} = 4 \cdot 8^{19}$ . Vad blir det uttrycket lika med om du räknar med modulo 7?
Spoiler och tips i ett!
Ett allmänt tips är att försöka hitta potenser och förenklingar som gör att du kommer till ett uttryck på formen $k \cdot {(t \cdot a \pm 1)}^{n} (\mod a)$ , där k är någon konstant (fyra i detta fall) och t är något heltal. Det gör att exponentuttrycket kommer att vara kongruent med $(\pm1)^n$ , vilket är ett. Det är ett fantastiskt snabbt sätt att bli av med exponenter, även om det kan kräva att man bryter ut några faktorer för att få en bas på formen $a\pm1$ .

I ditt exempel är ett snabbt sätt att använda denna metod att konstatera att $3^3=27=28-1=3\cdot3-1$ . :) Din metod fungerar också utmärkt, men det är lätt att tappa bort någon faktor längs vägen.

Yes jag hamnade där men fortsatte bryta och förenkla istället för att göra kongruensen på uttrycket!

så 4x8^19 (mod 7) ≡ 4x1^19 (då 8/7 ger resten 1) = 4x1 = 4

så där är svaret 4! Har jag tänkt rätt?

Det ser bra ut!

Smutstvätt skrev:
Det ser bra ut!

Tack för hjälpen! :)

Ett systematiskt sätt som fungerar bra när modulen eller vad det heter (7 i det här fallet) är liten är att beräkna successiva potenser av basen, tills det blir 1. (Det går inte alltid, men när modulen är ett primtal går det.)

$3 \equiv 3$
$3^2 \equiv 3\cdot 3 \equiv 9 \equiv 2$
$3^3 \equiv 3\cdot 2 \equiv 6$
$3^4 \equiv 3\cdot 6 \equiv 18 \equiv 4$
$3^5 \equiv 3\cdot 4 \equiv 12 \equiv 5$
$3^6 \equiv 3\cdot 5 \equiv 15 \equiv 1$ .

Sen kan vi skriva 3¹¹⁸ som $3^{19\cdot 6 + 4} = (3^6)^{19}\cdot 3^4 \equiv 1^{19}\cdot 3^4 \equiv 3^4$ .

Svara

Visa senaste svar