Даю 100 баллов, олимпиадная задача по алгебре 8 класс на арифметику остатков
У Пети есть тринадцать карточек с числами от 1 до 13
Он хочет взять как можно больше из них так, чтобы их произведение давало остаток 9 при делении на 14
Сколько чисел он возьмёт? Введите все числа, которые он возьмет
Ответы
Ответ:
Максимальное кол-во чисел которое мог взять Петя равно 5-ти , а взял он числа : 13,5,1,11,9
Объяснение:
Если число m при делении на число k дает остаток r , а при делении n на k дает остаток s , то остаток от деления произведения m·n на k , равен остатку от деления произведения остатков s·r на k
Как пример :
Найти остаток от деления числа 72·83 на 7
72 : 7 = 10 (ост 2)
83 : 7 = 11(ост 6)
Находим остаток , от деления произведения остатков на 7
2·6 : 7 = 12 : 7 = 1 (ост 5)
С помощью данного алгоритма можно довольно просто решить данную задачу
( 14k + 9 подставляя место k = 1,2,3 ... находим число 65)
13·5 = 65 : 14 = 14 (ост 9)
65 = 13·5
Теперь же , просто находим числа которые при делении на 14 дают остаток 1 , т.к согласно выше указанному алгоритму мы умножим остаток равный 9 на 1 , и поэтому он никак не изменится
Ищем такие пары пары произведений чисел , 14k + 1-остаток подставляя вместо k числа от 1 до 11 , поскольку наибольшее произведение чисел на карточках равно 13·12 = 156
0) при k = 0 , 0 + 1 = 1
1) при k = 1 , 14 +1 = 15 = 3·5 , пятерку мы уже брали
2) при k = 2 , 28 + 1 = 29 простое число , и данного числа нет среди карточек
3) при k = 3 , 42 + 1 = 43 простое > 13
4) при k = 4 , 57 = 19·3 , а 19 простое > 13
5) при k = 5 , 71 простое > 13
6) при k = 6 , 85 = 17·5 , 17 > 13
7) при k = 7 , 99 = 11·9
8) при k = 8 , 113 простое > 13
9) при k = 9 , 127 простое > 13
10) при k = 10 , 141 = 47·3 , 47 > 13
11) при k = 11 , 155 = 31·5 , 31 > 13
Таким образом , максимальное кол-во карточек которое мог взять Петя равно 5-ти , а взял он карточки 13,5,1,11,9