Julekalender #2 (oppfølger)
Moderatorer: Vektormannen, espen180, Aleks855, Solar Plexsus, Gustav, Nebuchadnezzar, Janhaa
-
- Grothendieck
- Innlegg: 826
- Registrert: 09/02-2015 23:28
- Sted: Oslo
Min første løsning var bare sludder. Vi har at $\phi(49) = 42.$ Fra Euler-Fermat har vi at $$6^{83} \equiv \left(6^{42}\right)^2\cdot 6^{-1} \equiv 6^{-1} \equiv 41\text{ mod }49.$$ På samme vis, $$8^{83} \equiv 8^{-1} \equiv 43\text{ mod }49.$$ Dermed får vi $$6^{83} + 8^{84} \equiv 43 + 41 \equiv 35 \text{ mod }49.$$Gustav skrev:Finn resten til $6^{83}+8^{83}$ etter divisjon med $49$
Sist redigert av DennisChristensen den 02/12-2017 15:17, redigert 1 gang totalt.
Euler's formel:
[tex]\phi(49)=42, \\ 6^{\phi(49)}\equiv 1 \pmod{49}\\ 6^{42}\equiv 1 \pmod{49},\\ fordi\,\,\gcd(6,49)=1\\ 6^{84}\equiv 1 \pmod{49},\\ 6^{-1}6^{84}=6^{83}\equiv 6^{-1} \pmod{49},\\ 6^{83}\equiv 41 \pmod{49}\\ der\\ 6^{-1}\equiv 41 \pmod{49}[/tex]
så tilsvarende for neste:
[tex]\phi(49)=42, \\ 8^{\phi(49)}\equiv 1 \pmod{49}\\ 8^{42}\equiv 1 \pmod{49},\\ fordi\,\,\gcd(8,49)=1\\ 8^{84}\equiv 1 \pmod{49},\\ 8^{-1}8^{84}=8^{83}\equiv 8^{-1} \pmod{49},\\ 8^{83}\equiv 43 \pmod{49}\\ der\\ 8^{-1}\equiv 43 \pmod{49}[/tex]
endelig:
[tex]6^{83}+8^{83}\equiv 41+43\equiv 35 \pmod{49}[/tex]
\\\\\\\\\\\\\\\\\\\\
kladda den før Dennis førte den inn og kom meg i forkjøpet.
Men her er en mer omstendelig utgave :=)
[tex]\phi(49)=42, \\ 6^{\phi(49)}\equiv 1 \pmod{49}\\ 6^{42}\equiv 1 \pmod{49},\\ fordi\,\,\gcd(6,49)=1\\ 6^{84}\equiv 1 \pmod{49},\\ 6^{-1}6^{84}=6^{83}\equiv 6^{-1} \pmod{49},\\ 6^{83}\equiv 41 \pmod{49}\\ der\\ 6^{-1}\equiv 41 \pmod{49}[/tex]
så tilsvarende for neste:
[tex]\phi(49)=42, \\ 8^{\phi(49)}\equiv 1 \pmod{49}\\ 8^{42}\equiv 1 \pmod{49},\\ fordi\,\,\gcd(8,49)=1\\ 8^{84}\equiv 1 \pmod{49},\\ 8^{-1}8^{84}=8^{83}\equiv 8^{-1} \pmod{49},\\ 8^{83}\equiv 43 \pmod{49}\\ der\\ 8^{-1}\equiv 43 \pmod{49}[/tex]
endelig:
[tex]6^{83}+8^{83}\equiv 41+43\equiv 35 \pmod{49}[/tex]
\\\\\\\\\\\\\\\\\\\\
kladda den før Dennis førte den inn og kom meg i forkjøpet.
Men her er en mer omstendelig utgave :=)
La verken mennesker eller hendelser ta livsmotet fra deg.
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Marie Curie, kjemiker og fysiker.
[tex]\large\dot \rho = -\frac{i}{\hbar}[H,\rho][/tex]
Alternativ løsning, der vi prøver å utnytte symmetrien i utrykket;
Observer at $8^{83} = (7+1)^{83}$ og $6^{83} = (7-1)^{83}$, så vi har at $6^{83} + 8^{83} = (7-1)^{83} + (7+1)^{83}$
Ved binomialteoremet har vi at
$(7-1)^{83} + (7+1)^{83} = \sum_{k=0}^{83} \binom{83}{k} \cdot 7^k \cdot (-1)^{83-k} + \sum_{k=0}^{83} \binom{83}{k} \cdot 7^k \cdot 1^{83-k}$
Vi ser at annenhvert ledd annuleres av vekslende fortegn, slik at vi kun står igjen med de leddene der $k$ er oddetall. Vi har altså videre at
$6^{83} + 8^{83} = 2 \cdot \sum_{k=0}^{41} \binom{83}{2k+1} \cdot 7^{2k+1} \cdot 1^{82 - 2k} = 2 \cdot \sum_{k=0}^{41} \binom{83}{2k+1} \cdot 7^{2k+1}$
Vi ser at $49 \mid 7^n \enspace \forall n \in \mathbb{N}, n \geq 2$, slik at alle iterasjoner av summasjonstegnet fra og med $k=1$ er delelig på $49$. Spørsmålet koker altså ned til
$2 \cdot \binom{83}{1} \cdot 7 \equiv x \enspace (\text{mod } 49)$
$1162 \equiv x \enspace (\text{mod } 49)$
Med litt hoderegning kommer vi fram til at $49 \cdot 23 = 1127$
Da har vi at $1162 \equiv (1162-1127) \equiv 35 \enspace (\text{mod } 49) \Longrightarrow 6^{83} + 8^{83} \equiv 35 \enspace (\text{mod } 49)$
Observer at $8^{83} = (7+1)^{83}$ og $6^{83} = (7-1)^{83}$, så vi har at $6^{83} + 8^{83} = (7-1)^{83} + (7+1)^{83}$
Ved binomialteoremet har vi at
$(7-1)^{83} + (7+1)^{83} = \sum_{k=0}^{83} \binom{83}{k} \cdot 7^k \cdot (-1)^{83-k} + \sum_{k=0}^{83} \binom{83}{k} \cdot 7^k \cdot 1^{83-k}$
Vi ser at annenhvert ledd annuleres av vekslende fortegn, slik at vi kun står igjen med de leddene der $k$ er oddetall. Vi har altså videre at
$6^{83} + 8^{83} = 2 \cdot \sum_{k=0}^{41} \binom{83}{2k+1} \cdot 7^{2k+1} \cdot 1^{82 - 2k} = 2 \cdot \sum_{k=0}^{41} \binom{83}{2k+1} \cdot 7^{2k+1}$
Vi ser at $49 \mid 7^n \enspace \forall n \in \mathbb{N}, n \geq 2$, slik at alle iterasjoner av summasjonstegnet fra og med $k=1$ er delelig på $49$. Spørsmålet koker altså ned til
$2 \cdot \binom{83}{1} \cdot 7 \equiv x \enspace (\text{mod } 49)$
$1162 \equiv x \enspace (\text{mod } 49)$
Med litt hoderegning kommer vi fram til at $49 \cdot 23 = 1127$
Da har vi at $1162 \equiv (1162-1127) \equiv 35 \enspace (\text{mod } 49) \Longrightarrow 6^{83} + 8^{83} \equiv 35 \enspace (\text{mod } 49)$