Задача
ALG-B3-M06-P013 Аддитивность по модулю
#13
★★★★☆ Уровень 4 из 5
Пусть \(p\) - простое, \(f:\mathbb Z/p\mathbb Z\to\mathbb Z/p\mathbb Z\), и \(f(x+y)=f(x)+f(y)\). Докажите, что \(f(x)=ax\) для некоторого остатка \(a\).
Каждый остаток равен сумме нескольких единиц.
Пусть \(a=f(1)\). Для остатка \(x\) имеем \(x=1+\cdots+1\) по модулю \(p\). Тогда \(f(x)=xf(1)=ax\). Это верно и для \(x=0\), так как \(f(0)=0\).
Основной факт для финальных модульных задач.