Тема 5. Теорія подільності в кільці цілих чисел

5.2 Найбiльший спiльний дiльник I найменше спiльне кратне та способи знаходження їх. Взаємно простi числа

1. Знайти найбiльший спiльний дiльник i найменше спiльне кратне чисел: 1917 i 2000.

Р о з в'я з а н н я. 1 спосiб. Скористаємося алгоритмом Евклiда для знаходження найбiльшого спiльного дiльника.

1) Дiлимо 2000 на 1917, дiстаємо частку 1 i першу остачу 83;

2) дiлимо 1917 на 83, дiстаємо частку 23 i другу остачу 8;

3) дiлимо 83 на 8, дiстаємо частку 10 i третю остачу 3;

4. дiлимо 8 на 3, дiстаємо частку 2 i четверту остачу 2;

5. ділимо 3 на 2, дістаємо частку 1 і пяту остачу 1

6. дiлимо 2 на 1, дiстаємо частку 2 i шосту остачу 0.

Наведені обчислення можно записати також так:

													2000				1917
													1917				1
										1917					83
										1909					23
							83					8
							80					10
					8				3
					6				2
		3				2
		2				1
	2			1
	2			2
0

Остання вiдмiнна вiд нуля остача 5. Отже, (2000, 1917) = 5. Наведенi обчислення записують так:

Отже, числа 2000 i 1917 взаємно простi. Найменше спiльне кратне цих чисел дорiвнює їньому добутку, тобто [2000, 1917]= 20001917 = 3834000.

2 спосiб. Знайдемо канонiчнi розклади чисел 1917 i 1985: 1917 = 3³71, 2000 = 2⁴5³.

Запишемо цi числа в узагальнених канонiчних формах:

1917 = 2⁰3³5⁰71¹, 2000 = 2⁴3⁰5³71⁰.

Тодi (1917, 2000) = 2⁰3⁰5⁰71⁰ = 1, а [1917,2000] =2⁴3³5³71¹ = 3834000.

Зауваження. Цей спосiб доцiльно застосовувати в тих задачах, де треба знайти НСД i НСК в канонiчнiй формi.

2. Знайти найбiльший спiльний дiльник чисел 1917 i 1985, а також цiлi числа х i у, за допомогою яких число d лiнiйно виражається через числа 1917 i 1985, тобто d = 1917х + 1985у.

Р о з в'я з а н н я. Скористяємося попереднiм прикладом. Маємо:

2000 = 11917 + 83,

1917 = 2383 + 8,

83 = 108 + 3,

8 = 23 + 2,

3 = 12 + 1,

2 = 21 + 0.

Починаючи з передостанньої рiвностi, знаходимо остачi:

d = 1 = 3  12, (1)

2 = 8  23, (2)

3 = 83  108, (3)

8 = 1917  2383. (4)

83 = 2000  11917 (5)

Замiнюватимемо послiдовно остачi в цих рiвностях, поки не залишаться числа 1917 i 2000. Остачу у виразi (1) замiнюємо виразом (2) i зводимо подiбнi члени (3 i 8):

1 = 3  12 = 3  1(8  23) = 33  8.

У цiй рiвностi замiсть множника 3 пiдставляємо вираз (3) i знову зводимо подiбнi члени (83 i 8):

1 = 33  8 = 3(83  108) 8 = 383  318.

У знайденому виразi замiсть множника 8 пiдставляємо вираз (4) i знову зводимо подiбнi члени (1917 i 83):

1 = 383  318 = 383  31(1917  2383) = (3123 + 3)83  311917 = 71683   311917.

У знайденому виразi замiсть множника 83 пiдставляємо вираз (5) i знову зводимо подiбнi члени (1917 i 2000):

1 = 71683  311917 = 716(2000  11917)  311917 = 7162000  (716 +

+ 31)1917 = 7162000  7471917.

Отже, 1 =  7471917 + 7162000, звідси х =  747, у = 716.

Зауваження

1. Може трапитись, що у виразах для остач (особливо на промiжних етапах, в процесi знаходження лiнiйного виразу для НСД) деякi неповнi часткi збiгаються з якоюсь остачею. Тодi слiд пильно стежити, щоб замiсть таких часток не було підставлено вираз для остачi.

2. Часто лiнiйне зображення НСД чисел a i b є громоздким i тому, щоб не робити повну перевiрку, можна обмежитися тим, що лiва i права частини рiвностi aх + by = d повиннi мати однаковi останнi цифри. Так, у розглянутому прикладi права частина виразу 1 = 7471917 + 7162000 закiнчується цифрою 1, а лiва частина є 5.

3. Довести, що (a, b) = (5a + 3b, 13a + 8b) для довiльних цiлих чисел a i b.

Д о в е д е н н я. Введемо позначення (a, b) = d₁, (5a + 3b, 13a + 8b) = d₂. Доведемо, що d₁ = d_2.Оскiльки d₁ i d₂  натуральнi числа, то досить показати, що d₁\ d₂ i d₂ \ d_5. 3 означення d₁ маємо: d₁ \ a i d₁ \ b. Тодi d₁ \ 5a + 3b i d₁ \ 13a + 8b. Згiдно з означенням числа d₂, виходить d₁ \ d_2. Покажемо, що d₂ \ d_5. Виразимо числа 5a + 3b i 13a + 8b через d₂. Дiстанемо 5a + 3b = d₂х, i 13a + 8b = d₂у, де х i у  деякi цiлi числа. Домноживши першу рiвнiсть на 8, а другу на 3 i вiднявши вiд першої рiвностi другу, знайдемо a = d₂(8х  3у). Аналогiчно дiстаємо b = d₂(5у  13х). Отже, d₂ \ a i d₂ \ b. 3 означення числа d₁, випливає, що d₂ \ d₁ що й треба було довести.

Зауваження. З доведення цього твердження випливає що, (a, b) = (m₁a + + m₂b, n₁a + n₂b), якщо |m₁n₂  m₂n₁| = 1, де m₁, n₁, m₂, n₂  цiлi числа.

4. Знайти натуральнi числа m i n, якщо їхня сума дорiвнює 168, а найбiльший спiльний дiльник 24.

Р о з в 'я з а н н я. Використуємо факт: якщо (a, b) = d i a = da₁, b = db₁, то . У цьому разi (m, n) = 24. Тодi m = 24m₁, n = 24n₁, де (m₁, n₁) = 5. Оскiльки , то 24m₁ + 14n₁ = 168, тобто m₁ + n₁ = 7. Оскiльки натуральнi числа m₁ i n₁ взаємно простi, то розглядаючи всi можливi випадки, дiстаємо, що m₁ i n₁ набувають таких значень :1 i 6, 2 i 5, 3 i 4, i навпаки. Отже, числа m i n дорiвнюють 24 i 144, 48 i 120, 72 i 96, i навпаки.

5. Довести, що для довiльних натуральних a, b, c

[a, b, c] = ;

Д о в е д н н я. У відповідності з означенням НСК . Доведемо тепер, що . Нехай . Це означає: , , і при цьому . Користуючись ціми означеннями, можна одержати . Тоді з випливає, що виконується принаймні одне з співвідношень , , . Нехай це буде останнє, тобто . Тоді 1, оскільки при виконується також і умова .