найти остаток от деления 6^39 на 41

[give_up]

В школе когда-то изучал теорию чисел, но почти все забыл, вот есть задача - найти, чему равняется число $x$, если $x=6^{39} (\mod 41)$ Как я понимаю, здесь нужно найти остаток от деления числа $6^{39}$ на 41. Но есть ли для этого более простой способ, нежели возводить число 6 в 39 степень и делить его затем на 41?

[ИСН]

Можете делить на 41 после каждого умножения, это сложнее, но и проще.

[Sonic86]

Удобно умножить обе части на $6$ и воспользоваться малой теоремой Ферма. А дальше - проще (алгоритм Евклида).

[Zealint]

Так ведь Вы можете возвести в 39 степень довольно быстро, за 6 умножений всего, а может и быстрее... После каждого, действительно, берите остаток.

[bot]

Sonic86 в сообщении #544323 писал(а):

... А дальше проще

$6\times 7=42$

[give_up]

Понятно