Задание №177051: Турнир городов

7. [12] Некоторые из чисел 1, 2, 3, ..., n покрашены в красный цвет так, что выполняется условие:
если для красных чисел a, b, c (не обязательно различных) a(b − c) делится на n, то b = c.
Докажите, что красных чисел не больше чем (n). (Александр Семенов)

Лемма. Пусть D – некоторое множество различных простых делителей числа n. Количество

 1 
натуральных чисел, не превосходящих n и не кратных ни одному числу из D , равно n1 .
 
 p 
pD
Доказательство. Раскрыв скобки, получаем формулу включений-исключений. 

Пусть красных чисел больше φ(n). Тогда некоторые красные числа имеют с n общий простой
делитель. Пусть q – наибольшее из таких простых и a – красное число, кратное q. Для противоречия
n
достаточно найти различные красные числа b и c, сравнимые по модулю , а для этого достаточно
q
показать, что φ(n) больше количества возможных остатков красных чисел по модулю
n
q
.
 1 
По лемме, φ(n) = n1 , где D – множество всех простых делителей у n, а указанное коли-
 
 p 
pD
чество остатков не больше, чем
n
q
p 
D
, p  q

1 
1
p

.
Достаточно доказать, что n p
 D

1 
1
p

>
n
q
p 
D
, p  q

1 
1
p

.
Сокращая на n и на скобки, в которых p>q, получаем
 1   1  1 p
1   1   , что равносильно неравенству q 1  .
   
 q   p  q p 1
pD,pq pD,pq
Оно верно, поскольку q – 1 =
q
q


1
2

q
q


2
3
 . . . 
3
2

2
1
.