Районная олимпиада, 2012-2013 учебный год, 8 класс

Делится ли число $1+2+2^2+2^3+\dots+2^{77}$ на 7?

Комментарий/решение

$a^n - b^n = (a - b)(a^{n - 1} + a^{n - 2}b + \ldots + ab^{n - 2} + b^{n - 1})$

$2^{78}-1 = (2^3)^{26}-1 = (2^3-1)((2^3)^{25}+(2^3)^{24}+\ldots+2^3+1)=7 \cdot ((2^3)^{25}+(2^3)^{24}+\ldots+2^3+1).$ Следовательно, разделив данное число на 7 получим $((2^3)^{25}+(2^3)^{24}+\ldots+2^3+1),$ то есть $(2^{78}-1) \vdots 7.$

1+x+x^2+x^3+....+x^n=((x^n+1)-1)/x-1

Подставим нашу задачку под эту формулу и получим: (2^78)-1 = (8^26)-1

При делении 8^26 на 7, он дает остаток 1, в итоге в остатке остается: (1^26)-1=0

Значит (2^78)-1 делится на 7

$1+2+2^2=7$

$1+2+2^2+...+2^{77} = 2^0(1+2+2^2)+2^3(1+2+2^2)+2^6(1+2+2^2)+...+2^{75}(1+2+2^2) \equiv 0 \pmod{7}$

Шешуі: Мына өте әдемі заңдылықты (формуланы) жадыңда сақтаған абзал.

\[a_0 + a_1 + a_2 + a_3 + \ldots + a_n = \frac{a^{n+1}-1}{a-1}\]

Осы формула негізінде қосындыны оңай табуға болады:

\[1 + 2 + 2^2 + 2^3 + \ldots + 2^{77} = \frac{2^{77+1}-1}{2-1} = 2^{78} - 1\]

\[2^{78} - 1 = (2^{39} - 1) \cdot (2^{39} + 1) = (2^{38} - 1) \cdot (2^{38} + 1) = \ldots = (2^{36} - 1) \cdot (2^{36} + 1)\]

\[23(236 - 1) + 7 = (218 - 1) \cdot (218 + 1) = (29 - 1) \cdot (29 + 1) = 511(29 + 1)\]

Сонымен, 511 саны 7-ге қалдықсыз бөлінгендіктен 23(236 - 1) + 7 санының алғашқы саны 7-ге қалдықсыз бөлінеді. Жауабы: 7-ге бөлінеді.