No 2
интернет-провайдер хочет проложить новую
сеть. в стране 7 городов, которые нужно
соединить между собой так, чтобы из каждого
города можно было посылать сообщение в
любой другой (возможно, через другие города).
для прокладывания оптоволоконной линии
между двумя требуется потратить
некоторое количество денег. стоимость
прокладки сети между двумя
записана на линии, соединяющей эти города.
какие оптоволоконные линии должны быть
проложены, чтобы соединить все города
потратив меньше всего денег?
решение оформите на отдельном листе и сдайте в штаб конкурса -
кабинет no 24. обязательно подпишите номер и класс
Основная теорема арифметики утверждает[1][2]:
Каждое натуральное число {\displaystyle n>1}n>1 можно представить в виде {\displaystyle n=p_{1}\cdot \ldots \cdot p_{k}}{\displaystyle n=p_{1}\cdot \ldots \cdot p_{k}}, где {\displaystyle p_{1},\ldots ,p_{k}}{\displaystyle p_{1},\ldots ,p_{k}} — простые числа, причём такое представление единственно, если не учитывать порядок следования множителей.
Если формально условиться, что произведение пустого множества чисел равно 1, то условие {\displaystyle n>1}n>1 в формулировке можно опустить, тогда для единицы подразумевается разложение на пустое множество простых: {\displaystyle 1=1}{\displaystyle 1=1}[3][4].
Как следствие, каждое натуральное число {\displaystyle n}n единственным образом представимо в виде
{\displaystyle n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k}},}{\displaystyle n=p_{1}^{d_{1}}\cdot p_{2}^{d_{2}}\cdot \ldots \cdot p_{k}^{d_{k}},} где {\displaystyle p_{1}<p_{2}<\ldots <p_{k}}{\displaystyle p_{1}<p_{2}<\ldots <p_{k}} — простые числа, и {\displaystyle d_{1},\ldots ,d_{k}}{\displaystyle d_{1},\ldots ,d_{k}} — некоторые натуральные числа.
Такое представление числа {\displaystyle n}n называется его каноническим разложением на простые сомножители.
Пошаговое объяснение:
1) 64 = 2⁶; 54 = 2 · 3³
НОК (64 и 54) = 2⁶ · 3³ = 1728 - наименьшее общее кратное
1728 : 64 = 27 1728 : 54 = 32
2) 95 = 5 · 19; 114 = 2 · 3 · 19
НОК (95 и 114) = 2 · 3 · 5 · 19 = 570 - наименьшее общее кратное
570 : 95 = 6 570 : 114 = 5
3) 100 = 2² · 5²; 125 = 5³
НОК (100 и 125) = 2² · 5³ = 500 - наименьшее общее кратное
500 : 100 = 5 500 : 125 = 4
4) 121 = 11²; 88 = 2³ · 11
НОК (121 и 88) = 2³ · 11² = 968 - наименьшее общее кратное
968 : 121 = 8 968 : 88 = 11
5) 168 = 2³ · 3 · 7; 140 = 2² · 5 · 7
НОК (168 и 140) = 2³ · 3 · 5 · 7 = 840 - наименьшее общее кратное
840 : 168 = 5 840 : 140 = 6
6) 144 = 12²; 324 = 2² · 3⁴
Числа 144 и 324 взаимно простые, так как у них нет общих делителей, кроме единицы
НОК (144 и 324) = 144 · 324 = 46656 - наименьшее общее кратное
7) 125 = 5³; 225 = 3² · 5²
НОК (125 и 225) = 3² · 5³ = 1125 - наименьшее общее кратное
1125 : 125 = 9 1125 : 225 = 5
8) 185 = 5 · 37; 111 = 3 · 37
НОК (185 и 111) = 3 · 5 · 37 = 555 - наименьшее общее кратное
555 : 185 = 3 555 : 111 = 5