Линейное представление НОД. Простые и составные числа

8. Линейное представление НОД. Простые и составные числа

Теорема. Пусть $a,b$ – целые числа, $d=$ НОД $(a,b)$ . Число $d$ можно представить в виде

Доказательство. Пусть $A$ — множество всех чисел, которые можно получить из $a$ и $b$ с помощью сложения и вычитания. Тогда, если $x\in A,y\in A$ , то $x-y\in A,x+y\in A$ . Так как в алгоритме Евклида

$r_1=a-bq_1,r_2=b-r_1q_2,r_3=r_1-r_2q_3,\dots,r_n=r_{n-2}-r_{n-1}q_n,$

$r_1\in A\Longrightarrow r_2\in A\Longrightarrow r_3\in A\Longrightarrow\dots\Longrightarrow r_n\in A.$

Но $r_n=d$ .

Следствия.

1. НОД двух чисел делится на любой общий делитель этих чисел.

2. Уравнение $ax+by=c$ , где $a,b,c$ — целые коэффициенты, $x,y$ — целочисленные неизвестные, разрешимо в том и только в том случае, если $c$ делится на НОД $(a,b)$ .

Простые и составные числа

Определение. Целое число $a$ называется составным, если оно делится на какое-нибудь целое число, отличное от $a$ и $-a$ , $1$ и $-1$ .

Целое число называется простым, если оно не является составным и не равно $\pm1$ .

Замечание. Здесь необходимо отметить, что общепринятым является другое определение простых и составных чисел. Обычно простыми числами называются только натуральные числа. По этому поводу читайте здесь. В этом есть свои удобства и неудобства. В любом случае, когда возникнут сомнения, какие числа имеются в виду, всегда можно задать вопрос.

Теорема. Всякое составное натуральное число можно представить в виде произведения простых натуральных чисел.

Доказательство. Пусть есть такие составные натуральные числа, которые нельзя представить в виде произведения простых. Выберем из этих чисел самое маленькое и обозначим его через $m$ . Так как $m$ — составное число, то у него есть делитель $a$ , который больше 1 и меньше $m$ .

$\begin{array}{l} m\vdots a,\quad 1<a<m\\ m=ab,1<b<m. \end{array}$

Числа $a,b$ натуральные. Каждое из чисел $a,b$ либо является простым, либо это составное, меньшее $m$ , которое поэтому раскладывается на простые множители. Но тогда и $m$ раскладывается на простые множители. Получили противоречие.

Теорема. Если $a,b$ – целые числа, $p$ — простое число, $ab\vdots p$ , то $a\vdots p$ или $b\vdots p$ .

Доказательство. Пусть ни $a$ , ни $b$ не делятся на $p$ . Тогда
НОД $(a,p)=1$ ,НОД $(b,p)=1$ . Следовательно, можно подобрать такие целые числа $x$ и $y$ и такие целые числа $z$ и $t$ , что

$ax+py=1,bz+pt=1.$

Перемножим эти равенства почленно:

$abxz+apxt+bpyz+p^2yt=1.$

Каждое слагаемое в левой части равенства делится на $p$ , а $1\not\vdots p$ . Получили противоречие.

Теорема. Пусть $n$ — составное натуральное число и

$n=p_1p_2\cdot\ldots\cdot p_k,\ n=q_1q_2\cdot\ldots\cdot q_l,$

где $p_1,\dots,p_k,q_1,\ldots,q_l$ — простые натуральные числа. Пусть

$p_1\le p_2\le\ldots\le p_k,\ q_1\le q_2\le\ldots\le q_l.$

Тогда $k=l$ и $p_1=q_1,p_2=q_2,\ldots,p_k=q_k$ .

Доказательство.

$p_1p_2\ldots p_k=q_1q_2\ldots q_l$

Если в левой и правой части есть равные сомножители, сократим на них и получим равенство такого же вида, в котором ни один сомножитель в левой части не равен ни одному сомножителю в правой части (если не все сомножители сократятся).

