Нет, степени надо тоже учитывать,конечно. Если есть число (m*n+k)^p, то его остаток при делении на n равен k^p.