Question

Как найти остаток деления 5^48 на 6 как найти остаток деления 3^258 на 13только не просто ответ, а хотя бы примерный алгоритм как все это находится

Answer 1

3 mod 13 = 3           первая степень
9 mod 13 = 9           вторая степень
27 mod 13 = 1         третья степень
81 mod 13 = 3         четвертая степень остаток как у первой степени
243 mod 13 = 9        пятая степень остаток как у второй степени
и так далее

у 258 степени остаток будет как у третьей, то есть 1

Answer 2

Для нахождения остатка от деления чисел 5^48 на 6 и 3^258 на 13, можно использовать алгоритм возведения в степень по модулю.

Алгоритм для нахождения остатка от деления 5^48 на 6:

1. Начните с числа 5. 2. Возведите число 5 в степень 48. 3. Разделите полученное число на 6 и найдите остаток от деления.

Алгоритм для нахождения остатка от деления 3^258 на 13:

1. Начните с числа 3. 2. Возведите число 3 в степень 258. 3. Разделите полученное число на 13 и найдите остаток от деления.

Примечание: Для возведения чисел в большие степени, можно использовать алгоритм быстрого возведения в степень, чтобы уменьшить количество операций.

Примерный алгоритм для быстрого возведения числа в степень: 1. Если степень равна 0, верните 1. 2. Если степень четная, возведите число в степень, деленную пополам, а затем возведите результат в квадрат. 3. Если степень нечетная, возведите число в степень, деленную пополам, а затем возведите результат в квадрат и умножьте на само число.

Например, для нахождения остатка от деления 5^48 на 6, можно использовать следующий алгоритм:

1. Возведение числа 5 в степень 48: - Разделим степень 48 на 2: 48 / 2 = 24. - Возведем число 5 в степень 24: 5^24. - Возведем результат в квадрат: (5^24)^2. - Повторим шаги 2-3 еще 2 раза: ((5^24)^2)^2^2. - Получим результат: 5^48. 2. Разделение результата на 6 и нахождение остатка от деления: 5^48 % 6.

Аналогично, для нахождения остатка от деления 3^258 на 13, можно использовать алгоритм быстрого возведения в степень:

1. Возведение числа 3 в степень 258: - Разделим степень 258 на 2: 258 / 2 = 129. - Возведем число 3 в степень 129: 3^129. - Возведем результат в квадрат: (3^129)^2. - Повторим шаги 2-3 еще 6 раз: ((3^129)^2)^2^2^2^2^2^2. - Получим результат: 3^258. 2. Разделение результата на 13 и нахождение остатка от деления: 3^258 % 13.

Пожалуйста, обратите внимание, что эти алгоритмы являются примерными и могут быть улучшены для более эффективного вычисления.