Правая часть равенства делится на $p_1$ . Так как $p_1$ — простое число, то хотя бы один сомножитель в правой части делился на $p_1$ (по предыдущей теореме). В то же время все сомножители в правой части — это простые числа, не равные $p_1$ . Следовательно, они не делятся на $p_1$ . Противоречие.

Пусть

$a=p_1^{k_1}p_2^{k_2}\ldots p_s^{k_s},\ b=q_1^{l_1}q_2^{l_2}\ldots p_t^{l_t}$

— канонические разложения чисел $a$ и $b$ .

В каноническое разложение НОД $(a,b)$ входят те и только те простые числа, которые входят в оба разложения, причем из двух показателей выбирается меньший.

Простое число $p$ входит в каноническое разложение числа $n!$ с показателем, равным

$\left[{n\over p}\right]+\left[{n\over p^2}\right]+\left[{n\over p^3}\right]+\left[{n\over p^4}\right]+\ldots,$

где суммирование ведется до тех пор, пока целая часть не станет равной нулю.

Задачи.

1. Доказать, что $n^5-n$ делится на 30 для любого целого $n$ .

2. Доказать, что $n^3+3n^2+5n+3\vdots3$ для любого целого $n$ .

3. Доказать, что сумма кубов трех последовательных чисел кратна 9.

4. Доказать, что для любого целого неотрицательного $n$

$7\cdot5^{2n}+12\cdot 6^n\vdots19.$

5. Доказать, что для любого целого неотрицательного $n$

$6^{2n}+19^n-2^{n+1}\vdots17.$

6. Доказать, что при любом простом натуральном $p,p>3$ число $>p^2-1\vdots24$ .

7. Доказать, что для любого натурального $n$

$4^{n}+15n-1\vdots9.$

8. Доказать, что для любого натурального нечетного $n$

$n^3+3n^2-n-3\vdots48.$

9. Какие остатки могут давать при делении на 9 кубы целых чисел?

10. Доказать, что для любого целого $n$

$n^3+5n\vdots3.$

11. Доказать, что для любого натурального $n$

$5^{n+2}+26\cdot5^{n}+8^{2n+1}\vdots59.$

12. Доказать, что $x^2+5x+16$ ни при каком целом $x$ не делится на 169.

13. Доказать, что если $m^2+n^2\vdots3$ , то целые числа $m$ и $n$ также делятся на 3.

14. Доказать, что для любого целого $n$

$n^5+4n^3+3n$ и $n^4+3n^2+1$

не имеют общих делителей, отличных от 1.

15. Два двузначных числа, оканчивающихся одной и той же цифрой, таковы, что при делении на 9 частное каждого из них равно остатку другого. Найти все числа, удовлетворяющие этим условиям.

16. Доказать, что в любой из последовательностей

а) $2^2+1,4^2+1,6^2+1,8^2+1,\ldots$

б) $4^2+1,14^2+1,24^2+1,34^2+1,\ldots$

содержится бесконечно много составных чисел.

17. Разложить число $2^{1982}+1$ на два натуральных множителя, каждый из которых не меньше 1000.

18. Доказать, что число $4^{545}+545^4$ составное.

19*. Натуральные числа $a,b,c,d$ такие, что $ab=cd$ . Доказать, что число

$a^4+b^4+c^4+d^4$

— составное.

20. Доказать, что число $1010\ldots101$ ( $k$ нулей и $k+1$ единиц) составное $(k\ge2)$ .

21. Доказать, что число

$\underbrace{11\ldots1}_{n { \rm цифр } }2\underbrace{11\ldots1}_{n { \rm цифр }}$

(цифр там, где отмечено фигурной скобкой, по $n$ ) составное.

22. Представить в каноническом виде, найти НОД

а) $4828896$ и $27147960$ ;

б) $22754277$ и $7484400$ .

23. Доказать, что для любого натурального $n$

$10^{n}+45n-1\vdots27.$

24. Доказать, что для любого натурального $n$

$3^{3n+2}+7^{n}\vdots10.$

25. Доказать, что нечетная степень $48$ , увеличенная на $1$ , кратна $7$ .

