17 svar

291 visningar

Insaneboy behöver inte mer hjälp

Bestöm resten då 3^179 delas med 7

Jag ska bestämma resten då 3^179 delas med 7 och jag har helt kört fast. Jag har gjort liknande uppgifter men just detta talet har gjort mig förrvirrad och jag kommer inte riktigt vidare. Jag hade verkligen uppskattat om jag hade kunnat få lite hjälp på traven.

Vi kollar resterna för potenser av 3 modulo 7:

3*3 = 9 ger resten 2
3*2 = 6
3*6 = 18 ger resten 4
3*4 = 12 ger resten 5
3*5 = 15 ger resten 1

Är du hjälpt av detta?

Nja, Jag hade liksom velat skriva (3^3)^x som då skulle bli 179 men det funkar inte riktigt.

Av det jag skrev ovan får man att 3⁶ ger resten 1.

Ja men med 3^6 kan jag inte skriva som (3^6)^x = 179 så det blir ju konstigt liksom.

Du kan skriva 3¹⁷⁹ som 3^6*29+5.

Snyggt! Hur kom du fram till det? Testade du dig fram eller?

Jag hade ju att 3⁶ ger resten 1, så jag vill uttrycka 179 som en multipel av 6 plus någonting.

Hur går jag vidare nu?

Ett sätt att uttrycka resten är med hjälp av modulär aritmetik.

Om en tal $a = n \cdot q_{a} + r_{a}$
så kan resten av $a$ vid division med $n$ uttryckas som $r_{a} = a (\mod n)$

En viktig regel inom modulär aritmetik berör resten av en produkt av två tal:
$(a \cdot b) (\mod n) = ((n \cdot q_{a} + r_{a}) \cdot b) (\mod n) = (n \cdot (q_{a} \cdot b) + (r_{a} \cdot b)) (\mod n) = (r_{a} \cdot b) (\mod n) = ((a (\mod n)) \cdot b) (\mod n)$

Man kan alltså ersätta ett tal $a$ med sin rest $(a (\mod n))$
och ändå få rätt svar för resten av produkten.
Detta är väldigt användbart om talet är stort men resten är liten.

I ditt problem är vi intresserade av $x = 3^{179} (\mod 7)$

Potensen kan vi dela upp som en produkt enligt följande:
$3^{179} = 3^{k} \cdot 3^{179 - k}$ för något tal $k$

Enligt regeln ovan betyder det att:
$x = ((3^{k} (\mod 7)) \cdot 3^{179 - k}) (\mod 7)$

Låt oss därför undersöka $3^{k} (\mod 7)$ för några olika värden av $k$ .
$k = 1 \Rightarrow 3^{k} (\mod 7) = 3 (\mod 7) = 3$
$k = 2 \Rightarrow 3^{k} (\mod 7) = 9 (\mod 7) = 2$
$k = 3 \Rightarrow 3^{k} (\mod 7) = 27 (\mod 7) = 6$
$k = 4 \Rightarrow 3^{k} (\mod 7) = 81 (\mod 7) = 4$
$k = 5 \Rightarrow 3^{k} (\mod 7) = 243 (\mod 7) = 5$
$k = 6 \Rightarrow 3^{k} (\mod 7) = 729 (\mod 7) = 1$

Att resten blir $1$ när $k = 6$ är extra intressant.
Sätter vi in detta i uttrycket för $x$ får vi att:
$x = ((3^{6} (\mod 7)) \cdot 3^{179 - 6}) (\mod 7) = (1 \cdot 3^{173}) (\mod 7) = 3^{173} (\mod 7)$

Resten är alltså opåverkad av att vi minskade exponenten med 6.
Men samma resonemang kan användas igen på det nya uttrycket för $x$ .
Så länge exponenten är större än eller lika med 6 kan vi minska den med 6 utan att $x$ påverkas.

Vi väljer därför att skriva om exponenten så här: $179 = 6 q + r$ .
Sätter vi in detta i uttrycket för $x$ får vi:
$x = 3^{6 q + r} (\mod 7) = (\underset{q gånger}{\underset{⏟}{3^{6} \cdot \dots \cdot 3^{6}}} \cdot 3^{r}) (\mod 7) = (\underset{q gånger}{\underset{⏟}{(3^{6} (\mod 7)) \cdot \dots \cdot (3^{6} (\mod 7))}} \cdot 3^{r}) (\mod 7) = (1^{q} \cdot 3^{r}) (\mod 7) = 3^{r} (\mod 7)$

