Question

Даю 100 баллов, олимпиадная задача по алгебре 8 класс на арифметику остатков У Пети есть тринадцать карточек с числами от 1 до 13 Он хочет взять как можно больше из них так, чтобы их произведение давало остаток 9 при делении на 14 Сколько чисел он возьмёт? Введите все числа, которые он возьмет

Answer 1

Ответ:

Максимальное кол-во  чисел  которое мог взять Петя  равно  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