#80. HARD PROBLEM ABOUT THE GREATEST COMMON DIVISOR! (№19, math exam)

A tough task in number theory at the USE in mathematics (No. 19). Decide, look, study, ask questions!
TASK TO ALL VIDEOS: wall-135395111_8104
SPEED UP THE PROCESS OF CREATING A NEW VIDEO: www.donationalerts.ru/r/wildma...
VK: wildmathing
PAY ATTENTION: in the video I say a lot about the fact that the 11th, 13th and 17th numbers are simple, it’s true, but the main thing is that they are mutually simple with any others from the set. Let's say the number 7 is prime, but that does not mean that the greatest common divisor of seven and any other number is equal to one. Here is a simple counterexample: GCD (7; 14) = 7.
The current task will not be easy: three points after all, which means composite. But there will be something simple in its composition. Not complexity, of course, rather numbers. In general, success!
Condition. In a circle, in a certain order, once written numbers from 9 to 18. For each of ten pairs of neighboring numbers found their greatest common divisor.
a) Could it be that all the largest common divisors are equal to 1?
b) Could it be that all the largest common divisors are pairwise distinct?
c) What is the greatest number of pairwise distinct greatest common divisors that could result?
MORE STEPS ON THE THEORY OF NUMBERS
1. The most difficult task on KZbin: • #141. СОЧНАЯ ЗАДАЧА ПО...
2. A beautiful task from the exam: • #151. КРАСИВАЯ ЗАДАЧА ...
3. The problem of sets and subsets: • #77. КАК РЕШАТЬ ЗАДАЧИ...

[@planetrinaaa]

Что конкретно означает "попарно различны"? Вроде бы, должно быть очевидно, но что-то сомнения закрались..

[@WildMathing]

Да, эта фраза любопытная. Смотрите: нашли мы, значит, десяток наибольших общих делителей. Если среди них какие два не выбрать - окажутся разными, то вывод: наши наибольшие общие делители попарно различны. Проще говоря, попарно различный набор чисел означает то, что в наборе не имеется одинаковых чисел.

[@planetrinaaa]

спасибо!)

[@user-jx2pf3pn7x]

4 минуты. 4 минуты - и 4 балла в кармане. 4 минуты - и сбудутся все мечты. Но на экзамене я просижу 40 минут и, максимум, сделаю первый пункт. Пристрелите меня.

[@-umnica-]

Изучив метод оценки+пример с методички Яковлева, даже эта задача для такого идиота как я становится решаемой за час полностью!Спасибо за вашу подачу, и за великолепные материалы!

[@AlexeyEvpalov]

Спасибо за подробное обоснованное решение.

[@elnurbda]

большое спасибо за видеоролик!

[@moxeeem3045]

что это было... почему это так круто?

[@user-oc6wk6kz5z]

Сделайте, пожалуйста, серию видео по планиметрии (16 номер)

[@WildMathing]

А как же без планиметрии? Конец апреля, начало мая: vk.com/wall-135395111_215

[@user-oc6wk6kz5z]

Спасибо.

[@koshail8197]

На часть б) рассуждения с избытком. Достаточно увидеть, что на интервале от 9 до 18 есть хотя бы одно простое число - оно даст с каждым соседом НОД=1. Остальное относится уже к части в) Если бы задача состояла только из части б), то приведённые рассуждения были бы ошибочными.

[@WildMathing]

Спасибо за обратную связь! Наша цель - решить всю задачу: если мы заранее позаботились сделать оценку для в) в предыдущих пунктах, то это замечательно. Кроме того, напомню, что если верны утверждения A, B, а также следствие (A ⇒ C), то следствие (A ∧ B) ⇒ С также является верным. Так что если бы задача состояла только из части б), решение было бы засчитано полностью

[@koshail8197]

​@@WildMathing с тем, что решение верное я не спорю. Но для сокращённой задачи оно не оптимальное - достаточно найти один случай, опровергающий исходное утверждение и показать, что избежать такого случая не получится. Я же задумался над другой задачей: доказать, что для любого натурального A>1 есть хотя бы одно простое число P такое, что A

[@ppomogaev9]

А такое доказательство сгодится? НОД может быть только натуральным числом, а соответственно, наибольший из НОД должен быть больше либо равен 10, однако наибольший НОД при данных числах - 9. Мне такое объяснение первым пришло на ум.

