matematikk.net

Finn resten til $6^{83}+8^{83}$ etter divisjon med $49$

Gustav skrev:Finn resten til $6^{83}+8^{83}$ etter divisjon med $49$

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.$$

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 :=)

Korrekt! (Fra AIME 1983)

Edit: Alternativ løsning er å omskrive til $(7-1)^{83}+(7+1)^{83}$ og så benytte binomialteoremet.

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)$

Flott!