Задача
ALG-B3-M06-P004 Циклическая рекурсия
#4
★★☆☆☆ Уровень 2 из 5
Пусть \(f\) задана на остатках по модулю \(7\) и \(f(x+1)\equiv f(x)+1\pmod 7\). Докажите, что \(f(x)\equiv x+c\pmod 7\) для некоторого \(c\).
Начните с \(c=f(0)\).
Пусть \(c=f(0)\). По индукции \(f(1)\equiv c+1\), \(f(2)\equiv c+2\), и так далее. Так как все значения считаются по модулю \(7\), получаем \(f(x)\equiv c+x\pmod 7\) для каждого остатка \(x\).
Короткая задача на конечный домен и модульные равенства.