Квант
Задачник

Задача M309

Условие: Квант 1975, №2, с. 26-27Решение: Квант 1975, №10, с. 40-47Тег GG60

Условие

a) При каких nn многочлен x2n+x+1x^{2n} + x + 1 делится на x2+x+1x^2 + x + 1?
6) При каких nn число
10…010…0110 \dots 010 \dots 01
делится на 37?

В. Г. Шлейфер

Решение

a) При каких nn многочлен x2n+xn+1x^{2n} + x^n + 1 делится на x2+x+1x^2 + x + 1?**

б) При каких nn число

10…0⏟n1…0⏟n1 \underbrace{0 \dots 0}_{n} \underbrace{1 \dots 0}_{n}

делится на 37?

a) Рассмотрим три случая, соответствующие различным остаткам от деления nn на 3.

1°. Пусть n=3kn=3k; тогда

x6k+x3k+1=(x6k−1)+(x3k−1)+3=x^{6k} + x^{3k} + 1 = (x^{6k} - 1) + (x^{3k} - 1) + 3 =
=(x3−1)(x6k−3+x6k−6+⋯+1)+= (x^3 - 1)(x^{6k} - 3 + x^{6k} - 6 + \dots + 1) +
+(x3−1)(x3k−3+x3k−6+⋯+1)+3=+ (x^3 - 1)(x^{3k} - 3 + x^{3k} - 6 + \dots + 1) + 3 =
=(x2+x+1)⋅Q(x)+3,= (x^2 + x + 1) \cdot Q(x) + 3,

где Q(x)=(x−1)[(x6k−3+x6k−6+⋯+1)+(x3k−3+⋯+1)]Q(x) = (x - 1)[(x^{6k} - 3 + x^{6k} - 6 + \dots + 1) + (x^{3k} - 3 + \dots + 1)].

Следовательно, если n=3kn=3k, то многочлен x2n+xn+1x^{2n} + x^n + 1 при делении на x2+x+1x^2 + x + 1 дает в остатке 3.

2°. Пусть n=3k+1n=3k + 1. Имеем

x6k+2+x3k+1+1=(x6k+2−x2)+(x3k+1−x)+x^{6k + 2} + x^{3k + 1} + 1 = (x^{6k + 2} - x^2) + (x^{3k + 1} - x) +
+(x2+x+1)=x2(x6k−1)+x(x3k−1)+(x2+x+1)+ (x^2 + x + 1) = x^2(x^{6k} - 1) + x(x^{3k} - 1) + (x^2 + x + 1)

В 1° мы показали, что многочлены (x6k−1)(x^{6k} - 1) и (x3k−1)(x^{3k} - 1) делятся на (x3−1)(x^3 - 1), следовательно, и на (x2+x+1)(x^2 + x + 1); поэтому при n=3k+1n=3k + 1 многочлен x2n+xn+1x^{2n} + x^n + 1 делится на x2+x+1x^2 + x + 1.

3°. Пусть n=3k+2n=3k + 2. Тогда

x6k+4+x3k+2+1=x1(x6k−1)+x2(x3k−1)+x4+x2+x^{6k + 4} + x^{3k + 2} + 1 = x^1(x^{6k} - 1) + x^2(x^{3k} - 1) + x^4 + x^2 +
+1=x4(x6k−1)+x2(x3k−1)+x3−1+(x2+x+1)=(x2+x+1)[(x−1)R(x)+1],+ 1 = x^4(x^{6k} - 1) + x^2(x^{3k} - 1) + x^3 - 1 + (x^2 + x + 1) = (x^2 + x + 1)[(x - 1)R(x) + 1],

где R(x)=x4(x6k−3+⋯+1)+x2(x3k−3+⋯+1)+xR(x) = x^4(x^{6k} - 3 + \dots + 1) + x^2(x^{3k} - 3 + \dots + 1) + x, и многочлен x2n+xn+1x^{2n} + x^n + 1 снова делится на x2+x+1x^2 + x + 1.

*) Аналогично решена эта задача в книге Полина и Сете «Задачи и теоремы из анализа».

42

Итак, ответ в задаче a) таков:
многочлен x2n+xn+1x^{2n} + x^n + 1 делится на x2+x+1x^2 + x + 1, если nn не кратно трех.

  1. При решении этой задачи можно воспользоваться результатом пункта a), поскольку все многочлены, получающие при делении — частиные и остатки — имеют целые коэффициенты. Действительно, при x=10x = 10 мы получим соответствующее
    x2+x+1=111,x2(n+1)+x(n+1)+1=10…0⏟n1…0⏟n.x^2 + x + 1 = 111, x^{2(n+1)} + x^{(n+1)} + 1 = 1 \underbrace{0 \ldots 0}_{n} \underbrace{1 \ldots 0}_{n}.
    С другой стороны, 102m+10m+110^{2m} + 10^m + 1 делится на 3 при всех mm, и вопрос о том, делится ли 102m+10m+110^{2m} + 10^m + 1 на 37, эквивалентен вопросу о делимости 102m+10m+110^{2m} + 10^m + 1 на 37.3 = 111. Ответ в этой задаче такой: число 10…0⏟n10…0⏟n\underbrace{10 \ldots 0}_{n} \underbrace{10 \ldots 0}_{n} делится на 37, если nn кратно 3 или если nn при делении на 3 дает остаток 1.
    Ф. Г. Шлейфер