Visa att 5^2019 är jämnt delbart med 39

Fermats lilla sats borde gå att använda, men var kommer 47 ifrån? Det borde väl bli:

$5^{38}$ i modulo 39 ger resten 1. 

?

Smutstvätt skrev:

Fermats lilla sats borde gå att använda, men var kommer 47 ifrån? Det borde väl bli:

$5^{38}$ i modulo 39 ger resten 1. 

?

Ja asså jag flyttade 8an från vänsterledet till högerledet. Men det var nog konstig approach. Ja du har helt rätt. Dåfår vi 1-8 modulo 39. Nu vet jag ej var 2019 exponenten försvann. Den ska vi väl använda eller? 

destiny99 skrev:

Smutstvätt skrev:

Fermats lilla sats borde gå att använda, men var kommer 47 ifrån? Det borde väl bli:

Visa föregående citat

$5^{38}$ i modulo 39 ger resten 1. 

?

Ja asså jag flyttade 8an från vänsterledet till högerledet. Men det var nog konstig approach.

Aha, då förstår jag! Det blir lite knasigt om du gör så tyvärr. Det vi fått från påståendet är att $5^{2019}-8=0 (\mathrm{mod} 39)$, så om du flyttar åttan till högerledet förändrar det inte mod 39. Det blir bara $5^{2019}=8 (\mathrm{mod} 39)$. Men, att använda Fermats lilla sats är helt rätt väg att gå!

Ja du har helt rätt. Dåfår vi 1-8 modulo 39. Nu vet jag ej var 2019 exponenten försvann. Den ska vi väl använda eller? 

Vi får från Fermats lilla sats att $5^38$ är kongruent med 1 (mod 39), så vi behöver arbeta med 2019-exponenten, så att den blir något som utgår från 38. 

Tänk på hur du kan beräkna $2^{48} (\mathrm{mod} 7)$ genom att skriva om $2^48$ till ${\left(2^3\right)}^{16}=8^{16}$. Det går att göra något liknande här också. :)

Smutstvätt skrev:

destiny99 skrev:

Visa föregående citat

Smutstvätt skrev:

Fermats lilla sats borde gå att använda, men var kommer 47 ifrån? Det borde väl bli:

$5^{38}$ i modulo 39 ger resten 1. 

?

Ja asså jag flyttade 8an från vänsterledet till högerledet. Men det var nog konstig approach.

Aha, då förstår jag! Det blir lite knasigt om du gör så tyvärr. Det vi fått från påståendet är att $5^{2019}-8=0 (\mathrm{mod} 39)$, så om du flyttar åttan till högerledet förändrar det inte mod 39. Det blir bara $5^{2019}=8 (\mathrm{mod} 39)$. Men, att använda Fermats lilla sats är helt rätt väg att gå!

Ja du har helt rätt. Dåfår vi 1-8 modulo 39. Nu vet jag ej var 2019 exponenten försvann. Den ska vi väl använda eller? 

Vi får från Fermats lilla sats att $5^38$ är kongruent med 1 (mod 39), så vi behöver arbeta med 2019-exponenten, så att den blir något som utgår från 38. 

Tänk på hur du kan beräkna $2^{48} (\mathrm{mod} 7)$ genom att skriva om $2^48$ till ${\left(2^3\right)}^{16}=8^{16}$. Det går att göra något liknande här också. :)

Okej nu är det väldigt rörig. Jag har jätte svårt att hänga med i alla snabba steg du gör. Så vi får börja från början då jag ej är så snabb på att uppfatta saker fort. 

Jag börjar med att skriva som 5^2019 konguent med 8mod(39)

Kan man utnyttja att 5^2019 konguent med 3 mod 39 ? För vi vet att 8=5*1+3

Det är inte så konstigt om du blir förvirrad, för jag har räknat fel... 

Missade helt att 39 inte är ett primtal. :( Då kan vi inte använda Fermats lilla sats, utan vi behöver använda den generaliserade varianten, Eulers sats. Den säger att $a^{\phi \left(n\right)}\equiv 1 (\mathrm{mod} n)$, där $\varphi \left(n\right)$ är Eulers fi-funktion. Denna sats gäller för alla tal a och n som är relativt prima. 

$\varphi \left(39\right)$ är lika med antalet positiva heltal som är mindre än 39, som inte är relativt prima med 39. Det finns 24 stycken sådana, tal, så $\varphi \left(39\right)=24$. 

Detta ger oss att $5^{24} {\equiv }_{39}1$. 

Nu vill vi bli av med så stora delar av exponenten 2019 som möjligt. Tyvärr är inte 2019 delbart med 24, men vi kan skriva 2019 som $24\cdot k+m$, för några heltal k och m. Detta är bra, då det innebär att vi kan skriva om $5^{2019}$ till $5^{24k+m}={\left(5^{24}\right)}^k·5^m$. Faktorn ${\left(5^{24}\right)}^k$ kan, enligt Eulers sats, förenklas till $1^k$, så då har vi bara faktorn $5^m$ kvar. Därför vill vi gärna maximera k och minimera m. 

Det maximala heltalsvärdet på k ger oss omskrivingen $2019=24\cdot84+3$. 

Detta kan vi sätta in istället för exponenten 2019, och då få: 

$5^{2019}=\underset{\equiv 1^{84}\equiv 1}{\underbrace{{\left(5^{24}\right)}^{84}}}·5^3\equiv 5^3 (\mathrm{mod} 39)$

Då kvarstår bara $5^3$. Vad är $5^3 (\mathrm{mod} 39)$? :)

