Resturi Puteri 408341

1. Problema cere să găsim resturile împărțirii lui $2^{1000000}$ la $35$ și $7^{2025}$ la $1000$. 2. Vom folosi teorema lui Euler și proprietăți ale congruențelor pentru a simplifica calculele. --- **Partea 1: Calculul restului lui $2^{1000000}$ la $35$** 3. Observăm că $35 = 5 \times 7$, iar $5$ și $7$ sunt prime între ele. 4. Folosim teorema resturilor chineze pentru a calcula separat resturile modulo $5$ și $7$. 5. Calculăm $2^{1000000} \bmod 5$: - Euler totient pentru $5$ este $\varphi(5) = 4$. - Deci $2^{4} \equiv 1 \pmod{5}$. - $1000000 \bmod 4 = 0$, deci $2^{1000000} \equiv (2^{4})^{250000} \equiv 1^{250000} \equiv 1 \pmod{5}$. 6. Calculăm $2^{1000000} \bmod 7$: - Euler totient pentru $7$ este $\varphi(7) = 6$. - $1000000 \bmod 6 = 4$ (deoarece $6 \times 166666 = 999996$, rest $4$). - Deci $2^{1000000} \equiv 2^{4} \equiv 16 \equiv 2 \pmod{7}$ (deoarece $16 - 2 \times 7 = 16 - 14 = 2$). 7. Acum avem sistemul: $$\begin{cases} x \equiv 1 \pmod{5} \\ x \equiv 2 \pmod{7} \end{cases}$$ 8. Folosim metoda substituției: - $x = 1 + 5k$ - Înlocuim în a doua congruență: $$1 + 5k \equiv 2 \pmod{7} \Rightarrow 5k \equiv 1 \pmod{7}$$ 9. Observăm că $5 \times 3 = 15 \equiv 1 \pmod{7}$, deci inversul lui $5$ modulo $7$ este $3$. 10. Deci: $$k \equiv 3 \times 1 = 3 \pmod{7}$$ 11. Cel mai mic $k$ este $3$, deci: $$x = 1 + 5 \times 3 = 16$$ 12. Verificăm: - $16 \bmod 5 = 1$ - $16 \bmod 7 = 2$ Deci restul lui $2^{1000000}$ la $35$ este $16$. --- **Partea 2: Calculul restului lui $7^{2025}$ la $1000$** 13. Observăm că $1000 = 2^{3} \times 5^{3}$. 14. Folosim din nou teorema resturilor chineze, calculând separat modulo $8$ și $125$. 15. Calculăm $7^{2025} \bmod 8$: - $7 \equiv -1 \pmod{8}$ - $7^{2025} \equiv (-1)^{2025} = -1 \equiv 7 \pmod{8}$ (deoarece $2025$ este impar). 16. Calculăm $7^{2025} \bmod 125$: - Euler totient pentru $125$ este $\varphi(125) = 125 \times (1 - \frac{1}{5}) = 100$. - $2025 \bmod 100 = 25$ (deoarece $100 \times 20 = 2000$, rest $25$). - Deci $7^{2025} \equiv 7^{25} \pmod{125}$. 17. Calculăm $7^{25} \bmod 125$ prin înmulțiri succesive: - $7^{1} = 7$ - $7^{2} = 49$ - $7^{3} = 49 \times 7 = 343 \equiv 343 - 2 \times 125 = 343 - 250 = 93 \pmod{125}$ - $7^{4} = 93 \times 7 = 651 \equiv 651 - 5 \times 125 = 651 - 625 = 26 \pmod{125}$ - $7^{5} = 26 \times 7 = 182 \equiv 182 - 1 \times 125 = 57 \pmod{125}$ - $7^{10} = (7^{5})^{2} = 57^{2} = 3249 \equiv 3249 - 26 \times 125 = 3249 - 3250 = -1 \equiv 124 \pmod{125}$ - $7^{20} = (7^{10})^{2} = 124^{2} = 15376 \equiv 15376 - 123 \times 125 = 15376 - 15375 = 1 \pmod{125}$ - $7^{25} = 7^{20} \times 7^{5} = 1 \times 57 = 57 \pmod{125}$ 18. Deci $7^{2025} \equiv 57 \pmod{125}$. 19. Sistemul este: $$\begin{cases} x \equiv 7 \pmod{8} \\ x \equiv 57 \pmod{125} \end{cases}$$ 20. Folosim metoda substituției: - $x = 7 + 8m$ - Înlocuim în a doua congruență: $$7 + 8m \equiv 57 \pmod{125} \Rightarrow 8m \equiv 50 \pmod{125}$$ 21. Trebuie să găsim inversul lui $8$ modulo $125$. - Folosim algoritmul Euclid extins: - $125 = 8 \times 15 + 5$ - $8 = 5 \times 1 + 3$ - $5 = 3 \times 1 + 2$ - $3 = 2 \times 1 + 1$ - $2 = 1 \times 2 + 0$ - Revenind: - $1 = 3 - 2 \times 1$ - $2 = 5 - 3 \times 1$ - $3 = 8 - 5 \times 1$ - $5 = 125 - 8 \times 15$ - Calculăm coeficienții pentru $1$: - $1 = 3 - 2 = 3 - (5 - 3) = 2 \times 3 - 5$ - $= 2 \times (8 - 5) - 5 = 2 \times 8 - 3 \times 5$ - $= 2 \times 8 - 3 \times (125 - 8 \times 15) = 2 \times 8 - 3 \times 125 + 45 \times 8 = 47 \times 8 - 3 \times 125$ - Deci inversul lui $8$ modulo $125$ este $47$. 22. Calculăm: $$m \equiv 47 \times 50 = 2350 \equiv 2350 - 18 \times 125 = 2350 - 2250 = 100 \pmod{125}$$ 23. Cel mai mic $m$ este $100$, deci: $$x = 7 + 8 \times 100 = 7 + 800 = 807$$ 24. Verificăm: - $807 \bmod 8 = 7$ - $807 \bmod 125 = 57$ Deci restul lui $7^{2025}$ la $1000$ este $807$. --- **Răspuns final:** - Restul lui $2^{1000000}$ la $35$ este $16$. - Restul lui $7^{2025}$ la $1000$ este $807$.