26. Найти все простые $p$ , для которых $p+14$ и $p+70$ также являются простыми.

27. Натуральные числа $a,b,c$ таковы, что $a<b<c$ ,

$a+b\vdots c,a+c\vdots b,b+c\vdots a.$

Доказать, что $b=2a,c=3a$ .

28. На какую наибольшую степень числа $3$ делится произведение всех четных четырехзначных чисел?

Комментарии (RSS) | Трекбек

Комментариев: 37

1 Непрерывные дроби | Математика, которая мне нравится:

[...] Линейное представление наибольшего общего делителя чисел и получается из [...]
22 Июнь 2011, 0:07
2 Легко догадаться, трудно доказать | Математика, которая мне нравится:

[...] выписывать простые числа по [...]
29 Февраль 2012, 0:12
3 Вася Пупкин:

Непривычно Ваш конспект читать после школьных учебников, где все подробно расписано)

[Ответить]
21 Июнь 2012, 17:14
4 Елизавета Александровна Калинина:

А это хорошо или плохо?

[Ответить]
21 Июнь 2012, 19:38
5 Вася Пупкин:

Я имел в виду, что в учебниках более подробно расписано, чем у Вас (на всякий случай).

Ваш конспект кажется строгим. Дольше приходиться вникать в материал. Но, думаю, это полезная закалка перед ВУЗ-ом )

[Ответить]
21 Июнь 2012, 23:10
6 Елизавета Александровна Калинина:

Да, думаю, Вы правы. Возможно, это мое и только мое восприятие ) . Но мне всегда нравились лекции, которые не до конца все разъясняли, и после которых оставалось, над чем подумать. Как бы лектор считает слушателей умными, не разжевывает все до конца ИМХО Ну и вопросы приветствуются всегда, конечно же ) .

[Ответить]
21 Июнь 2012, 23:42
7 Вася Пупкин:

Как первые примеры решать, методом мат. индукции? Или я что-то упустил…

[Ответить]
24 Июнь 2012, 15:54
8 Вася Пупкин:

В первом примере имеется ввиду, что n целое и |n| >= 2 ?

[Ответить]
24 Июнь 2012, 16:29
9 Елизавета Александровна Калинина:

Нет, в первом примере $n$ — любое целое число. Задачи не требуется решать методом мат. индукции, хотя можно и индукцию использовать, если нужно.

[Ответить]
24 Июнь 2012, 22:50
10 Лейб:

Мне кажется, что в некоторых задачах требуется кое-что откорректировать.
————————————————–
В задачах 4 и 5, вместо – ДЛЯ ЛЮБОГО ЦЕЛОГО, должно быть:
ДЛЯ ЛЮБОГО НЕОТРИЦАТЕЛЬНОГО ЦЕЛОГО.
————————————————–
В задаче 10, вместо – ДЛЯ ЛЮБОГО НАТУРАЛЬНОГО, лучше так (хотя и то, что есть – тоже, конечно, правильно): ДЛЯ ЛЮБОГО ЦЕЛОГО

[Ответить]
24 Июнь 2012, 23:58
11 Елизавета Александровна Калинина:

Лейб Александрович, спасибо большое! Исправила.

[Ответить]
25 Июнь 2012, 0:03
12 Вася Пупкин:

0 и 1 – это же целые числа? Тогда что там доказывать, если при n = 0 или n = 1 выражение не делится на 30. Или имеется в виду “доказать или опровергнуть?”

[Ответить]
25 Июнь 2012, 0:37
13 Елизавета Александровна Калинина:

Не поняла. Смотрите, если $n=0$ , то $n^5-n=0^5-0=0$ делится на $30$ . И для $n=1$ тоже получаем, что $0\vdots30$ — это верно. Что Вас смущает?

[Ответить]
25 Июнь 2012, 11:10
14 О числах простых и составных | Математика, которая мне нравится:

[...] [...]
25 Июнь 2012, 19:46
15 Вася Пупкин:

Именно это меня и смущало, что ноль может на что-то делиться..

[Ответить]
28 Июнь 2012, 12:08
16 Елизавета Александровна Калинина:

