8. Линейное представление НОД. Простые и составные числа
Теорема. Пусть – целые числа,
НОД
. Число
можно представить в виде
, где
— целые числа
Доказательство. Пусть — множество всех чисел, которые можно получить из
и
с помощью сложения и вычитания. Тогда, если
, то
. Так как в алгоритме Евклида
Но .
Следствия.
1. НОД двух чисел делится на любой общий делитель этих чисел.
2. Уравнение , где
— целые коэффициенты,
— целочисленные неизвестные, разрешимо в том и только в том случае, если
делится на НОД
.
Простые и составные числа
Определение. Целое число называется составным, если оно делится на какое-нибудь целое число, отличное от
и
,
и
.
Целое число называется простым, если оно не является составным и не равно .
Замечание. Здесь необходимо отметить, что общепринятым является другое определение простых и составных чисел. Обычно простыми числами называются только натуральные числа. По этому поводу читайте здесь. В этом есть свои удобства и неудобства. В любом случае, когда возникнут сомнения, какие числа имеются в виду, всегда можно задать вопрос.
Теорема. Всякое составное натуральное число можно представить в виде произведения простых натуральных чисел.
Доказательство. Пусть есть такие составные натуральные числа, которые нельзя представить в виде произведения простых. Выберем из этих чисел самое маленькое и обозначим его через . Так как
— составное число, то у него есть делитель
, который больше 1 и меньше
.
Числа натуральные. Каждое из чисел
либо является простым, либо это составное, меньшее
, которое поэтому раскладывается на простые множители. Но тогда и
раскладывается на простые множители. Получили противоречие.
Теорема. Если – целые числа,
— простое число,
, то
или
.
Доказательство. Пусть ни , ни
не делятся на
. Тогда
НОД,НОД
. Следовательно, можно подобрать такие целые числа
и
и такие целые числа
и
, что
Перемножим эти равенства почленно:
Каждое слагаемое в левой части равенства делится на , а
. Получили противоречие.
Теорема. Пусть — составное натуральное число и
где — простые натуральные числа. Пусть
Тогда и
.
Доказательство.
Если в левой и правой части есть равные сомножители, сократим на них и получим равенство такого же вида, в котором ни один сомножитель в левой части не равен ни одному сомножителю в правой части (если не все сомножители сократятся).
Правая часть равенства делится на . Так как
— простое число, то хотя бы один сомножитель в правой части делился на
(по предыдущей теореме). В то же время все сомножители в правой части — это простые числа, не равные
. Следовательно, они не делятся на
. Противоречие.
Пусть
— канонические разложения чисел и
.
В каноническое разложение НОД входят те и только те простые числа, которые входят в оба разложения, причем из двух показателей выбирается меньший.
Простое число входит в каноническое разложение числа
с показателем, равным
где суммирование ведется до тех пор, пока целая часть не станет равной нулю.
Задачи.
1. Доказать, что делится на 30 для любого целого
.
2. Доказать, что для любого целого
.
3. Доказать, что сумма кубов трех последовательных чисел кратна 9.
4. Доказать, что для любого целого неотрицательного
5. Доказать, что для любого целого неотрицательного
6. Доказать, что при любом простом натуральном число
.
7. Доказать, что для любого натурального
8. Доказать, что для любого натурального нечетного
9. Какие остатки могут давать при делении на 9 кубы целых чисел?
10. Доказать, что для любого целого
11. Доказать, что для любого натурального
12. Доказать, что ни при каком целом
не делится на 169.
13. Доказать, что если , то целые числа
и
также делятся на 3.
14. Доказать, что для любого целого
и
не имеют общих делителей, отличных от 1.
15. Два двузначных числа, оканчивающихся одной и той же цифрой, таковы, что при делении на 9 частное каждого из них равно остатку другого. Найти все числа, удовлетворяющие этим условиям.
16. Доказать, что в любой из последовательностей
а)
б)
содержится бесконечно много составных чисел.
17. Разложить число на два натуральных множителя, каждый из которых не меньше 1000.
18. Доказать, что число составное.
19*. Натуральные числа такие, что
. Доказать, что число
— составное.
20. Доказать, что число (
нулей и
единиц) составное
.
21. Доказать, что число
(цифр там, где отмечено фигурной скобкой, по ) составное.
22. Представить в каноническом виде, найти НОД
а) и
;
б) и
.
23. Доказать, что для любого натурального
24. Доказать, что для любого натурального
25. Доказать, что нечетная степень , увеличенная на
, кратна
.
26. Найти все простые , для которых
и
также являются простыми.
27. Натуральные числа таковы, что
,
Доказать, что .
28. На какую наибольшую степень числа делится произведение всех четных четырехзначных чисел?
1 Непрерывные дроби | Математика, которая мне нравится:
[...] Линейное представление наибольшего общего делителя чисел и получается из [...]
22 Июнь 2011, 0:072 Легко догадаться, трудно доказать | Математика, которая мне нравится:
[...] выписывать простые числа по [...]
29 Февраль 2012, 0:123 Вася Пупкин:
Непривычно Ваш конспект читать после школьных учебников, где все подробно расписано)
[Ответить]
21 Июнь 2012, 17:144 Елизавета Александровна Калинина:
А это хорошо или плохо?
[Ответить]
21 Июнь 2012, 19:385 Вася Пупкин:
Я имел в виду, что в учебниках более подробно расписано, чем у Вас (на всякий случай).
Ваш конспект кажется строгим. Дольше приходиться вникать в материал. Но, думаю, это полезная закалка перед ВУЗ-ом )
[Ответить]
21 Июнь 2012, 23:106 Елизавета Александровна Калинина:
Да, думаю, Вы правы. Возможно, это мое и только мое восприятие ) . Но мне всегда нравились лекции, которые не до конца все разъясняли, и после которых оставалось, над чем подумать. Как бы лектор считает слушателей умными, не разжевывает все до конца
ИМХО
Ну и вопросы приветствуются всегда, конечно же ) .
[Ответить]
21 Июнь 2012, 23:427 Вася Пупкин:
Как первые примеры решать, методом мат. индукции? Или я что-то упустил…
[Ответить]
24 Июнь 2012, 15:548 Вася Пупкин:
В первом примере имеется ввиду, что n целое и |n| >= 2 ?
[Ответить]
24 Июнь 2012, 16:299 Елизавета Александровна Калинина:
Нет, в первом примере
— любое целое число. Задачи не требуется решать методом мат. индукции, хотя можно и индукцию использовать, если нужно.
[Ответить]
24 Июнь 2012, 22:5010 Лейб:
Мне кажется, что в некоторых задачах требуется кое-что откорректировать.
————————————————–
В задачах 4 и 5, вместо – ДЛЯ ЛЮБОГО ЦЕЛОГО, должно быть:
ДЛЯ ЛЮБОГО НЕОТРИЦАТЕЛЬНОГО ЦЕЛОГО.
————————————————–
В задаче 10, вместо – ДЛЯ ЛЮБОГО НАТУРАЛЬНОГО, лучше так (хотя и то, что есть – тоже, конечно, правильно): ДЛЯ ЛЮБОГО ЦЕЛОГО
[Ответить]
24 Июнь 2012, 23:5811 Елизавета Александровна Калинина:
Лейб Александрович, спасибо большое! Исправила.
[Ответить]
25 Июнь 2012, 0:0312 Вася Пупкин:
0 и 1 – это же целые числа? Тогда что там доказывать, если при n = 0 или n = 1 выражение не делится на 30. Или имеется в виду “доказать или опровергнуть?”
[Ответить]
25 Июнь 2012, 0:3713 Елизавета Александровна Калинина:
Не поняла. Смотрите, если
, то
делится на
. И для
тоже получаем, что
— это верно. Что Вас смущает?
[Ответить]
25 Июнь 2012, 11:1014 О числах простых и составных | Математика, которая мне нравится:
[...] [...]
25 Июнь 2012, 19:4615 Вася Пупкин:
Именно это меня и смущало, что ноль может на что-то делиться..
[Ответить]
28 Июнь 2012, 12:0816 Елизавета Александровна Калинина:
Так он на все делится, кроме нуля
[Ответить]
28 Июнь 2012, 22:1317 Корнеев В.Ф.:
14. Доказать, что для любого целого n
n^5+4n^3+3n{ \rm и } n^4+3n^2+1
не имеют общих делителей, отличных от 1.
——————————————-
Я не понял этой задачи. Скопировал, но копия не совпадает с оригиналом. Фигурные скобки отсутствуют!
[Ответить]
13 Июль 2012, 1:4318 Корнеев В.Ф.:
В “Мире чётных чисел” равенства ах+ву=1 некорректны ибо число 1 отсутствует. Вы даёте другое доказательство основной теоремы арифметики.
Кстати, когда будет обещанный комментарий. Я ведь ради него завёл “Математическую страничку”.
[Ответить]
13 Июль 2012, 1:5419 Елизавета Александровна Калинина:
на 17: Спасибо, исправила. Проблема в отображении русских букв в формулах, пока не решаемая никак…
на 18: Я писала комментарий Вам на сайте. Он не появился. Я Вам об этом тоже писала. Или мы о разном говорим?
Вот, подумалось. Если речь о ссылке, то она есть вот тут, и давно уже есть: http://hijos.ru/2012/02/19/eshhe-nemnogo-o-veroyatnostyax/.
Или я чего-то не понимаю?
[Ответить]
13 Июль 2012, 14:0720 Корнеев В.Ф.:
Я не знал. Но почему не появился? Попробуйте ещё раз.
[Ответить]
14 Июль 2012, 19:3021 Елизавета Александровна Калинина:
Хорошо, попробую. До этого пробовала раза два или три. Теперь уже не помню, где в комментариях Вам отвечала, что не появился мой комментарий у Вас, но писала точно. И Вам на сайт тоже писала, что нет комментария
Попробовала еще раз.
[Ответить]
14 Июль 2012, 21:3122 Корнеев В.Ф.:
А где писали? В http://hijos.ru/2012/02/19/eshhe-nemnogo-o-veroyatnostyax/ этого нет. Попробуйте ещё раз. Я немного изменил эту страничку. Вместо по частям, ибо блог не воспринимал большие файлы, я их за архивировал и поместил меньшим количеством.
[Ответить]
18 Июль 2012, 18:5423 Елизавета Александровна Калинина:
Так вот ведь опять попробовала, и опять ничего нет. Теперь вот тут написала: http://hijos.ru/2012/07/18/zadacha-ot-hewlett-packard/comment-page-1/#comment-2600
Нашла, где написала об этом раньше: http://hijos.ru/2012/04/18/gaspar-monzh-i-ego-teoremy/
[Ответить]
18 Июль 2012, 19:4024 Корнеев В.Ф.:
Почему же там же в “Дебюте” есть 1 прим.? А может это исключение из правил? Может надо самому попробовать. Потому и нет примечаний.
[Ответить]
18 Июль 2012, 21:4125 Корнеев В.Ф.:
А хоть рамка для комментов есть? А в ней печатается?
[Ответить]
18 Июль 2012, 21:5626 Елизавета Александровна Калинина:
Да, рамка есть, текст печатается и отсылается. А дальше ничего. Я сначала думала, что есть модерация комментариев, а вот и нет, просто куда-то все пропадает. Ну да, я думаю, что именно поэтому и не пишут Вам
[Ответить]
18 Июль 2012, 22:4327 Корнеев В.Ф.:
А откуда Вы посылали? Из своего п/я или ещё откуда-то? Ведь один коммент у меня таки есть.
[Ответить]
Елизавета Александровна Калинина Reply:
Июль 19th, 2012 at 21:44
Посылала так же, как это делаю здесь: писала текст в рамке для комментариев и нажимала Надiслати. Да, еще указывала логин и сайт.
[Ответить]
28 Корнеев В.Ф.:
Ой, наконец-то я сам зашёл в свои комменты. Выскочило “Страница временно недоступна”. Тогда я обратил внимание на “залогироваться”. Т. е. “создать свой профиль”. Т. е. выдать свои секретные данные. Стало понятно, почему так мало комментов. Залогировался со второстепенного п/я. И тогда всё получилось.
[Ответить]
23 Июль 2012, 2:0129 Корнеев В Ф:
Нужно менять хостинг блога. Я свой первый блог “Королевский гамбит” создал в “ЖЖ”. Там мои первые статьи по шахматам получились с кракозябрами. Тогда я перешёл на этот. Надо опять куда=то сваливать.
[Ответить]
23 Июль 2012, 2:1030 Елизавета Александровна Калинина:
А точно дело в хостинге? Может, просто CMS поменять или с той, что есть, разобраться? У меня wordpress, вполне устраивает. В принципе, можно поменять параметры, и тогда тоже будет нужна регистрация. Но мне это не нужно. Может, у Вас тоже такое есть?
[Ответить]
23 Июль 2012, 11:1031 Корнеев В Ф:
Это всё для меня тёмный лес.
[Ответить]
23 Июль 2012, 13:1632 Елизавета Александровна Калинина:
Боюсь, что просто смена хостинга в данном случае не поможет. Если хостинг бесплатный, надо тогда смотреть, что они предлагают. К сожалению, про Blox не поняла, не настолько хорошо знаю украинский. У меня хостинг платный, делаю, что кажется правильным.
Да, подумалось… Вы можете спросить кого-нибудь, у кого блог на Blox и комментарии правильные.
[Ответить]
23 Июль 2012, 13:3133 Премия института Клэя | Математика, которая мне нравится:
[...] чисел, например, 2, 3, 5, 7 и т.д. Такие числа называются простыми, и они играют важную роль как в чистой математике, так [...]
14 Ноябрь 2012, 0:0434 Юлия Иванова:
Добрый вечер, Елизавета Александровна!
Не могу понять, как в 16 номере сделать доказательство. Разъясните, пожалуйста!
[Ответить]
Елизавета Александровна Калинина Reply:
Декабрь 17th, 2014 at 13:00
Когда непонятно, что делать, нужно попробовать посмотреть, что же там получается.
а) Последовательность такая: 5, 13, 37, 65 и т.д. Видим, что есть числа, делящиеся на 5, они и будут составными. Осталось доказать, что таких чисел бесконечно много в этой последовательности. А это уже совсем легко.
б) Тоже посмотрите, какая последовательность получается.
[Ответить]
35 Михаил:
Супер! Единственная статья в рунете, спустя часа три поисков, нашёл, понял про линейное представление НОД. Спасибо.
[Ответить]
26 Август 2017, 12:00