Smutstvätt skrev:

Det är inte så konstigt om du blir förvirrad, för jag har räknat fel... 

Missade helt att 39 inte är ett primtal. :( Då kan vi inte använda Fermats lilla sats, utan vi behöver använda den generaliserade varianten, Eulers sats. Den säger att $a^{\phi \left(n\right)}\equiv 1 (\mathrm{mod} n)$, där $\varphi \left(n\right)$ är Eulers fi-funktion. Denna sats gäller för alla tal a och n som är relativt prima. 

$\varphi \left(39\right)$ är lika med antalet positiva heltal som är mindre än 39, som inte är relativt prima med 39. Det finns 24 stycken sådana, tal, så $\varphi \left(39\right)=24$. 

Detta ger oss att $5^{24} {\equiv }_{39}1$. 

Nu vill vi bli av med så stora delar av exponenten 2019 som möjligt. Tyvärr är inte 2019 delbart med 24, men vi kan skriva 2019 som $24\cdot k+m$, för några heltal k och m. Detta är bra, då det innebär att vi kan skriva om $5^{2019}$ till $5^{24k+m}={\left(5^{24}\right)}^k·5^m$. Faktorn ${\left(5^{24}\right)}^k$ kan, enligt Eulers sats, förenklas till $1^k$, så då har vi bara faktorn $5^m$ kvar. Därför vill vi gärna maximera k och minimera m. 

Det maximala heltalsvärdet på k ger oss omskrivingen $2019=24\cdot84+3$. 

Detta kan vi sätta in istället för exponenten 2019, och då få: 

$5^{2019}=\underset{\equiv 1^{84}\equiv 1}{\underbrace{{\left(5^{24}\right)}^{84}}}·5^3\equiv 5^3 (\mathrm{mod} 39)$

Då kvarstår bara $5^3$. Vad är $5^3 (\mathrm{mod} 39)$? :)

Jag  hänger ej med på alla steg nu igen och jag känner ej till eulers sats. 

Om man vill använda Fermats lilla sats behöver man ett primtal i exponenten. Exponenten 2019 består av två primtal så här:

$2019=673\cdot 3$

Om man använder den uppdelningen av talet 2019 får man

$5^{2019}=(5^{3})^{673}$

Vad är det kongruent med enligt Fermats lilla sats?

Edit: !!!OBS!! Fermats lilla sats kräver primtal! Använd istället

$a\equiv b \ \pmod{m} \iff a^k\equiv b^k \ \pmod{m}$

D4NIEL skrev:

Om man vill använda Fermats lilla sats behöver man ett primtal i exponenten. Exponenten 2019 består av två primtal så här:

$2019=673\cdot 3$

Om man använder den uppdelningen av talet 2019 får man

$5^{2019}=(5^{3})^{673}$

Vad är det kongruent med enligt Fermats lilla sats?

Aa okej men är ej 39 primtal?  39=13*3

5^(673*3) = 8mod39? Jag  förstår ej formel utnyttjande här.

Nej, du har helt rätt, 39 är inte ett primtal. Fermats sats blir krånglig att använda här.

Använd $a\equiv b\ \pmod{m}  \equiv a^k\equiv b^k\ \pmod{m}$ istället om ni lärt er det.

Om ni måste använda Fermats lilla sats får vi skriva om det.

D4NIEL skrev:

Nej, du har helt rätt, 39 är inte ett primtal. Fermats sats blir krånglig att använda här.

Använd $a\equiv b\ \pmod{m}  \equiv a^k\equiv b^k\ \pmod{m}$ istället om ni lärt er det.

Om ni måste använda Fermats lilla sats får vi skriva om det.

Jag menar att 39 är primtal för det består av 13 och 3. Men du säger att det ej är det? Jag förstår ej varför.

Jag förstår ej hur du menar att jag ska använda a^k=b^k mod(m). Det har jag aldrig sett

Ett primtal får bara vara delbart med sig själv och 1.

39 är delbart med 3 och är därför inte ett primtal. Är du med?

