В каких числах n деление происходит без остатка?

Question

[Yeldos Adetbekov]

(x+1)^n-x^n-1\\\ x^2+x+1
:)
\\\ - делимость (три точки вертикальные)

Answer 1

[xmoonlight]

https://ru.wikipedia.org/wiki/%D0%A2%D0%B5%D0%BE%D...

Answer 2

[Mrrl]

Получается n=6*m+1 и 6*m+5. Надо воспользоваться тем, что (x+1)^2 mod (x^2+x+1) = x, рассмотреть отдельно случаи n=2*k и n=2*k+1, в каждом умножить обе части на (x-1) и искать P*(x-1) mod (x^3-1). Там x^(3*a+b) mod (x^3-1) = x^b, а в многочлене P после применения первого тождества останется 3 или 4 слагаемых, так что считать несложно.