Разделы 
Дополнительно
Задача по математике - 2808
2019-05-06 
а) Доказать, что из пяти последовательных целых чисел всегда можно выбрать одно, взаимно простое со всеми остальными.
б) Доказать, что из 16 последовательных целых чисел всегда можно выбрать одно число, взаимно простое со всеми остальными.
Решение:
а) Если два неравных числа отличаются одно от другого я» больше чем на 4, то они не могут иметь общих делителей, больших 4.
Таким образом, два числа из наших пяти последовательных чисел могут иметь или общий делитель 2, или общий делитель 3, или общий делитель 4, или быть взаимно простыми. Из пяти последовательных чисел, по крайней мере, два будут нечетны; из двух последовательных нечетных чисел, по крайней мере, одно не будет делиться на 3. Следовательно, среди наших чисел имеется хотя бы одно нечетное число, не делящееся на 3; это число заведомо будет взаимно просто с остальными четырьмя числами.
б) Решение этой задачи близко к решению задачи а), но значительно сложнее. Если два неравных числа отличаются друг от друга не больше чем на 15, то они не могут иметь общих делителей больших 15. Так как два числа заведомо взаимно просты, если они не имеют общих простых делителей, но, для того, чтобы доказать нашу теорему, достаточно показать, что среди 16 последовательных целых чисел можно найти число, не имеющее с остальными 15 числами - общих делителей 2, 3, 5, 7, и 13: это число и будет взаимно просто со всеми остальными.
Прежде всего, из 16 чисел вычеркнем как не удовлетворяющие нашим требованиям восемь четных чисел; после этого у нас останется восемь последовательных нечетных чисел. Из восьми последовательных нечетных чисел, очевидно, на 3 делятся или 1-е, 4-е, 7-е, или 2-е, 5-е, 8-е, или 3-е, 6-е; на 5 делятся или 1-е и 6-е, или 2-е и 7-е, или 3-е и 8-е, или же только одно число; на 7 делятся или 1-е и 8-е, или же только одно число; на 11 н 13 делится не больше одного числа. Если среди наших восьми последовательных нечетных чисел имеется не больше пяти чисел, делящихся на 3, или на 5, или на 7, но среди этих восьми чисел найдется число, не делящееся ни на 3, ни на 5, ни на 7, ни на 11, ни на 13; это число заведомо будет взаимно просто со всеми остальными. Рассмотрим теперь все те случаи, когда чисел, делящихся или на 3, или на 5, или на 7, будет не меньше 6.
Пусть среди наших восьми нечетных последовательных чисел на 3 делятся три числа; тогда на 5 могут делиться два из оставшихся чисел только в том случае, если одно из крайних чисел делится на 3, а второе - на 5. Вычеркнув эти пять чисел, мы оставим 2-е, 5-е и 6-е числа, или же 7-е, 4-е, и 3-е числа. Рассмотрим сначала первый случай 2-е, 5-е и 6-е нечетные числа являются в ряду всех 16 последовательных чисел 4-м, 10-м и 12-м или 3-м, 9-м и 11-м числами. Ни одно из этих чисел не может иметь ни с одним из остальных 15 чисел общий делитель 13, так как каждое из остальных чисел отличается от него меньше чем на 13. Следовательно, если эти три числа не делятся ни на 3, ни на 5, то одно из них (а именно, то, которое не делится ни на 7, ни на 11) будет взаимно просто со всеми остальными числами. Точно так же проводится доказательство и в том случае, когда после вычеркивания чисел, делящихся на 3 и на 5, остаются 3-е, 4-е и 7-е числа.
Если из наших восьми чисел на 3 делятся три числа, то на 7 не могут делиться никакие два из оставшихся. Если же на 3 делятся только два числа, 3-е и 6-е, то возможно, что из оставшихся на 7 делятся два, а именно 1-е и 8-е, и на 5 делятся два: 2-е и 7-е. Вычеркнув эти шесть чисел, мы оставим из наших восьми нечетных чисел 4-е и 5-е, которые не будут уже делиться ни на 3, ни на 5, ни на 7. Оба эти числа будут взаимно простыми с каждым из остальных 15 чисел нашей последовательности, так как каждое из остальных чисел отличается от них меньше чем на 11 и поэтому не может иметь с ними общий делитель 11 или 13.
Итак, мы полностью доказали, что из 16 последовательных целых чисел всегда можно выбрать одно, взаимно простое с остальными.
а) Доказать, что из пяти последовательных целых чисел всегда можно выбрать одно, взаимно простое со всеми остальными.
б) Доказать, что из 16 последовательных целых чисел всегда можно выбрать одно число, взаимно простое со всеми остальными.
Решение:
а) Если два неравных числа отличаются одно от другого я» больше чем на 4, то они не могут иметь общих делителей, больших 4.
Таким образом, два числа из наших пяти последовательных чисел могут иметь или общий делитель 2, или общий делитель 3, или общий делитель 4, или быть взаимно простыми. Из пяти последовательных чисел, по крайней мере, два будут нечетны; из двух последовательных нечетных чисел, по крайней мере, одно не будет делиться на 3. Следовательно, среди наших чисел имеется хотя бы одно нечетное число, не делящееся на 3; это число заведомо будет взаимно просто с остальными четырьмя числами.
б) Решение этой задачи близко к решению задачи а), но значительно сложнее. Если два неравных числа отличаются друг от друга не больше чем на 15, то они не могут иметь общих делителей больших 15. Так как два числа заведомо взаимно просты, если они не имеют общих простых делителей, но, для того, чтобы доказать нашу теорему, достаточно показать, что среди 16 последовательных целых чисел можно найти число, не имеющее с остальными 15 числами - общих делителей 2, 3, 5, 7, и 13: это число и будет взаимно просто со всеми остальными.
Прежде всего, из 16 чисел вычеркнем как не удовлетворяющие нашим требованиям восемь четных чисел; после этого у нас останется восемь последовательных нечетных чисел. Из восьми последовательных нечетных чисел, очевидно, на 3 делятся или 1-е, 4-е, 7-е, или 2-е, 5-е, 8-е, или 3-е, 6-е; на 5 делятся или 1-е и 6-е, или 2-е и 7-е, или 3-е и 8-е, или же только одно число; на 7 делятся или 1-е и 8-е, или же только одно число; на 11 н 13 делится не больше одного числа. Если среди наших восьми последовательных нечетных чисел имеется не больше пяти чисел, делящихся на 3, или на 5, или на 7, но среди этих восьми чисел найдется число, не делящееся ни на 3, ни на 5, ни на 7, ни на 11, ни на 13; это число заведомо будет взаимно просто со всеми остальными. Рассмотрим теперь все те случаи, когда чисел, делящихся или на 3, или на 5, или на 7, будет не меньше 6.
Пусть среди наших восьми нечетных последовательных чисел на 3 делятся три числа; тогда на 5 могут делиться два из оставшихся чисел только в том случае, если одно из крайних чисел делится на 3, а второе - на 5. Вычеркнув эти пять чисел, мы оставим 2-е, 5-е и 6-е числа, или же 7-е, 4-е, и 3-е числа. Рассмотрим сначала первый случай 2-е, 5-е и 6-е нечетные числа являются в ряду всех 16 последовательных чисел 4-м, 10-м и 12-м или 3-м, 9-м и 11-м числами. Ни одно из этих чисел не может иметь ни с одним из остальных 15 чисел общий делитель 13, так как каждое из остальных чисел отличается от него меньше чем на 13. Следовательно, если эти три числа не делятся ни на 3, ни на 5, то одно из них (а именно, то, которое не делится ни на 7, ни на 11) будет взаимно просто со всеми остальными числами. Точно так же проводится доказательство и в том случае, когда после вычеркивания чисел, делящихся на 3 и на 5, остаются 3-е, 4-е и 7-е числа.
Если из наших восьми чисел на 3 делятся три числа, то на 7 не могут делиться никакие два из оставшихся. Если же на 3 делятся только два числа, 3-е и 6-е, то возможно, что из оставшихся на 7 делятся два, а именно 1-е и 8-е, и на 5 делятся два: 2-е и 7-е. Вычеркнув эти шесть чисел, мы оставим из наших восьми нечетных чисел 4-е и 5-е, которые не будут уже делиться ни на 3, ни на 5, ни на 7. Оба эти числа будут взаимно простыми с каждым из остальных 15 чисел нашей последовательности, так как каждое из остальных чисел отличается от них меньше чем на 11 и поэтому не может иметь с ними общий делитель 11 или 13.
Итак, мы полностью доказали, что из 16 последовательных целых чисел всегда можно выбрать одно, взаимно простое с остальными.