Так он на все делится, кроме нуля

[Ответить]
28 Июнь 2012, 22:13
17 Корнеев В.Ф.:

14. Доказать, что для любого целого n

n^5+4n^3+3n{ \rm и } n^4+3n^2+1

не имеют общих делителей, отличных от 1.
——————————————-
Я не понял этой задачи. Скопировал, но копия не совпадает с оригиналом. Фигурные скобки отсутствуют!

[Ответить]
13 Июль 2012, 1:43
18 Корнеев В.Ф.:

В “Мире чётных чисел” равенства ах+ву=1 некорректны ибо число 1 отсутствует. Вы даёте другое доказательство основной теоремы арифметики.
Кстати, когда будет обещанный комментарий. Я ведь ради него завёл “Математическую страничку”.

[Ответить]
13 Июль 2012, 1:54
19 Елизавета Александровна Калинина:

на 17: Спасибо, исправила. Проблема в отображении русских букв в формулах, пока не решаемая никак…

на 18: Я писала комментарий Вам на сайте. Он не появился. Я Вам об этом тоже писала. Или мы о разном говорим?

Вот, подумалось. Если речь о ссылке, то она есть вот тут, и давно уже есть: http://hijos.ru/2012/02/19/eshhe-nemnogo-o-veroyatnostyax/.

Или я чего-то не понимаю?

[Ответить]
13 Июль 2012, 14:07
20 Корнеев В.Ф.:

Я не знал. Но почему не появился? Попробуйте ещё раз.

[Ответить]
14 Июль 2012, 19:30
21 Елизавета Александровна Калинина:

Хорошо, попробую. До этого пробовала раза два или три. Теперь уже не помню, где в комментариях Вам отвечала, что не появился мой комментарий у Вас, но писала точно. И Вам на сайт тоже писала, что нет комментария

Попробовала еще раз.

[Ответить]
14 Июль 2012, 21:31
22 Корнеев В.Ф.:

А где писали? В http://hijos.ru/2012/02/19/eshhe-nemnogo-o-veroyatnostyax/ этого нет. Попробуйте ещё раз. Я немного изменил эту страничку. Вместо по частям, ибо блог не воспринимал большие файлы, я их за архивировал и поместил меньшим количеством.

[Ответить]
18 Июль 2012, 18:54
23 Елизавета Александровна Калинина:

Так вот ведь опять попробовала, и опять ничего нет. Теперь вот тут написала: 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:40
24 Корнеев В.Ф.:

Почему же там же в “Дебюте” есть 1 прим.? А может это исключение из правил? Может надо самому попробовать. Потому и нет примечаний.

[Ответить]
18 Июль 2012, 21:41
25 Корнеев В.Ф.:

А хоть рамка для комментов есть? А в ней печатается?

[Ответить]
18 Июль 2012, 21:56
26 Елизавета Александровна Калинина:

Да, рамка есть, текст печатается и отсылается. А дальше ничего. Я сначала думала, что есть модерация комментариев, а вот и нет, просто куда-то все пропадает. Ну да, я думаю, что именно поэтому и не пишут Вам

[Ответить]
18 Июль 2012, 22:43
27 Корнеев В.Ф.:

А откуда Вы посылали? Из своего п/я или ещё откуда-то? Ведь один коммент у меня таки есть.

[Ответить]
Елизавета Александровна Калинина Reply:
Июль 19th, 2012 at 21:44
Посылала так же, как это делаю здесь: писала текст в рамке для комментариев и нажимала Надiслати. Да, еще указывала логин и сайт.

[Ответить]
19 Июль 2012, 16:05
28 Корнеев В.Ф.:

Ой, наконец-то я сам зашёл в свои комменты. Выскочило “Страница временно недоступна”. Тогда я обратил внимание на “залогироваться”. Т. е. “создать свой профиль”. Т. е. выдать свои секретные данные. Стало понятно, почему так мало комментов. Залогировался со второстепенного п/я. И тогда всё получилось.

[Ответить]
23 Июль 2012, 2:01
29 Корнеев В Ф:

Нужно менять хостинг блога. Я свой первый блог “Королевский гамбит” создал в “ЖЖ”. Там мои первые статьи по шахматам получились с кракозябрами. Тогда я перешёл на этот. Надо опять куда=то сваливать.

[Ответить]
23 Июль 2012, 2:10
30 Елизавета Александровна Калинина:

А точно дело в хостинге? Может, просто CMS поменять или с той, что есть, разобраться? У меня wordpress, вполне устраивает. В принципе, можно поменять параметры, и тогда тоже будет нужна регистрация. Но мне это не нужно. Может, у Вас тоже такое есть?

[Ответить]
23 Июль 2012, 11:10
31 Корнеев В Ф:

Это всё для меня тёмный лес.

[Ответить]
23 Июль 2012, 13:16
32 Елизавета Александровна Калинина:

Боюсь, что просто смена хостинга в данном случае не поможет. Если хостинг бесплатный, надо тогда смотреть, что они предлагают. К сожалению, про Blox не поняла, не настолько хорошо знаю украинский. У меня хостинг платный, делаю, что кажется правильным.

Да, подумалось… Вы можете спросить кого-нибудь, у кого блог на Blox и комментарии правильные.

[Ответить]
23 Июль 2012, 13:31
33 Премия института Клэя | Математика, которая мне нравится:

[...] чисел, например, 2, 3, 5, 7 и т.д. Такие числа называются простыми, и они играют важную роль как в чистой математике, так [...]
14 Ноябрь 2012, 0:04
34 Юлия Иванова:

Добрый вечер, Елизавета Александровна!
Не могу понять, как в 16 номере сделать доказательство. Разъясните, пожалуйста!

[Ответить]
Елизавета Александровна Калинина Reply:
Декабрь 17th, 2014 at 13:00
Когда непонятно, что делать, нужно попробовать посмотреть, что же там получается.

а) Последовательность такая: 5, 13, 37, 65 и т.д. Видим, что есть числа, делящиеся на 5, они и будут составными. Осталось доказать, что таких чисел бесконечно много в этой последовательности. А это уже совсем легко.

б) Тоже посмотрите, какая последовательность получается.

[Ответить]
12 Декабрь 2014, 22:10
35 Михаил:

Супер! Единственная статья в рунете, спустя часа три поисков, нашёл, понял про линейное представление НОД. Спасибо.

[Ответить]
26 Август 2017, 12:00

Математика, которая мне нравится

8. Линейное представление НОД. Простые и составные числа

Комментариев: 37

1 Непрерывные дроби | Математика, которая мне нравится:

2 Легко догадаться, трудно доказать | Математика, которая мне нравится:

3 Вася Пупкин:

4 Елизавета Александровна Калинина:

5 Вася Пупкин:

6 Елизавета Александровна Калинина:

7 Вася Пупкин:

8 Вася Пупкин:

9 Елизавета Александровна Калинина:

10 Лейб:

11 Елизавета Александровна Калинина:

12 Вася Пупкин:

13 Елизавета Александровна Калинина:

14 О числах простых и составных | Математика, которая мне нравится:

15 Вася Пупкин:

16 Елизавета Александровна Калинина:

17 Корнеев В.Ф.:

18 Корнеев В.Ф.:

19 Елизавета Александровна Калинина:

20 Корнеев В.Ф.:

21 Елизавета Александровна Калинина:

22 Корнеев В.Ф.:

23 Елизавета Александровна Калинина:

24 Корнеев В.Ф.:

25 Корнеев В.Ф.:

26 Елизавета Александровна Калинина:

27 Корнеев В.Ф.:

28 Корнеев В.Ф.:

29 Корнеев В Ф:

30 Елизавета Александровна Калинина:

31 Корнеев В Ф:

32 Елизавета Александровна Калинина:

33 Премия института Клэя | Математика, которая мне нравится:

34 Юлия Иванова:

35 Михаил:

Оставьте свой отзыв

Навигация по сайту

Разделы

Новые комментарии

Хороший книжный магазин

Подписка на обновления сайта

Твиттер