Det enda som återstår är att räkna ut $r$ , resten då 179 delas med 6,
och sätta in det i det sista uttrycket för $x$ .

Jag får att R = 5 , så ska jag då bara få 3^5 ( mod 7) som svar då?

3^5= (3^2)^2.5 ???

9^2.5 mod 7

2^2.5 mod 7

Det blir ju fel

$r = 5$ är rätt.

$\Rightarrow 3^{r} = 3^{5} = 243$

Vad är resten av 243 delat med 7?

Jag löste det, stort tack! Det enda jag undrar är när du skriver exponenten som 3^179 = 3^6q+r borde det inte vara 3^173=3^6q+r. Svaret blev visserligen samma pga kongruensen men undrar bara.

Steget där jag visade att resten för 3^179 var samma som resten för 3^173
var mest menad som ett exempel på varför den här metoden fungerar.

När man blir mer van vid den här typen av beräkningar inser man från början
att man först behöver hitta en exponent där resten blir 1 (i detta fallet 6)
och sedan beräkna resten av problemets exponent delat med detta.

Att då först reducera exponenten med en enda 6:a
blir lika överflödigt som mellanstegen i följande beräkning:
$179 - 6 \cdot 25 = (179 - 6) - 6 \cdot (25 - 1) = 173 - 6 \cdot 24 = 5$

En alternativ lösning kan vara den här:

1) vi letar efter ett tal som ger rest 1, 0 eller -1 vid division med 7.

2) Det talet vill vi att ska vara 3^x. 3, 9, 27. Oj här stöter vi på $27 \equiv - 1$ (mod7)

3) $3^{179} = 3^{2} \cdot 3^{177} = 3^{2} {(3^{3})}^{59} = 9 \cdot 27^{59}$ (För att få fram 59 dividerade jag 179 med 3 och fick 59 och rest 2).

4) $9 \cdot 27^{59} \equiv 2 \cdot {(- 1)}^{59}$ och vi får $2 \cdot (- 1) = - 2$

5) $- 2 \equiv 5$ (mod7)

Så resten är 5.

Laguna skrev:
Vi kollar resterna för potenser av 3 modulo 7:

3*3 = 9 ger resten 2
3*2 = 6
3*6 = 18 ger resten 4
3*4 = 12 ger resten 5
3*5 = 15 ger resten 1

Av det får man att 3⁶ ger resten 1.

Det här har jag grunnat på i flera dagar.
Hur är tankegången?
Jag ser att $3^{2} = 9 \equiv 2$ (mod7), vilket då stämmer med din första rad.

$3^{3} = 3^{1} \cdot 3^{2} \equiv 3 \cdot 2 = 6$ (mod7), vilket stämmer med din andra rad.

Så kan vi fortsätta och kommer till sista raden som då motsvarar 3⁶
Är det så du tänker?

Det som också förvirrar mig är sambandet mellan dina rader. Förmodligen en detalj som är solklar när man kan den, men av någon anledning ser jag inte det uppenbara.
Första raden ger resten 2 som du sedan multiplicerar med 3.
Andra raden ger resten 6 som du sedan multiplicerar med 3 osv.
Det ger rätt resultat ser jag, men tror du att du kan utveckla din tankegång litet?

Just precis. Första raden ger 3². Sen tar jag det gånger 3 så jag får 3³. När jag har fått resultatet 1 kan jag sluta för då blir det 3 igen på nästa rad.

Samma sak som i inlägg #10, alltså.

Laguna skrev:
Just precis. Första raden ger 3². Sen tar jag det gånger 3 så jag får 3³. När jag har fått resultatet 1 kan jag sluta för då blir det 3 igen på nästa rad.

Samma sak som i inlägg #10, alltså.

OK. Då är jag med på din lösning. Inlägg #10 får jag nog vänta med ett tag. Jag måste nog stanna upp ett tag och gå vidare med matematik 5, men det blev en lärorik tråd för mig. Tack så länge för mig.

Svara

Visa senaste svar