Julekalender #2 (oppfølger)

[Gustav]

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

[DennisChristensen]

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

Min første løsning var bare sludder. Vi har at $\varphi (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.$$

[Janhaa]

Euler's formel:

$$\begin{gathered} \varphi (49)=42, \\ {6}^{\varphi (49)}\equiv 1(\mathrm{mod}49) \\ {6}^{42}\equiv 1(\mathrm{mod}49), \\ fordigcd(6,49)=1 \\ {6}^{84}\equiv 1(\mathrm{mod}49), \\ {6}^{-1}{6}^{84}=6^{83}\equiv 6^{-1}(\mathrm{mod}49), \\ {6}^{83}\equiv 41(\mathrm{mod}49) \\ der \\ {6}^{-1}\equiv 41(\mathrm{mod}49) \end{gathered}$$

så tilsvarende for neste:


$$\begin{gathered} \varphi (49)=42, \\ {8}^{\varphi (49)}\equiv 1(\mathrm{mod}49) \\ {8}^{42}\equiv 1(\mathrm{mod}49), \\ fordigcd(8,49)=1 \\ {8}^{84}\equiv 1(\mathrm{mod}49), \\ {8}^{-1}{8}^{84}=8^{83}\equiv 8^{-1}(\mathrm{mod}49), \\ {8}^{83}\equiv 43(\mathrm{mod}49) \\ der \\ {8}^{-1}\equiv 43(\mathrm{mod}49) \end{gathered}$$

endelig:

$6^{83}+8^{83}\equiv 41+43\equiv 35(\mathrm{mod}49)$
\\\\\\\\\\
kladda den før Dennis førte den inn og kom meg i forkjøpet.
Men her er en mer omstendelig utgave :=)

[Gustav]

Korrekt! (Fra AIME 1983)

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

[Markus]

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}(\genfrac{}{}{0ex}{}{83}{k})\cdot 7^k\cdot (-1{)}^{83-k}+\sum _{k=0}^{83}(\genfrac{}{}{0ex}{}{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}(\genfrac{}{}{0ex}{}{83}{2k+1})\cdot 7^{2k+1}\cdot 1^{82-2k}=2\cdot \sum _{k=0}^{41}(\genfrac{}{}{0ex}{}{83}{2k+1})\cdot 7^{2k+1}$

Vi ser at $49\mid 7^n\mathrm{\forall }n\in \mathbb{N},n\ge 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 (\genfrac{}{}{0ex}{}{83}{1})\cdot 7\equiv x(\text{mod }49)$

$1162\equiv x(\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(\text{mod }49)⟹6^{83}+8^{83}\equiv 35(\text{mod }49)$

[Gustav]

Flott!