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

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

d=am+bn,\mbox{ \rm где }m,n — целые числа

Доказательство. Пусть 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<br /> 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}<br /> m\vdots a,\quad 1<a<m\\<br /> m=ab,1<b<m.<br /> \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},\<br /> b=q_1^{l_1}q_2^{l_2}\ldots p_t^{l_t}

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

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

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

\displaystyle\left[{n\over p}\right]+\left[{n\over p^2}\right]+\left[{n\over<br /> 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 цифр }<br /> }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)  |  Трекбек

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

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

    [...] Линейное представление наибольшего общего делителя чисел и получается из [...]

    22 Июнь 2011, 0:07

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

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

    [Ответить]

    21 Июнь 2012, 17:14

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

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

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

    [Ответить]

    21 Июнь 2012, 23:10

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

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

    [Ответить]

    21 Июнь 2012, 23:42

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

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

    [Ответить]

    24 Июнь 2012, 15:54

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

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

    [Ответить]

    24 Июнь 2012, 16:29

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

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

    [Ответить]

    24 Июнь 2012, 22:50

  10. 10 Лейб:

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

    [Ответить]

    24 Июнь 2012, 23:58

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

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

    [Ответить]

    25 Июнь 2012, 0:03

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

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

    [Ответить]

    25 Июнь 2012, 0:37

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

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

    [Ответить]

    25 Июнь 2012, 11:10

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

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

    [Ответить]

    28 Июнь 2012, 12:08

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

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

    [Ответить]

    28 Июнь 2012, 22:13

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

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

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

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

    [Ответить]

    13 Июль 2012, 1:43

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

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

    [Ответить]

    13 Июль 2012, 1:54

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

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

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

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

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

    [Ответить]

    13 Июль 2012, 14:07

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

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

    [Ответить]

    14 Июль 2012, 19:30

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

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

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

    [Ответить]

    14 Июль 2012, 21:31

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

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

    [Ответить]

    18 Июль 2012, 18:54

  23. 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. 24 Корнеев В.Ф.:

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

    [Ответить]

    18 Июль 2012, 21:41

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

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

    [Ответить]

    18 Июль 2012, 21:56

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

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

    [Ответить]

    18 Июль 2012, 22:43

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

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

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Июль 19th, 2012 at 21:44

    Посылала так же, как это делаю здесь: писала текст в рамке для комментариев и нажимала Надiслати. Да, еще указывала логин и сайт.

    [Ответить]

    19 Июль 2012, 16:05

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

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

    [Ответить]

    23 Июль 2012, 2:01

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

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

    [Ответить]

    23 Июль 2012, 2:10

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

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

    [Ответить]

    23 Июль 2012, 11:10

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

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

    [Ответить]

    23 Июль 2012, 13:16

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

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

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

    [Ответить]

    23 Июль 2012, 13:31

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

    [...] чисел, например, 2, 3, 5, 7 и т.д. Такие числа называются простыми, и они играют важную роль как в чистой математике, так [...]

    14 Ноябрь 2012, 0:04

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

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

    [Ответить]

    Елизавета Александровна Калинина Reply:
    Декабрь 17th, 2014 at 13:00

    Когда непонятно, что делать, нужно попробовать посмотреть, что же там получается.

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

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

    [Ответить]

    12 Декабрь 2014, 22:10

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

Добавить изображение