Задача 71303 ...
Условие
N = 428!
[blue]2)Для числа [b]a=p_(1)^(a_(1))*p_(2)^(a_(2))*...*p_(k)^(a_(k))[/b] вычислить три мультипликативные функции:[/blue]
1. количество делителей τ(a)
2. сумму делителей S(a)
3. функцию Эйлера φ(a)
Данные: a=2^(5)5^(2)*7*61[/b]
[b][blue]3)Найдите остаток от деления:[/blue]
12^(2751) на 5[/b]
Решение
Чтобы найти, сколько 0 в конце, нужно найти, сколько 5 в этом факториале. При этом надо помнить, что:
25 (и все числа, кратные 25) - содержат две 5.
125 (и все числа, кратные 125) - содержат три 5.
Получаем:
1) 5, 10, 15, 20, ..., 425 - 85 штук 5.
2) 25, 50, 75, 100, ..., 425 - 17 штук 25.
Они уже все учтены в 1) пункте, поэтому прибавляем по одной 5,
а не по две.
3) 125, 250, 375 - три штуки 125.
Всего 85 + 17 + 3 = 105
Ответ: 428! кончается на 105 нулей.
2) Это я не знаю, как делать. Считать делители, а тем более их сумму - это долго и трудно.
3) 12^(2751) делим на 5.
Фактически нужно узнать, какая последняя цифра.
0 или 5 - остаток 0.
1 или 6 - остаток 1.
2 или 7 - остаток 2.
3 или 8 - остаток 3.
4 или 9 - остаток 4.
На последнюю цифру влияет только последняя цифра основания.
2^(2751) = 2*2^(2750) = 2*(2^(10))^(275) = 2*1024^(275)
Оставляем последнюю цифру основания 4.
2*4^(275) = 2*(4^5)^(55) = 2*1024^(55)
Опять оставляем последнюю цифру основания 4.
2*4^(55) = 2*(4^5)^(11) = 2*1024^(11) = 2*4^(11) = 2*4*4^(10) =
= 8*(4^5)^2 = 8*1024^2
Опять оставляем последнюю цифру основания 4.
8*4^2 = 8*16 = 128
Число кончается на 8, значит, при делении на 5 будет остаток 3.
Ответ: 3