Question

Сколько существует натуральных чисел, которые меньше 20^13, и квадрат которых делится на 13 без остатка? И объясните, пожалуйста, свой ход решения

Answer 1

Ответ:  k= (20^13-7)/13

Можно  посчитать и проверить:

k=6301538461538461

Пошаговое объяснение:

Все просто . Тк  13  простое число,  то  если  n^2  делиться на 13, то  и n делится на 13.  Тк  13 можно  разбить одним способом в виде произведения натуральных  чисел 13*1 ,то  n в любом случае делится на 13.   Таким образом  задаче удовлетворяют все числа кратные 13.  То  есть:  13*1 ;13*2 ;....13*k

13*k<=20^13

Чтобы найти наибольшее k необходимо отыскать  остаток от  деления

20^13  на  13    

Найдем закономерность чередования остатков  20^m на 13.

Тк остатков ограниченное количество, то рано или поздно остаток повторится с каким то  из предыдущих , это  и будет период чередования.  Умножаем сразу на предыдущий остаток,тк 20*13*f делится на 13 :

20= 13 +7   (-6)

20*7=140= 10*13+10 (10) (-3)

20*10=200= 13*15+5 (5) (-8)

20*5=100=13*7+9 (9)   (-4)

20*9=180=13*13+11 (11)   (-2)

20*11=220=13*16 +12  (12)   (-1)  

20*12=240=13*18+6 (-7) (повтор)

Таким образом остатки чередуются по  закону:

7,10,5,9,11,12,-7,-10,-5,-9 ,-11,-12,7,10... (период равен 12)

Остаток от деления 13 на  12  равен 1, таким образом остаток от деления

20^13 на 13  равен  7.

Тогда  таких чисел:

 k= (20^13-7)/13

P.s  найдем например остаток от деления:

20^100  на  13  

Для  этого ищем остаток от  деления  100 на 12

100=12*8+4.  Таким образом нам нужно 4 число в периоде:

7,10,5,9,11,12,-7,-10,-5,-9 ,-11,-12

Таким  образом  остаток от деления :

20^100 на 13 равен 9.