[@WildMathing]

Да, это хорошее объяснение пункта б).

[@meinhertz4382]

а можно было в букве б сказать, что раз используется 3 простых числа, для которых в любом случае наибольший общий делитель с кем-либо 1, то как минимум 4 раза наибольшим общим делителем будет единица? или это надо ещё доказать?

[@WildMathing]

Можно, конечно! Доказывать в этой ситуации ничего и не нужно, достаточно сделать акцент на том, что числа 11, 13 и 17 взаимно просты с любыми другими из набора.

[@diegocosta4701]

В пункте А можно было даже проще;) Два последовательных числа всегда взаимнопросты. То есть А не может иметь общих делителей с А+1 Поэтому можно их просто по порядку поставить)

[@WildMathing]

Числа расставляют по кругу, поэтому при таком подходе, увы, 9 и 18 окажутся рядом, и условие выполнено не будет.

[@diegocosta4701]

Wild Mathing точно, я дурак) Ждём ещё разборов

[@WildMathing]

@@diegocosta4701, обязательно будут!

[@user-sr5cu7xp8u]

Wild Mathing можно просто 18 и 17 местами поменять тогда все будет выполнено

[@barsick2380]

@@user-sr5cu7xp8u тогда 16 и 18 будут стоять рядом, а там уже делитель двойка

[@user-xk3qc6nt9k]

Можно же просто для пункта а поставить все числа по кругу начиная от 9 до 18, только в конце надо 18 поменять на 17

[@WildMathing]

Увы, Иван, так не получится: ведь тогда 18 и 16 будут стоять рядом и одновременно делиться на 2.

[@user-xk3qc6nt9k]

@@WildMathing ах да, точно, сорян)

[@WildMathing]

Ничего страшного, бывает!

[@user-xk3qc6nt9k]

@@WildMathing у меня к вам вопрос. Куда можно обратиться? В группу?

[@WildMathing]

Если он может быть интересен в контексте какого-нибудь видео, то лучше прям под видео. Но если что - да, в группу можно написать, на данный момент хотя и не оперативно - наверняка отвечу.

[@user-ch7ts5sq1j]

В пункте а) самый лёгкий пример-просто выписать по порядку числа от 9-18

[@WildMathing]

Увы, в таком примере 18 окажется по соседству с 9.

[@user-ch7ts5sq1j]

@@WildMathing Аа,точно,они же по кругу расположены. Значит я ошибся

[@WildMathing]

@@user-ch7ts5sq1j, да, в этом все дело. Ничего страшного, бывает!

[@woomy_squid]

В) у меня получилочь 8. 11,13,17,14,16,12,15,10,18,9.... 17-14 и 14-16 это 2 попарно различных нода. 18-9 и 9-11 - тоже 2 попарно различных нода. Между ними я насчитал еще 4 штуки. Мб я неправильно посчитал?

[@WildMathing]

Спасибо за интерес! В твоем примере только 6 различных наибольших общих делителей. Максимум их может быть семь: 1, 2, 3, 4, 5, 6, 9. А у тебя отсутствует 6, поскольку числа 12 и 18 не стоят рядом. НОД(17,14)=НОД(9,11)=1, НОД(14,16)=НОД(10,18)=2 - скорее всего вот эти пары ты посчитал дважды. Не разберешься - дай знать!

[@-umnica-]

Добавлю, что вместо канонического разложения просто записал Числа которые делятся на 3, 4, ..., 9 Что дало мне ту же картину, показало то, что 11 13 17-числа простые Вообщем, даже без него можно справиться) Для а) ещё можно рассуждать о чередовании чётных и нечётных чисел, у меня вышел иной круг: 12 11 18 13 10 9 16 15 14 17

[@user-tv3lc6eu2y]

А разве нельзя сказать в пункте б, что у нас есть простые числа в круге, и значит уже нашлись два единичных нода?

[@WildMathing]

Не совсем. Если опираться только на наличие простых чисел, то возможны ситуации в духе НОД(7,14)=7, несмотря на то, что число 7 является простым. Но если объяснить, почему все простые числа здесь являются взаимно простыми с любыми соседями, то рассуждение получится строгим!

[@user-tv3lc6eu2y]

@@WildMathing да, понял в чем неточность, спасибо)