Det är lite svårt att veta vad ni lärt er för metoder, hittills har vi uteslutet Eulerfunktionen och modulär exponentialkompabilitet.

Har du något formelblad med modulär aritmetik ni gått igenom kanske?

D4NIEL skrev:

Ett primtal får bara vara delbart med sig själv och 1.

39 är delbart med 3 och är därför inte ett primtal. Är du med?

Det är lite svårt att veta vad ni lärt er för metoder, hittills har vi uteslutet Eulerfunktionen och modulär exponentialkompabilitet.

Har du något formelblad med modulär aritmetik ni gått igenom kanske?

Aa nu är jag med. 

Nej tyvärr är formelblad ej tillåtet på högskolan inför tentan. Ja vi har lärt oss räkneregler inom konguens och sånt,men jag har ej allt i huvudet. Sen fermats sats lärde vi oss. 

Då kan du göra en fattigmans-variant av Smutstvätts förslag.

Vi har en stor mängd 5:or som multipliceras med varandra. Vi kan börja med att försöka hitta en variant $5^m$ som lämnar resten 1. Vi vill alltså hitta ett $m$ så att $5^m\equiv 1\ \pmod{39}$. Det kan hända att ni lärt er en metod för att lösa den diofantiska ekvationen, annars får man prova sig fram, som när man gissar rötter ungefär.

$5^m-39\cdot k = 1$

$5\cdot y-39\cdot k = 1$ (Diofantisk ekvation)

För stora tal är det svårt att prova sig fram, men man kan testa $m=3$ och $m=4$. Man kan också lösa den diofantiska ekvationen.

För $m=4$ får vi

$5^4-39\cdot k = 1\Rightarrow k=16$

Alltså har vi

$5^4\equiv 1\ \pmod{39}$

Är du med så långt?

D4NIEL skrev:

Då kan du göra en fattigmans-variant av Smutstvätts förslag.

Vi har en stor mängd 5:or som multipliceras med varandra. Vi kan börja med att försöka hitta en variant $5^m$ som lämnar resten 1. Vi vill alltså hitta ett $m$ så att $5^m\equiv 1\ \pmod{39}$. Det kan hända att ni lärt er en metod för att lösa den diofantiska ekvationen, annars får man prova sig fram, som när man gissar rötter ungefär.

$5^m-39\cdot k = 1$

$5\cdot y-39\cdot k = 1$ (Diofantisk ekvation)

För stora tal är det svårt att prova sig fram, men man kan testa $m=3$ och $m=4$. Man kan också lösa den diofantiska ekvationen.

För $m=4$ får vi

$5^4-39\cdot k = 1\Rightarrow k=16$

Alltså har vi

$5^4\equiv 1\ \pmod{39}$

Är du med så långt?

Men du började ju förut med 5^(3*673)=8 mod(39) . Kan man ej tänka 5^3 är konguent med 1 mod(39) pga fermats lilla sats. 

Då får vi 1^673 =8mod(39)

Nej, för att få använda Fermats lilla sats måste delaren vara ett primtal och $39=3\cdot 13$ är inte ett primtal eftersom 39 är delbart med 3.

Dessutom är $5^3\equiv 8\ \pmod{39}$. Min första ansats bygger på en omskrivning av Fermats sats ni inte gått igenom.

Jag tror det är lättare för dig att lösa den diofantiska ekvationen eller pröva dig fram till en lösning av $5^m\equiv 1\ \pmod{39}$

När du har löst det vet du att $5^4\equiv 1 \ \pmod{39}$ och kan skriva om talet $5^{2019}$ som

$5^{2019}=(5^4)^{504} \cdot 5^3$

D4NIEL skrev:

Nej, för att få använda Fermats lilla sats måste delaren vara ett primtal och $39=3\cdot 13$ är inte ett primtal eftersom 39 är delbart med 3.

Dessutom är $5^3\equiv 8\ \pmod{39}$. Min första ansats bygger på en omskrivning av Fermats sats ni inte gått igenom.

Jag tror det är lättare för dig att lösa den diofantiska ekvationen eller pröva dig fram till en lösning av $5^m\equiv 1\ \pmod{39}$

När du har löst det vet du att $5^4\equiv 1 \ \pmod{39}$ och kan skriva om talet $5^{2019}$ som

$5^{2019}=(5^4)^{504} \cdot 5^3$

 

Jag förstår verkligen ej varför vi ska göra diofantisk lösning.  Dessutom förstår jag ej varför du skriver 5^m konguent med 1 mod39 när du precis skrev att 39 inte är primtal. Ursäkta men jag är super förvirrad..

Här är facits lösningsförslag. Kan vi gå igenom? Var kommer (-1) ifrån? De har 0 lite överallt också vilket jag absolut ej är med på.

