Ученик решил построить таблицу умножения всех целых неотрицательных чисел меньших некоторого натурального числа n. При этом он все время делал одну и ту же ошибку — вместо значения произведения записывал в таблицу остаток от деления этого произведения на число n. Например, таблица для n = 4 приведена на рисунке.
| x | 0 | 1 | 2 | 3 |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 2 | 3 |
| 2 | 0 | 2 | 0 | 2 |
| 3 | 0 | 3 | 2 | 1 |
а) Может ли на диагонали такой таблицы стоять ровно 9 нулей?
б) Может ли общее количество нулей (не считая тех, которые находятся в первой строке или первом столбце — шапке таблицы) в таблице быть равным 41?
в) Найдите максимальное количество нулей в одной строке таблицы (исключая строку со всеми нулями), если n — нечетное и 15 ≤ n ≤ 35.
Нуль возникает в таблице в случае, когда ab кратно n, при этом числа a и b не превосходят n − 1.
а) Да. Пусть, например, n = 81. Тогда a2 кратно 81 в том и только том случае, когда a кратно 9. Таких чисел ровно девять: 0, 9, 18, ..., 72.
б) Поскольку в строке и столбце с умножением на 0 точно все клетки заполнены нулями, а их 2n − 1, то 2n − 1 ≤ 41, откуда n ≤ 21. Если n простое, то других клеток с нулями и нет; но 21 не простое число. Если n ≤ 6, то всего в таблице не более 36 клеток.
Если число имеет вид pq, где p и q простые, то один из множителей кратен p, а второй q или один из множителей нулевой. Имеется p − 1 число, кратное q, и q − 1 число, кратное p (кроме нулей). Значит, всего вариантов
но 41 не раскладывается на множители иначе как 41 · 1. Но тогда q = 1, что невозможно.
Итак, осталось проверить только составные числа от 7 до 21 и при этом не вида pq, то есть 8, 9, 12, 16, 18, 20. На диагонали должно быть ровно 41 − (2n − 1) = 42 − 2n — четное число нулей (кроме клетки 0 · 0 — она уже посчитана).
Для n = 8 такая клетка только 4 · 4.
Для n = 9 только 3 · 3 и 6 · 6
Для n = 12 только 6 · 6.
Для n = 16 только 4 · 4, 8 · 8 и 12 · 12.
Для n = 18 только 6 · 6 и 12 · 12.
Для n = 20 только 10 · 10.
Теперь осталось разобрать случаи n = 9 и n = 18. Будем перечислять только произведения с ненулевыми множителями.
При n = 9 подходят 3 · 3, 3 · 6, 6 · 3, 6 · 6, итого 
При n = 18 подходят 2 · 9, 4 · 9, ..., 16 · 9, что уже дает 
вариант.
Требуемое невозможно.
в) Допустим это строка для числа a. Нас интересует количество таких b, что ab кратно n. Заметим, что любые два таких b отличаются минимум на 3 (поскольку если ab и a(b + 1) кратно n, то и их разность a кратна n, а если ab и a(b + 2) кратно n, то и их разность 2a кратна n, а тогда и a кратно n поскольку n нечетно. Значит, количество таких b не более чем 
округленное вверх. При всех n, кроме 35, это не более 11 (а при n = 33 можно взять a = 11 и все кратные 3 числа на роль b). При n = 35 подходящие числа не могут отличаться и на 3, поскольку если ab и a(b + 3) кратны 35, то и 3a, а с ним и a кратно 35, поэтому для 35 этих чисел не более 
с округлением вверх, что равно 9.
Ответ: а) да; б) нет; в) 11.