Question

Знайти остачу від ділення на 33 числа 633^763^406

Answer 1

Ответ:

24

Объяснение:

Рассмотрим кольцо остатков числа $633^n$ от деления на 33. Известно, что $a^n\equiv (a\text{ mod } b)^n\,\,(\text{mod }b)$, следовательно, нам достаточно лишь исследовать кольцо остатков числа $6^n$ от деления на 33 (так как $633\text{ mod }33 = 6$):

$\begin{center}\\\begin{tabular}[c c}\\\\n & 6^n \text{ mod 33}\\\\n=1 & 6\\n=2 & 3\\\\n=3 & 18\\\\n=4 & 9\\n=5 & 21\\n=6 & 27\\\\n=7 & 30\\n=8 & 15\\n=9 & 24\\n=10 & 12\\\\n=11 & 6\\\end{tabular}\\\end{center}$

Мы получили снова $6$, следовательно, кольцо замкнулось, и дальше мы будем получать те же самые остатки. Поскольку в таблице есть всего 10 разных остатков, то, следовательно, $633^{n}\text{ mod 33} = 633^{(n\text{ mod 10})}\text{ mod 33}$. И следовательно, нам теперь необходимо вычислить $763^{406}\text{ mod }10$. Сделаем мы это аналогично тому, как мы сделали таблицу $633^n\text{ mod 33}$ - рассмотрим кольцо остатков. $763\equiv3\,(\text{mod 10})$, следовательно делаем такую таблицу:

$\begin{center}\\\begin{tabular}{c c}\\\\n & 3^n\text{ mod 10}\\n=1 & 3\\n=2 & 9\\n=3 & 7\\n=4 & 1\\n=5 & 3\end{center}\\\end{tabular}$

Итак, мы получили, что $763^{n}\text{ mod 4} = 763^{(n\text{ mod 4})}\text{ mod 10}$.

Следовательно, теперь, используя эти факты и таблицы, можно без проблем найти этот остаток:$633^{{763}^{406}}\equiv 6^{(3^{(406\text{ mod }4)}\text{ mod }10)}\equiv6^{(3^2\text{ mod }10)}\equiv6^9\equiv 24\,\,(\text{mod 33})$.

Итак, остаток от деления $633^{{763}^{406}}$ на 33 равен 24.

Answer 2

Ответ: 24

Объяснение:

Знайти остачу від ділення на 33 числа  $\large \boldsymbol {} \displaystyle 633^{763^{406}}$

Воспользуемся сравнениями по модулю

$\large \boldsymbol {} \displaystyle 633^{763^{406}} \equiv (633 - 19\cdot 33)^{763^{406}} \equiv 6^{763^{406}} \equiv 2^{763^{406}}\cdot 3^{763^{406}} \mod 33$

Согласно китайской теореме об остатках (коротко КТО)

Если

$\left \{\begin{array}{l} m \equiv r_1 \pmod{k} \\ n \equiv r_2 \pmod{k} \end{array}$

То тогда
m·n ≡ r₁ ·r₂ ≡ mod k

Находим по отдельности остаток при делении   $\large \boldsymbol {} 3^{763^{406}}$ на 33 ,  и  для$\text { \large 2^{763^{406}} }$ , затем применяем КТО  

1.Попробуем найти длину  наименьшего периода остатков для 3ⁿ при делении на 33

3¹  ≡ 3 mod 33
3² ≡ 9 mod 33
3³ ≡ 27 mod 33
3⁴ ≡ 15 mod  33
3⁵ ≡ 15·3 ≡ 12 mod  33
3⁶ ≡ 12·3 ≡ 3  mod 33

На 6 степени мы получили первый остаток при делении на 33, значит длина периода равна 5

Соответственно  $\large \boldsymbol {} 3^{763^{406}} = 3^{5i + j}$, чтобы найти остаток нам потребуется вычислить  0 ≤ j ≤ 4, т.е остаток от деления $763^{406}$  на 5

Ну тогда

$\large \boldsymbol {} 763^{406} \equiv (763 - 760)^{406} \equiv 3^{406} \mod5$

Согласно теореме Эйлера φ(5) = 4 ⇒

$\large \boldsymbol {} 3^{406} \equiv 3^{101\cdot 4 + 2} \equiv 3^2 \equiv 4 \mod5$

Таким образом

$\large \boldsymbol {} 3^{763^{406}} \equiv 3^{4} \equiv 15 \mod 33$

2. Поскольку 211 взаимно просто с 33, то в данном случае мы можем применить теорему Эйлера и сразу найти длину периода остатков

$\large \boldsymbol {}2^{k} \equiv 1 \mod 33$

k = НОК ( φ(11)  , φ(3)   ) = НОК(3,10) = 30

Далее аналогично как и в 1

$\large \boldsymbol {} 763^{406} \equiv (763 - 30\cdot 25)^{406} \equiv 13^{406} \mod 30$

$\varphi (30) = (5-1)(3-1)(2-1) = 10$

$\large \boldsymbol {} 13^{406} \equiv 13^{10\cdot 40 +6 } \equiv 13^6 \equiv 169^3 \equiv (169 - 30\cdot 6)^3 \equiv \\\\ \equiv -11^3 \equiv -1331 \equiv -1331 +30\cdot 45 \equiv 19 \mod 30$

Остается посчитать

$\large \boldsymbol {}211^{763^{406}} \equiv 2^{19 } \equiv 2^{19 - 10 } \equiv 2^9 \equiv (32-33) \cdot 16 \equiv - 1\cdot 16 \equiv \\\\ \equiv -16 + 33 \equiv 17 \mod 33$

3. Применяем КТО,  и находим искомый остаток

$\large \boldsymbol {}\left \{\begin{array}{l} 3^{763^{406}} \equiv 15 \pmod{33} \\ 2^{763^{406}}\equiv 17\pmod{33} \end{array}$

$\large \boldsymbol {} \displaystyle 633^{763^{406}} = 2^{763^{406}}\cdot 3^{763^{406}}\equiv 15\cdot 17 \equiv 24 \mod 33$