Oppgave fra abelkonkurransen:
Hva er siste siffer i [tex]17^{1996}[/tex]
Her tenkte jeg følgende for å finne et mønster:
[tex]17^{1}=17[/tex]. Siste siffer er 7.
[tex]17^{2}=289[/tex]. Siste siffer er 9.
[tex]17^{3}=4913[/tex]. Siste siffer er 3
[tex]17^{4}=83521[/tex]. Siste siffer er 1
[tex]17^{5}=1419857[/tex]. Siste siffer er 7
Mønsteret er altså [tex]7,9,3,1...[/tex] og siden [tex]\frac{1996}{4}=499 \in \mathbb{N}[/tex]
Så blir siste siffer [tex]1[/tex]. Er dette korrekt?
Finnes det en enklere måte?
Siste siffer i et tall.
Moderatorer: Aleks855, Gustav, Nebuchadnezzar, Janhaa, DennisChristensen, Emilga
-
- Grothendieck
- Innlegg: 826
- Registrert: 09/02-2015 23:28
- Sted: Oslo
Vi vet at $17^2 = 289 = 9 = -1 \text{ }(\text{mod }10),$ så $$17^{1996} = \left(17^2\right)^{998} = (-1)^{998} = 1 \text{ }(\text{mod }10).$$ Altså er siste siffer i $17^{1996}$ lik $1$.Gjest skrev:Oppgave fra abelkonkurransen:
Hva er siste siffer i [tex]17^{1996}[/tex]
Her tenkte jeg følgende for å finne et mønster:
[tex]17^{1}=17[/tex]. Siste siffer er 7.
[tex]17^{2}=289[/tex]. Siste siffer er 9.
[tex]17^{3}=4913[/tex]. Siste siffer er 3
[tex]17^{4}=83521[/tex]. Siste siffer er 1
[tex]17^{5}=1419857[/tex]. Siste siffer er 7
Mønsteret er altså [tex]7,9,3,1...[/tex] og siden [tex]\frac{1996}{4}=499 \in \mathbb{N}[/tex]
Så blir siste siffer [tex]1[/tex]. Er dette korrekt?
Finnes det en enklere måte?
Hei, hva betyr mod? Jeg har ikke så mye erfaring utenom 1T, men fremgangsmåten "min" fungerte tydeligvis?DennisChristensen skrev:
Vi vet at $17^2 = 289 = 9 = -1 \text{ }(\text{mod }10),$ så $$17^{1996} = \left(17^2\right)^{998} = (-1)^{998} = 1 \text{ }(\text{mod }10).$$ Altså er siste siffer i $17^{1996}$ lik $1$.
Når to tall $a, b$multipliseres, er det siste sifferet i produktet det samme som det siste sifferet i produktet til det siste sifferet til $a$ ganget med siste sifferet til $b$ (hvorfor?). Dermed betyr dette at man bare trenger å gange de nye siste sifrene sammen for å det nye siste sifferet, noe som reduserer arbeidet for å finne mønstret netydelig:
$7=7$
$7\cdot7=49$
$9\cdot7=63$
$3\cdot7=21$
$1\cdot7=1$
Man kan selvsagt også bruke moduloregning her for å forenkle arbeidet bitte litt mer, som nevnt over. Men tankegangen (som du også brukte) er essensielt det samme.
$7=7$
$7\cdot7=49$
$9\cdot7=63$
$3\cdot7=21$
$1\cdot7=1$
Man kan selvsagt også bruke moduloregning her for å forenkle arbeidet bitte litt mer, som nevnt over. Men tankegangen (som du også brukte) er essensielt det samme.
Rettet opp på noe der, kan ikke edite posts ved dette tidspunktet, beklager for spamerikmma skrev: redigert
Når to tall $a, b$ multipliseres, er det siste sifferet i produktet det samme som det siste sifferet i produktet til det siste sifferet til $a$ ganget med siste sifferet til $b$ (hvorfor?). Dermed betyr dette at man bare trenger å gange de nye siste sifrene sammen for å det nye siste sifferet, noe som reduserer arbeidet for å finne mønstret betydelig:
$7=7$
$7\cdot7=49$
$9\cdot7=63$
$3\cdot7=21$
$1\cdot7=7$
Man kan selvsagt også bruke moduloregning her for å forenkle arbeidet bitte litt mer, som nevnt over. Men tankegangen (som du også brukte) er essensielt det samme.
Aha, det gir litt mer mening. Så hvis vi har to tall [tex]10n+a[/tex] og [tex]10m+b[/tex] så vil det siste tallet alltid i produktet alltid være [tex]ab[/tex] fordi [tex]\left ( 10n+a \right ) *\left ( 10m+b \right )=100nm+10nb+10am+ab=10(10nm+nb+am)+ab[/tex]erikmma skrev:Rettet opp på noe der, kan ikke edite posts ved dette tidspunktet, beklager for spamerikmma skrev: redigert
Når to tall $a, b$ multipliseres, er det siste sifferet i produktet det samme som det siste sifferet i produktet til det siste sifferet til $a$ ganget med siste sifferet til $b$ (hvorfor?). Dermed betyr dette at man bare trenger å gange de nye siste sifrene sammen for å det nye siste sifferet, noe som reduserer arbeidet for å finne mønstret betydelig:
$7=7$
$7\cdot7=49$
$9\cdot7=63$
$3\cdot7=21$
$1\cdot7=7$
Man kan selvsagt også bruke moduloregning her for å forenkle arbeidet bitte litt mer, som nevnt over. Men tankegangen (som du også brukte) er essensielt det samme.
Hva med det nest siste tallet, eller det fjerde siste tallet? Finnes det en tilsvarende fremgangsmåte?
Enklere måte? Ja, det finnes, bruk en avansert kalkulator så ser du siste siffer.Gjest skrev:Oppgave fra abelkonkurransen:
Hva er siste siffer i [tex]17^{1996}[/tex]
Her tenkte jeg følgende for å finne et mønster:
[tex]17^{1}=17[/tex]. Siste siffer er 7.
[tex]17^{2}=289[/tex]. Siste siffer er 9.
[tex]17^{3}=4913[/tex]. Siste siffer er 3
[tex]17^{4}=83521[/tex]. Siste siffer er 1
[tex]17^{5}=1419857[/tex]. Siste siffer er 7
Mønsteret er altså [tex]7,9,3,1...[/tex] og siden [tex]\frac{1996}{4}=499 \in \mathbb{N}[/tex]
Så blir siste siffer [tex]1[/tex]. Er dette korrekt?
Finnes det en enklere måte?
Gjest skrev: Enklere måte? Ja, det finnes, bruk en avansert kalkulator så ser du siste siffer.
Hehe, skulle gjerne hvis det var tillat under slike konkurranser.
mod står for modulo. Det er "resten" ved divisjon.Gjest skrev:Hei, hva betyr mod? Jeg har ikke så mye erfaring utenom 1T, men fremgangsmåten "min" fungerte tydeligvis?DennisChristensen skrev:
Vi vet at $17^2 = 289 = 9 = -1 \text{ }(\text{mod }10),$ så $$17^{1996} = \left(17^2\right)^{998} = (-1)^{998} = 1 \text{ }(\text{mod }10).$$ Altså er siste siffer i $17^{1996}$ lik $1$.
Eksempel: Hvis vi betrakter divisjonen 23/7, så ender vi opp med 2 i rest. Dette er fordi 7*3 = 21, og da står vi igjen med en rest på 23-21 = 2. Vi ser også dette ved at $23 = (3\cdot7) + \underline2$
Dette skriver vi som at $23 \equiv 2 \pmod 7$.
Grunnen til at det brukes i slike oppgaver, er fordi hvis du betrakter et tall $\pmod{10}$ så vil dette gi siste siffer i tallet.
Eksempel: 33 har 3 som siste siffer. Dette gjenspeiles av at $33 - (3\cdot10) = 33-30 = 3$ som betyr at $33 \equiv 3 \pmod{10}$.
Aleks855 skrev: mod står for modulo. Det er "resten" ved divisjon.
Eksempel: Hvis vi betrakter divisjonen 23/7, så ender vi opp med 2 i rest. Dette er fordi 7*3 = 21, og da står vi igjen med en rest på 23-21 = 2. Vi ser også dette ved at $23 = (3\cdot7) + \underline2$
Dette skriver vi som at $23 \equiv 2 \pmod 7$.
Grunnen til at det brukes i slike oppgaver, er fordi hvis du betrakter et tall $\pmod{10}$ så vil dette gi siste siffer i tallet.
Eksempel: 33 har 3 som siste siffer. Dette gjenspeiles av at $33 - (3\cdot10) = 33-30 = 3$ som betyr at $33 \equiv 3 \pmod{10}$.
Takk for et oppklarende svar! Lærte jammen noe nytt i dag.
Hva er poenget/bruksområdet med moduloregning? Kan du komme med noen oppgaver/temaer hvor det brukes?
DennisChristensen skrev:
Vi vet at $17^2 = 289 = 9 = -1 \text{ }(\text{mod }10),$ så $$17^{1996} = \left(17^2\right)^{998} = (-1)^{998} = 1 \text{ }(\text{mod }10).$$ Altså er siste siffer i $17^{1996}$ lik $1$.
Dette forstår jeg ikke helt. [tex]9=-1(mod10)[/tex] Hvordan kan resten være [tex]-1[/tex] etter divisjon?
-
- Grothendieck
- Innlegg: 826
- Registrert: 09/02-2015 23:28
- Sted: Oslo
Aleks855 sin forklaring gir en god intuisjon for forståelsen av modulær likhet, men ingen fullstendig definisjon. Helt presist sier vi at $a \equiv b \text{ }(\text{mod } c)$ hvis det finnes et heltall $n\in\mathbb{Z}$ slik at $a = nc + b$. Dermed ser vi at $9 \equiv -1\text{ }(\text{mod }10),$ ettersom $9 = 1\cdot 10 - 1.$Gjest skrev:Aleks855 skrev: mod står for modulo. Det er "resten" ved divisjon.
Eksempel: Hvis vi betrakter divisjonen 23/7, så ender vi opp med 2 i rest. Dette er fordi 7*3 = 21, og da står vi igjen med en rest på 23-21 = 2. Vi ser også dette ved at $23 = (3\cdot7) + \underline2$
Dette skriver vi som at $23 \equiv 2 \pmod 7$.
Grunnen til at det brukes i slike oppgaver, er fordi hvis du betrakter et tall $\pmod{10}$ så vil dette gi siste siffer i tallet.
Eksempel: 33 har 3 som siste siffer. Dette gjenspeiles av at $33 - (3\cdot10) = 33-30 = 3$ som betyr at $33 \equiv 3 \pmod{10}$.
Takk for et oppklarende svar! Lærte jammen noe nytt i dag.
Hva er poenget/bruksområdet med moduloregning? Kan du komme med noen oppgaver/temaer hvor det brukes?
DennisChristensen skrev:
Vi vet at $17^2 = 289 = 9 = -1 \text{ }(\text{mod }10),$ så $$17^{1996} = \left(17^2\right)^{998} = (-1)^{998} = 1 \text{ }(\text{mod }10).$$ Altså er siste siffer i $17^{1996}$ lik $1$.
Dette forstår jeg ikke helt. [tex]9=-1(mod10)[/tex] Hvordan kan resten være [tex]-1[/tex] etter divisjon?
Modulær aritmetikk dukker opp i flere matematiske kontekster, men er helt essensielt i blant annet tallteori, kryptografi og abstrakt algebra. Du kan lese faget Matematikk X på vgs for å bli med kjent med modulær aritmetikk og også se noen elementære eksempler på bruksområder innen kryptografi. Dersom du studerer matematikk videre på universitetsnivå vil du bruke modulær aritmetikk en hel del innen algebra-fagene.
DennisChristensen skrev:
Aleks855 sin forklaring gir en god intuisjon for forståelsen av modulær likhet, men ingen fullstendig definisjon. Helt presist sier vi at $a \equiv b \text{ }(\text{mod } c)$ hvis det finnes et heltall $n\in\mathbb{Z}$ slik at $a = nc + b$. Dermed ser vi at $9 \equiv -1\text{ }(\text{mod }10),$ ettersom $9 = 1\cdot 10 - 1.$
Modulær aritmetikk dukker opp i flere matematiske kontekster, men er helt essensielt i blant annet tallteori, kryptografi og abstrakt algebra. Du kan lese faget Matematikk X på vgs for å bli med kjent med modulær aritmetikk og også se noen elementære eksempler på bruksområder innen kryptografi. Dersom du studerer matematikk videre på universitetsnivå vil du bruke modulær aritmetikk en hel del innen algebra-fagene.
Kult! Synes det var interessant mest mulig pga. overførbarheten til abelkonkurransen som jeg skal delta i år.
En ting til hvorfor tar du modulo [tex]10[/tex] når du finner siste siffer i et tall? Tallet må vel da ha 2 og 5 som faktor?
Ville det fungert på å finne det siste sifferet på dette; [tex]453!^{88}[/tex] ?
-
- Grothendieck
- Innlegg: 826
- Registrert: 09/02-2015 23:28
- Sted: Oslo
Det kommer av at det siste sifferet til et tall i titallssystemet alltid vil være lik resten når vi dividerer tallet på $10$: La $x\in\mathbb{N}$ være et heltall besteående av sifrene $x = a_n a_{n-1} \dots a_0,$ der $ a_n \neq 0$. Da har vi at $$x = 10^na_n + 10^{n-1}a_{n-1} + \dots + 10a_1 + a_0 = 10\left(10^{n-1}a_n + 10^{n-2}a_{n-1} + \dots + a_1\right) + a_0,$$ så $$x \equiv a_0 \text{ }(\text{mod }10).$$Gjest skrev:En ting til hvorfor tar du modulo [tex]10[/tex] når du finner siste siffer i et tall? Tallet må vel da ha 2 og 5 som faktor?
En ser nok dette fenomenet enklest ved å undersøke enkle eksempler.
$$23 = 2\cdot 10 + 3,\text{ så }23\equiv 3\text{ }(\text{mod }10);$$
$$1009 = 1\cdot 10^3 + 0\cdot 10^2 + 0\cdot 10 + 9,\text{ så }1009 \equiv 9\text{ }(\text{mod }10).$$
Her trengs ikke modulær aritmetikk. Ettersom $453 \geq 5$, har $453!$ både $2$ og $5$ som faktorer. Dermed er siste siffer i $453!$ lik $0$, og dermed er også siste siffer av $(453!)^{88}$ lik $0$.Gjest skrev:Ville det fungert på å finne det siste sifferet på dette; [tex]453!^{88}[/tex] ?
~~~~~~~~~
Hvis du egentlig mente å skrive $453^{88}$, kan vi bruke modulær aritmetikk. Ettersom $453 \equiv 3\text{ }(\text{mod }10)$, har vi at $453^2 \equiv 3^2 \equiv 9\equiv -1\text{ }(\text{mod }10)$, så $$453^{88} \equiv (453^2)^{44} \equiv (-1)^{44} \equiv 1\text{ }(\text{mod }10),$$ så siste siffer av $453^{88}$ er lik $1$.
EDIT: skrivefeil
Sist redigert av DennisChristensen den 15/07-2017 12:14, redigert 1 gang totalt.
DennisChristensen skrev:Det kommer av at det siste sifferet til et tall i titallssystemet alltid vil være lik resten når vi dividerer tallet på $10$: La $x\in\mathbb{N}$ være et heltall besteående av sifrene $x = a_n a_{n-1} \dots a_0,$ der $ a_n \neq 0$. Da har vi at $$x = 10^na_n + 10^{n-1}a_{n-1} + \dots + 10a_1 + a_0 = 10\left(10^{n-1}a_n + 10^{n-2}a_{n-1} + \dots + a_1\right) + a_0,$$ så $$x \equiv a_0 \text{ }(\text{mod }10).$$Gjest skrev:En ting til hvorfor tar du modulo [tex]10[/tex] når du finner siste siffer i et tall? Tallet må vel da ha 2 og 5 som faktor?
En ser nok dette fenomenet enklest ved å undersøke enkle eksempler.
$$23 = 2\cdot 10 + 3,\text{ så }23\equiv 3\text{ }(\text{mod }10);$$
$$1009 = 1\cdot 10^3 + 0\cdot 10^2 + 0\cdot 10 + 9,\text{ så }1009 \equiv 9\text{ }(\text{mod }10).$$
Her trengs ikke modulær aritmetikk. Ettersom $453 \geq 5$, har $453$ både $2$ og $5$ som faktorer. Dermed er siste siffer i $453!$ lik $0$, og dermed er også siste siffer av $(453!)^{88}$ lik $0$.Gjest skrev:Ville det fungert på å finne det siste sifferet på dette; [tex]453!^{88}[/tex] ?
~~~~~~~~~
Hvis du egentlig mente å skrive $453^{88}$, kan vi bruke modulær aritmetikk. Ettersom $453 \equiv 3\text{ }(\text{mod }10)$, har vi at $453^2 \equiv 3^2 \equiv 9\equiv -1\text{ }(\text{mod }10)$, så $$453^{88} \equiv (453^2)^{44} \equiv (-1)^{44} \equiv 1\text{ }(\text{mod }10),$$ så siste siffer av $453^{88}$ er lik $1$.
Igjen, tusen takk!
Enda en oppgave som på første øyekast virker umulig for meg:
Dersom [tex]a_0=0[/tex], [tex]a_1=1[/tex] og [tex]a_n=3a_{n-1}-2a_{n-2}[/tex] for [tex]n\geq 2[/tex]. Hva er siste siffer i [tex]a_{2014}[/tex].
Prøvde å først finne den eksplisitte formelen ut i fra den rekursive, men det gikk ikke. Vet at for å gå fra eksplisitt til rekursiv så regner man ut [tex]a_n-a_{n-1}[/tex].
[tex]a_n-a_{n-1}=3a_{n-1}-2a_{n-2 }\Rightarrow a_n=4a_{n-1}-2a_{n-2}[/tex] går ikke..
Prøve å angripe oppgaven annerledes da.
[tex]a_2=3a_{2-1}-2a_{2-2}=3a_1-2a_0=3*1-2*0=3[/tex]
[tex]a_3=3a_{3-1}-2a_{3-2}=3*3-2*1=7[/tex]
[tex]a_4=3a_{4-1}-2a_{4-2}=3*7-2*3=15[/tex]
Virker ikke som det er et lett gjennkjennelig møsnter her [tex]\left \{ a_0,a_1,a_2,a_3,a_4 \right \}\Rightarrow \left \{ 0,1,3,7,15 \right \}[/tex].
Uten at differansen mellom hvert ledd er et kvadrat tall? [tex]2^0,2^1,2^2,2^3...2^n..2^{n-1}[/tex] ? Vet ikke hva jeg skal jeg gjøre med denne informasjonen.
[tex]2014[/tex] er jo et partall så kanskje jeg burde uttrykke leddet på formen [tex]2n\pm 1[/tex]?
Siste siffer er vel kun avhengig av det siste sifferet i produktet av de siste sifrene i tallet, altså i [tex]a_{n-1}[/tex] og [tex]a_{n-2}[/tex] ?
Dersom [tex]a_0=0[/tex], [tex]a_1=1[/tex] og [tex]a_n=3a_{n-1}-2a_{n-2}[/tex] for [tex]n\geq 2[/tex]. Hva er siste siffer i [tex]a_{2014}[/tex].
Prøvde å først finne den eksplisitte formelen ut i fra den rekursive, men det gikk ikke. Vet at for å gå fra eksplisitt til rekursiv så regner man ut [tex]a_n-a_{n-1}[/tex].
[tex]a_n-a_{n-1}=3a_{n-1}-2a_{n-2 }\Rightarrow a_n=4a_{n-1}-2a_{n-2}[/tex] går ikke..
Prøve å angripe oppgaven annerledes da.
[tex]a_2=3a_{2-1}-2a_{2-2}=3a_1-2a_0=3*1-2*0=3[/tex]
[tex]a_3=3a_{3-1}-2a_{3-2}=3*3-2*1=7[/tex]
[tex]a_4=3a_{4-1}-2a_{4-2}=3*7-2*3=15[/tex]
Virker ikke som det er et lett gjennkjennelig møsnter her [tex]\left \{ a_0,a_1,a_2,a_3,a_4 \right \}\Rightarrow \left \{ 0,1,3,7,15 \right \}[/tex].
Uten at differansen mellom hvert ledd er et kvadrat tall? [tex]2^0,2^1,2^2,2^3...2^n..2^{n-1}[/tex] ? Vet ikke hva jeg skal jeg gjøre med denne informasjonen.
[tex]2014[/tex] er jo et partall så kanskje jeg burde uttrykke leddet på formen [tex]2n\pm 1[/tex]?
Siste siffer er vel kun avhengig av det siste sifferet i produktet av de siste sifrene i tallet, altså i [tex]a_{n-1}[/tex] og [tex]a_{n-2}[/tex] ?