Finn de tre siste sifrene i produktet 1·3·5·7·...·2009·2011
(vis en metode uten bruk av pc/kalkulator)
(oppgaven er fra finalen i Abelkonkurransen 2011)
Stort produkt
Moderators: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
Vektormannen
- Euler
- Posts: 5889
- Joined: 26/09-2007 19:35
- Location: Trondheim
- Contact:
Dette ble noe svineri, men:
Kaller tallet for N. Har at [tex]1 \cdot 3 \cdots 2011 \equiv (1 \cdot 3 \cdot 5 \cdot 7 \cdot 9)^{201} \equiv (1 \cdot 3 \cdot 5 \cdot (-3) \cdot (-1))^{201} \equiv (-5)^{201} \equiv 5 \ (\text{mod} \ 10)[/tex], så siste siffer er 5.
Videre er [tex]\frac{N-5}{10} = \frac{5(1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1)}{10} = \frac{1 \cdot 3 \cdot 7 \cdots 2011 - 1}{2}[/tex]
Ser på telleren modulo 10. Her får vi [tex]1 \cdot 3 \cdot 7 \cdots 2011 - 1 \equiv (1 \cdot 3 \cdot 7 \cdot 9) \cdot 5^{200} - 1 \equiv -5-1 = -6 \equiv 4 \ (\text{mod} 10)[/tex], så siste siffer i telleren er 4. Når vi deler et slikt tall på 2 blir siste siffer i tallet enten 2 eller 7 (siden [tex]\frac{10k + 4}{2} = 5k+2[/tex] enten er kongruent med 2 modulo 10, hvis k er et partall, og kongruent med 5 + 2 = 7 hvis k er et oddetall). Så det nest siste sifferet i N er altså 2 eller 7. Vi har at [tex]1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1 \equiv 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot (-1) \cdots (-1) \equiv 2 \ (\text{mod} \ 4)[/tex]. Det gir at [tex]\frac{1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1}{2}[/tex] er et oddetall, og kan ikke ha 2 som siste siffer. Det nest siste sifferet er altså 7.
Prosedyren gjentas igjen (dvs. trekker fra resten og deler på 10). Vi får da [tex]\frac{\frac{1 \cdot 3 \cdot 7 \cdots 2011 - 1}{2} - 7}{10} = \frac{1 \cdot 3^2 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 17 \cdots 2011 - 3}{4}[/tex]. Nå blir telleren kongruent med 2 modulo 10. Når vi deler et slikt tall på 4 blir siste siffer enten 3 eller 8. På samme måte får vi her at hvis tallet går opp i 8 blir siste siffer 8, og hvis ikke blir det 3. Vi får her at [tex]1 \cdot 3^2 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 17 \cdots 2011 - 3 \equiv 1 \cdot 1 \cdot (-1) \cdot 1 \cdot 3 \cdot (-3) \cdot (1 \cdot 3 \cdot (-3) \cdot 1)^{498} \cdot 1 \cdot 3 - 3 \equiv 3 - 3 = 0 \ (\text{mod} \ 8)[/tex]. Da er det tredje siste sifferet altså 8.
For å konkludere blir de tre siste sifrene 875.
Kaller tallet for N. Har at [tex]1 \cdot 3 \cdots 2011 \equiv (1 \cdot 3 \cdot 5 \cdot 7 \cdot 9)^{201} \equiv (1 \cdot 3 \cdot 5 \cdot (-3) \cdot (-1))^{201} \equiv (-5)^{201} \equiv 5 \ (\text{mod} \ 10)[/tex], så siste siffer er 5.
Videre er [tex]\frac{N-5}{10} = \frac{5(1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1)}{10} = \frac{1 \cdot 3 \cdot 7 \cdots 2011 - 1}{2}[/tex]
Ser på telleren modulo 10. Her får vi [tex]1 \cdot 3 \cdot 7 \cdots 2011 - 1 \equiv (1 \cdot 3 \cdot 7 \cdot 9) \cdot 5^{200} - 1 \equiv -5-1 = -6 \equiv 4 \ (\text{mod} 10)[/tex], så siste siffer i telleren er 4. Når vi deler et slikt tall på 2 blir siste siffer i tallet enten 2 eller 7 (siden [tex]\frac{10k + 4}{2} = 5k+2[/tex] enten er kongruent med 2 modulo 10, hvis k er et partall, og kongruent med 5 + 2 = 7 hvis k er et oddetall). Så det nest siste sifferet i N er altså 2 eller 7. Vi har at [tex]1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1 \equiv 1 \cdot (-1) \cdot (-1) \cdot 1 \cdot (-1) \cdots (-1) \equiv 2 \ (\text{mod} \ 4)[/tex]. Det gir at [tex]\frac{1 \cdot 3 \cdot 7 \cdot 9 \cdots 2011 - 1}{2}[/tex] er et oddetall, og kan ikke ha 2 som siste siffer. Det nest siste sifferet er altså 7.
Prosedyren gjentas igjen (dvs. trekker fra resten og deler på 10). Vi får da [tex]\frac{\frac{1 \cdot 3 \cdot 7 \cdots 2011 - 1}{2} - 7}{10} = \frac{1 \cdot 3^2 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 17 \cdots 2011 - 3}{4}[/tex]. Nå blir telleren kongruent med 2 modulo 10. Når vi deler et slikt tall på 4 blir siste siffer enten 3 eller 8. På samme måte får vi her at hvis tallet går opp i 8 blir siste siffer 8, og hvis ikke blir det 3. Vi får her at [tex]1 \cdot 3^2 \cdot 7 \cdot 9 \cdot 11 \cdot 13 \cdot 17 \cdots 2011 - 3 \equiv 1 \cdot 1 \cdot (-1) \cdot 1 \cdot 3 \cdot (-3) \cdot (1 \cdot 3 \cdot (-3) \cdot 1)^{498} \cdot 1 \cdot 3 - 3 \equiv 3 - 3 = 0 \ (\text{mod} \ 8)[/tex]. Da er det tredje siste sifferet altså 8.
For å konkludere blir de tre siste sifrene 875.
Elektronikk @ NTNU | nesizer
-
Brahmagupta
- Guru
- Posts: 628
- Joined: 06/08-2011 01:56
Var i finalen med denne oppgaven. Løsningen min var ikke særlig fin.
Så på produktet mod 1000, la til side 2001*2003*2005*2007*2009*2011
og klappet resten sammen til:
[tex](1*3*5*...*499)^4 mod 1000[/tex]
Hvilket må ende på 625:
[tex](10a + 5)**4=10^4a^4 + 2*10^4a^3 + 15*10^3a^2 + 5*10^3a + 625[/tex]
Deretter ganget jeg sammen 625 med tallene jeg la til siden i starten. Og sjekket de tre siste sifrene, hvilket er den langt mindre elegante delen...
Så på produktet mod 1000, la til side 2001*2003*2005*2007*2009*2011
og klappet resten sammen til:
[tex](1*3*5*...*499)^4 mod 1000[/tex]
Hvilket må ende på 625:
[tex](10a + 5)**4=10^4a^4 + 2*10^4a^3 + 15*10^3a^2 + 5*10^3a + 625[/tex]
Deretter ganget jeg sammen 625 med tallene jeg la til siden i starten. Og sjekket de tre siste sifrene, hvilket er den langt mindre elegante delen...
Hadde en lignende fremgangsmåte som Brahmagupta, men fant ut at
[tex]5^4(2n+1)^2-5^4=5^4(4n^2+4n)\equiv 0\,mod(1000)[/tex]
, og tallet kan da skrives på formen [tex]5^4(2n+1)^2*11*9*7*5*3\equiv 5^4*11*...*3[/tex] mod 1000,
For øvrig er vel Vektormannens metode i prinsippet mer elegant, ja:)
[tex]5^4(2n+1)^2-5^4=5^4(4n^2+4n)\equiv 0\,mod(1000)[/tex]
, og tallet kan da skrives på formen [tex]5^4(2n+1)^2*11*9*7*5*3\equiv 5^4*11*...*3[/tex] mod 1000,
For øvrig er vel Vektormannens metode i prinsippet mer elegant, ja:)
-
Brahmagupta
- Guru
- Posts: 628
- Joined: 06/08-2011 01:56
Den løsningen som ble presentert i etterkant av konkurransen gikk ut på å vise at de 3 siste sifrene må dele 125, siden 1000 deler 125, hvilket gir 4 muligheter 125, 375, 625, 875, og deretter vise at kun en av disse er kongruent med produktet mod 8.
Synes den var ganske grei
Synes den var ganske grei