Ja, facit använder den omskrivning av Fermats sats som vi pratade om tidigare. Den bygger på att man kan dela upp talet i primtalsfaktorer och sedan visa delbarhet i varje faktor för sig (trodde inte ni hade lärt er den, man brukar inte lära sig det på gymnasiet).

Först ska vi då visa att $5^{2019}-8\equiv 0\ \pmod{3}$

Enklare ansats (jämför inlägg #9, där jag skissade en variant på denna):

Är du med på att $5\equiv 2 \equiv-1\ \pmod{3}$?

Vad är alltså $5^{2019}\equiv ?\ \pmod{3}$

D4NIEL skrev:

Ja, facit använder den omskrivning av Fermats sats som vi pratade om tidigare. Den bygger på att man kan dela upp talet i primtalsfaktorer och sedan visa delbarhet i varje faktor för sig (trodde inte ni hade lärt er den, man brukar inte lära sig det på gymnasiet).

Först ska vi då visa att $5^{2019}-8\equiv 0\ \pmod{3}$

Enklare ansats (jämför inlägg #9, där jag skissade en variant på denna):

Är du med på att $5\equiv 2 \equiv-1\ \pmod{3}$?

Vad är alltså $5^{2019}\equiv ?\ \pmod{3}$

 

Varför står det 0 framför mod3?

Nej jag är ej med på det 5≡2≡−1 (mod3).

0 betyder att talet inte lämnar någon rest, t.ex. är

$6 \equiv 0 \ \pmod{3}$

Eftersom $6$ är jämnt delbart med $3$ och lämnar resten $0$.

När vi säger $2^{2019}-8 \equiv 0 \ \pmod{3}$ menar vi alltså att talet ska lämna resten $0$ vid division med $3$, dvs vara jämnt delbart med $3$.

$5 \equiv 2 \ \pmod{3}$ eftersom vi kan dela $5$ med $3$ en gång och det lämnar resten $2$. Är du med?

D4NIEL skrev:

0 betyder att talet inte lämnar någon rest, t.ex. är

$6 \equiv 0 \ \pmod{3}$

Eftersom $6$ är jämnt delbart med $3$ och lämnar resten $0$.

När vi säger $2^{2019}-8 \equiv 0 \ \pmod{3}$ menar vi alltså att talet ska lämna resten $0$ vid division med $3$, dvs vara jämnt delbart med $3$.

$5 \equiv 2 \ \pmod{3}$ eftersom vi kan dela $5$ med $3$ en gång och det lämnar resten $2$. Är du med?

Aa jag är med ungefär.

"När vi säger 2^2019−8≡0 mod3  menar vi alltså att talet ska lämna resten 00 vid division med 33, dvs vara jämnt delbart med "

Menar du ej 5^2019?

Ursprungsuppgiften är att visa att talet $(5^{2019}-8)$ är jämnt delbart med 39. Det betyder att vi vill visa att

$(5^{2019}-8) \equiv 0 \ \pmod{39}$

Genom att tillämpa en icke-trivial följdsats som säger att det är tillåtet att dela upp talet i faktorer  kan vi påstå att det är ekvivalent med att visa två saker:

1) $(5^{2019}-8) \equiv 0 \ \pmod{3}$

2) $(5^{2019}-8) \equiv 0 \ \pmod{13}$

Vi börjar med att försöka visa 1). Låt oss studera endast $5^{2019}$

Eftersom $5\equiv 2 \equiv -1 \ \pmod{3}$ kan vi direkt säga att

$5^{2019}\equiv (-1)^{2019} \equiv -1 \ \pmod{3}$

D4NIEL skrev:

Ursprungsuppgiften är att visa att talet $(5^{2019}-8)$ är jämnt delbart med 39. Det betyder att vi vill visa att

$(5^{2019}-8) \equiv 0 \ \pmod{39}$

Genom att tillämpa en icke-trivial följdsats som säger att det är tillåtet att dela upp talet i faktorer  kan vi påstå att det är ekvivalent med att visa två saker:

1) $(5^{2019}-8) \equiv 0 \ \pmod{3}$

2) $(5^{2019}-8) \equiv 0 \ \pmod{13}$

Vi börjar med att försöka visa 1). Låt oss studera endast $5^{2019}$

Eftersom $5\equiv 2 \equiv -1 \ \pmod{3}$ kan vi direkt säga att

$5^{2019}\equiv (-1)^{2019} \equiv -1 \ \pmod{3}$

Jag förstår ej det här steget

Eftersom 5≡2≡−1 (mod3) kan vi direkt säga att

5^2019≡(−1)^2019≡−1 (mod3).  Jag förstår ej hur 5 är konguent med 2 som i sin tur konguent med -1

5≡2 då 5=1*3+2

samt

5≡-1 då 5=2*3-1