Задача
NT-B2-M12-P009 Проверка по остаткам
#9
★★★☆☆ Уровень 3 из 5
Пусть \(f\in\mathbb Z[x]\), \(m\ge1\). Докажите: если \(m\mid f(r)\) для всех \(r=0,1,\ldots,m-1\), то \(m\mid f(n)\) для всех целых \(n\). Примените это к доказательству \(6\mid n^3-n\).
Каждое \(n\) сравнимо с одним из остатков \(r\).
Пусть \(n\equiv r\pmod m\), \(0\le r
Можно обсудить, когда проверка по остаткам практична, а когда лучше искать факторизацию.