p и q - такие натуральные числа, что
p/q=1-1/2+1/3-1/4+...-1/1318+1/1319.
Докажите, что p делится на 1979.
Задача была предложена на Международной математической олимпиаде в 1979 году.
Преобразуем дробь:
1-1/2+1/3-1/4+...-1/1318+1/1319=
(1+1/2+1/3+...+1/1318+1/1319)-2(1/2+1/4+...+1/1318)=
(1+1/2+1/3+...+1/1318+1/1319)-(1+1/2+...+1/659)=
1/660+1/661+...+1/1318+1/1319.
Теперь перегруппируем слагаемых в получившейся дроби:
(1/660+1/1319)+(1/661+1/1318)+...=
1979/(660*1319)+1979/(661*1318)+...=1979*A/B,
где A/B=1/(660*1319)+1/(661*1318)+...
Но 1979 - простое число, а все сомножители в знаменателе, которые получаются при приведении к общему знаменателю, меньше, чем 1979. Значит, ему не с чем сократиться.
Если же знать не только, что 1979 - простое число, но и помнить малую теорему Ферма, то можно придумать и такое решение.
Заметим, что 1/k=k^1977 mod 1979. Поэтому
1-1/2+1/3-1/4+...-1/1318+1/1319=
1^1977-2^1977+3^1977-4^1977+...-1318^1977+1319^1977=
(1^1977+2^1977+3^1977+4^1977+...+1318^1977+1319^1977)-2(2^1977+4^1977+...+1318^1977)=
(1^1977+2^1977+3^1977+4^1977+...+1318^1977+1319^1977)-2*2^1977*(1^1977+2^1977+...+659^1977)=
(1^1977+2^1977+3^1977+4^1977+...+1318^1977+1319^1977)-(1^1977+2^1977+...+659^1977)=
(660^1977+661^1977+...+1318^1977+1319^1977)=
(660^1977+(1979-660)^1977)+(661^1977+(1979-661)^1977)+...=
(660^1977+(-660)^1977)+(661^1977+(-661)^1977)+...=0.
1