Галкина_Таисия_нис

Теорема:
?(??) = ?(?)⋅?(?), если (?, ?) = 1(то есть выполняется мультипликативность)
Доказательство:
Рассмотрим числа от 1 до ?? таким образом:
1 2 … m
?+1 ?+2 … 2?
…
?(?-1)+1 ?(n-1)+2 … ??
Обратим внимание на случайный столбец:
? В этом столбце полная система вычетов по модулю ?. Пусть не так, тогда выполняется равенство:
?+? ?+?? ≡ ?+?? (mod ?), где НУО 0 ≤ ? < ? ≤ ?-1
… То есть ?(?-?)⋮? ⇒ ?-? ⋮ ? (?!)
?+?(?-1)
Тогда ?,…, ?+?(?-1) дают все остатки от деления на ? ровно по 1 разу, из которых ?(?) взаимно простых с ?.
Заметим, что если (?, ?) ≠ 1, то все числа в столбце не взаимно просты с ?, значит они не взаимно просты с ??. Тогда подобных столбцов ?(?).
Итого у нас ?(?) столбцов, где ?(?) чисел, взаимно простых с ?. Значит, в таблице ?(?)?(?) чисел взаимно простых с ??. Получается, что ?(??) = ?(?)?(?) ◼︎