Задача 78218

Темы:    [ Разложение на множители ] [ Арифметика остатков (прочее) ]

Сложность: 3 Классы: 8,9,10

Условие

a, b и n – натуральные числа, и n нечётно. Докажите, что если числитель и знаменатель дроби     делятся на n, то и сама дробь делится на n.

Решение

По условию  a ≡ – b (mod n),  а значит,   = a^n–1 – a^n–2b + ... – ab^n–1 + bⁿ ≡ nb^n–1 ≡ 0 (mod n).

Замечания

1. В исходном варианте задачи (на Московской олимпиаде) условие нечётности отсутствовало. Но тогда утверждение неверно: контрпример
a = b = 1,  n = 2.

2. Ср. с задачей 78682.

Источники и прецеденты использования

олимпиада
Название	Московская математическая олимпиада
год
Номер	23
Год	1960
вариант
	1
Класс	10
Тур	1
задача
Номер	2