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

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

d=am+bn, где m,n — целые числа

Доказательство. Пусть A — множество всех чисел, которые можно получить из a и b с помощью сложения и вычитания. Тогда, если xin A,yin A, то x-yin A,x+yin 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_1in ALongrightarrow r_2in ALongrightarrow r_3in ALongrightarrowdotsLongrightarrow r_nin 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} mvdots a,quad 1<a<m\ m=ab,1<b<m. end{array}]

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

Теорема. Если a,b – целые числа, p — простое число, abvdots p, то avdots p или bvdots 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, а 1notvdots p. Получили противоречие.

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

    [n=p_1p_2cdotldotscdot p_k, n=q_1q_2cdotldotscdot q_l,]

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

    [p_1le p_2leldotsle p_k, q_1le q_2leldotsle q_l.]

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

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

    [p_1p_2ldots p_k=q_1q_2ldots 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[{nover p}right]+left[{nover p^2}right]+left[{nover p^3}right]+left[{nover p^4}right]+ldots,]

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

Задачи.

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

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

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

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

    [7cdot5^{2n}+12cdot 6^nvdots19.]

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

    [6^{2n}+19^n-2^{n+1}vdots17.]

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

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

    [4^{n}+15n-1vdots9.]

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

    [n^3+3n^2-n-3vdots48.]

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

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

    [n^3+5nvdots3.]

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

    [5^{n+2}+26cdot5^{n}+8^{2n+1}vdots59.]

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

13. Доказать, что если m^2+n^2vdots3, то целые числа 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. Доказать, что число 1010ldots101 (k нулей и k+1 единиц) составное (kge2).

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

    [underbrace{11ldots1}_{n { rm цифр } }2underbrace{11ldots1}_{n { rm цифр }}]

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

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

а) 4828896 и 27147960;

б) 22754277 и 7484400.

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

    [10^{n}+45n-1vdots27.]

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+bvdots c,a+cvdots b,b+cvdots a.]

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

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

Ссылка на основную публикацию