📜 Euler's Theorem (Ојлерова Теорема)

## 💡 Дефиниција Нека $n$ е позитивен цел број и $a$ е цел број таков што $\gcd(a, n) = 1$ (заемно прости). Тогаш: $$a^{\phi(n)} \equiv 1 \pmod n$$ Каде $\phi(n)$ е **Ојлеровата функција** (бројот на цели броеви помали од $n$ кои се заемно прости со $n$). --- ## 🧠 Интуиција Ова е генерализација на Малата теорема на Ферма. Во светот на модуларна аритметика (часовник со $n$ часови), ако множиме број сам со себе доволно пати, на крајот ќе се вратиме на 1 (ако немаме заеднички делители со $n$). Циклусот на повторување секогаш е делител на $\phi(n)$. --- ## 📝 Примери 1. **Прост модул ($n=7$):** $\phi(7) = 6$. Нека $a=2$. $2^6 = 64 = 9 \cdot 7 + 1 \equiv 1 \pmod 7$. 2. **Сложен модул ($n=10$):** Броеви заемно прости со 10 се $\{1, 3, 7, 9\}$. Значи $\phi(10) = 4$. Нека $a=3$. $3^4 = 81 \equiv 1 \pmod{10}$. --- ## 🛠 Каде се користи? 1. **RSA Енкрипција:** Целиот интернет безбедносен систем се базира на оваа теорема. 2. **Пресметка на големи степени:** Колку е $7^{2025} \pmod{100}$? $\phi(100) = 100(1-1/2)(1-1/5) = 40$. $2025 = 50 \cdot 40 + 25 \equiv 25 \pmod{40}$. Значи $7^{2025} \equiv 7^{25} \pmod{100}$. 3. **Инверзни елементи:** $a^{\phi(n)-1}$ е модуларен инверз на $a$.