«Применение теории чисел к решению математических задач»

В каждой главе кратко излагается теоретический материал, необходимый для понимания задач. Также приводится ряд задач с подробным решением.

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

Например, числа 12 и 35 взаимно просты, так как натуральными делителями числа 12 являются числа 1,2,3,4,6, а натуральными делителями числа 35 являются числа 1,5,7.

Перечислим свойства делимости суммы (разности) и произведения чисел, считая, что a ∈ Z ,b ∈ Z ,m ∈ N .

1. Если a и b делятся на m, то числа a+b и a-b также делятся на m.

2. Если a и b делятся на m, то при любых целых числах k и l число ak+ bl также делится на m.

3. Если a делится на m , а b не делится на m , то числа a+b и a-b также не делятся на m.

4. Если a делится на m, а m делится на k ∈ N , то число a также делится на k.

5. Если a делится на m, а b не делится на m , то число ab делится на m.

6. Если a делится на каждое из чисел m и k, причем (m,k )= 1, то a делится на произведение mk.

7. Если a делится на m, то ak делится на mk при любом k ∈ N.

8. Если ab делится на m и b взаимно просто с m, то a делится на m.

Ограничимся доказательством свойства 1.

Доказательство. Если целые числа a и b делятся на m, то существуют числа p ∈ Z и q ∈ Z такие, что a = mp,b =qm .

Отсюда следует, что

a + b = mp + mq = ( p + q)m ,

a - b= mp- mq= ( p- q)m .

Так как числа p+ q и p- q – целые, то числа a+ b и a- b делятся на m. Свойство доказано.

Пример 1. Натуральное число 3n + 2 и 8n + 3 делятся на натуральное число p ≠ 1. Найти p.

Решение. Так как числа 3n + 2 и 8n + 3 делятся p, то и число

8 ∙ (3n + 2) - 3(8n + 3) = 7

должно делиться на p. Но единственное натуральное число p ≠ 1, на которое делится 7, равно 7. Значит p = 7. Например, при n = 4 получаем числа 14 и 35, которые делятся на 7.

Ответ: p = 7.

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

Натуральное число p называется простым, если p> 1 и p не имеет положительных делителей, отличных от 1 и p.

Из определений легко следует, что если p и p_1 – простые числа и p делит p_1, то p= p_1. Кроме того, для любого натурального числа его наименьший отличный от единицы положительный делитель является простым числом.

Натуральное число n> 1 называется составным, если n имеет, по крайней мере, один положительный делитель, отличный от 1 и n.

Число 1 не считается ни простым, ни составным.

Пример 2. Доказать, что число a= 4 ∙〖16〗^(12 )- 2^40 делится на 33.

Решение. Так как 4 ∙〖16〗^(12 )= 2^4∙ 4^48 = 2^50,

то

a = 2^50- 2^40 = 2^40 (2^10 -1) =

= 2^40 (2^5 -1)(2^5 +1) = 2^40 ∙ 32 ∙ 33,

откуда следует, что a делится на 33.

Пример 3. Доказать, что число a = 8n^2 + 10n + 3 является составным при любом натуральном n.

Решение. Число a является составным при любом натуральном n, поскольку a = 8n^2 + 10n + 3 = (2n + 1)(4n + 3) , где числа 2n +1 и 4n + 3 натуральные, большие единицы.

Пример 4. Произведение нескольких различных простых чисел делится на каждое из этих чисел, уменьшенное на 1. Чему может быть равно это произведение?

Решение. Пусть искомое число n= p_1 ∙ p_2∙…∙p_k ,где p_1 ,p_2,…,p_k- простые числа и p_1< p_2<⋯< p_k. Так как n делится на каждое из чисел p_1-1 ,p_2-1,…,p_k-1, а они все, кроме возможно числа p_1-1, - четные. Это значит, что среди сомножителей p_1 ,p_2,…,p_k присутствует число 2, т.е.

p_1= 2.

Тогда n = 2 ∙ p_2,…,p_k.

Рассмотрим число p_k-1= 2q_k .

По условию число 2q_k делит n = 2 ∙ p_2,…,p_k. Это значит, что q_kявляется делителем числа p_2∙…∙p_(k-1). Это возможно, если q_k есть некоторое число или произведение некоторого набора чисел из набора

p_2,…,p_(k-1.)

Учитывая это условие и то, что число n_1 = 2 ∙ p_2,…,p_(k-1) обладает тем же свойством, что и число n, получаем способ получения искомых произведений: на каждом этапе следующий множитель〖 p〗_(k )оп-ределяется набором множителей

2 ,p_2,…,p_(k-1.)

Поэтому будем строить искомые произведения начиная с двух сомножителей.

Пусть k = 2 . Тогда n = 2 ∙p_2 Учитывая, что p_2-1 = 2q_2 и 2q_2 делит число 2, получаем q_2=1. Тогда p_2 = 3 и n = 2 ∙3 = 6.

Пусть k = 3 . Тогда n = 2∙3∙p_3. Учитывая, что p_3-1 = 2q_3 и 2q_3 делит число 2∙3, получаем q_3 = 3.

Тогда p_3 = 7 и n = 2 ∙ 3 ∙ 7 = 42 .

Пусть k = 4 . Тогда n = 2∙3∙〖7∙p〗_4. Учитывая, что p_4-1 = 2q_4 и 2q_4 делит число 2∙3∙7, получаем возможные значения q_4 = 3 или q_4 = 7, или q_4 = 3 ∙ 7 = 21 . Тогда p_4= 7 (уже есть такой множитель) или p_4 = 15 (не простое число), или p_4=43.

Тогда n=2 ∙ 3 ∙ 7 ∙ 43 =1806.

Пусть k=5 . Тогда n=2∙3∙〖7∙43∙p〗_4. Учитывая, что p_5-1 =2q_5 и 2q_5 делит число = 2∙3∙7 ∙ 43, получаем возможные значения q_5 и p_5:

q_5 = 3,p_5 = 7 (такой множитель есть);

q_5 = 7,p_5 = 15 (не простое число);

q_5= 3 ∙ 7 ,p_5= 43 (такой множитель есть);

q_5 = 43 ,p_5 = 87 (не простое число, делится на 3);

q_5 = 3 ∙ 43,p_5 = 257 (не простое число, делится на 7);

q_5 = 7 ∙ 43,p_5 = 603 (не простое число, делится на 3);

q_5=3∙7∙43,p_5 =1807 (не простое число, делится на 13).

Следовательно, искомого произведения из пяти сомножителей не существует, а значит не существует подобных произведений и с большим числом сомножителей.

Ответ: 6,42,1806.

Теорема 1 (Евклида). Множество положительных простых чисел бесконечно.

Доказательство. Предположим, что множество положительных простых чисел конечно и состоит из чисел p_1 ,p_2,…,p_k.

Рассмотрим число p= p_1∙ p_1 ∙ .∙ p_1+1 .

Тогда либо натуральное число p, большее единицы, само является простым, либо оно разложимо в произведение положительных простых чисел и поэтому обладает хотя бы одним простым делителем. По предположению p не может быть простым, так оно не совпадает ни с одним из чисел p_1 ,p_2,…,p_k. Если же p разложи мо, то его делитель должен быть отличен от чисел p_1 ,p_2,…,p_k. так как в против ном случае этот делитель делит числа p_1∙ p_1 ∙ .∙ p_1 и p, а значит делит и разность 〖p-p〗_1∙ p_1 ∙ .∙ p_1= 1, а это невозможно.

Следовательно, простых чисел бесконечно.

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

Теорема 2. Для любого целого числа k ≥ 1 в натуральном ряду можно найти k составных чисел, непосредственно следующих друг за другом.

Доказательство. Возьмем число n = (k +1)! и рассмотрим k следующих друг за другом чисел

n_1 = n + 2,n_2 =n + 3,.,n_k= n + (k +1) .

Каждое число в этом списке является составным, так как n_1 делится на 2, n_2- на 3, n_3- на 4, . , n_k- на k +1. Теорема доказана.

Теорема 3. Если произведение нескольких натуральных чисел делится на простое число, то на него делится хотя бы один из сомножителей.

Доказательство. Возьмем канонические разложения входящих в произведение натуральных чисел. Так как произведение этих чисел делится на простое число, то это простое число должно присутствовать хотя бы в одном каноническом разложении множителей. Следовательно, на это число делятся все множители, в каноническом разложении которых присутствует это число. Теорема доказана.

1.2. Каноническое разложение натурального числа

Представление натурального числа n в виде произведения двух натуральных чисел ab называется разложением на множители. Представление числа в виде произведения простых чисел называется разложением на простые множители. Считается, что если n - простое число, то оно имеет разложение на простые множители, состоящее из одного числа n.

Два разложения на множители называются одинаковыми, если они отличаются только порядком множителей. Например, разложения

42 = 2 ∙ 3 ∙ 7 и 42 = 7 ∙2∙ 3

считаются одинаковыми.

Теорема 4 (основная теорема арифметики). Для каждого натурального числа n > 1 существует единственное разложение на простые множители.

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

Каноническим разложением целого числа n > 1 называется представление n в виде

n =P_1^(K_1 )∙P_2^(K_2 )∙…∙ P_S^(K_S ), (1)

где p_1,p_2,.,p_s - попарно различные простые числа, а k_1,k_2,.,k_s - натуральные числа. Для отрицательных целых чисел n < -1 каноническим разложением считается представление в виде n =- P_1^(K_1 )∙P_2^(K_2 )∙…∙ P_S^(K_S ) .

Пусть число p - наименьший среди простых делителей p_1,p_2,.,p_s. Тогда

n =P_1^(K_1 )∙P_2^(K_2 )∙…∙ P_S^(K_S )≥P^2.

Отсюда, p ≤√n . Следовательно, если n - составное число, то оно имеет простой делитель p такой, что p ≤√n. Если число n не имеет простых делителей, не превосходящих √n , то n - простое число.

Пример 5. Сколько существует способов разложения числа

n = P_1^(K_1 )∙P_2^(K_2 )∙…∙ P_S^(K_S )

в произведение двух взаимно простых множителей?

Решение. Пусть имеется разложение n = n_1∙n_2, где числа n_1 и n_2- взаимно просты, т.е. (n_1,n_2) = 1. Это будет возможно в случае, когда эти числа не содержат ни одного общего множителя p_i (1 ≤ i ≤s ). Поэтому искомое количество способов разложения будет равно количеству способов разбиения множества чисел {p_1,p_2,.,p_s} на две непересекающиеся группы.

Рассмотрим строчки ⏟(( , ,.,))┬(S позиций) в которых в i -й позиции стоит 1, если p_i входит в множитель n_1, и 0, если p_(i )входит в множитель n_2. Для заполнения каждой позиции имеется 2 способа. Всего s позиций. Две позиции можно заполнить 2∙ 2 = 2^2 способами, три - 2∙ 2∙ 2 = 2^3 и т.д. Соответственно, всего имеется 2^s различных строчек. Исключая строчки из одних 1 (в этом случае n_1= n ) и одних 0 (в этом случае n_2 = n), получаем искомое число, равное 2^s - 2 .

Ответ: 2^s - 2.

1.3. НОД и НОК

Наибольшим общим делителем (НОД) натуральных чисел a_1,a_2,.,a_n называется наибольшее натуральное число, на которое делятся данные числа. Наименьшим общим кратным (НОК) - наименьшее натуральное число, делящееся на каждое из этих чисел. Наибольший общий делитель чисел a_1,a_2,.,a_n обозначают (a_1,a_2,.,a_n ), а наименьшее общее кратное - [a_1,a_2,.,a_n ]. В частности, (a,b)- НОД чисел a и b, а [a,b] - НОК этих чисел.

Отметим, что

НОД (a; b) = НОД (a; a + b);

НОД (a; b) = НОД (a; a - b).

Числа a_1,a_2,.,a_n называются взаимно простыми, если (a_1,a_2,.,a_n )= 1 и попарно взаимно простыми, если любые два из них взаимно просты, т.е. (a_i,a_j ) = 1 при i ≠ j. Попарно взаимно простые числа являются взаимно простыми (в совокупности). Обратное утверждение неверно, как показывает следующий пример: числа

n_1 = 3 ,n_2= 2 ∙ 3 ,n_3= 2 ∙ 5 и n_4= 3 ∙ 5

не являются взаимно простыми, а (n_1,n_2,n_3,n_4) = 1.

Отметим, что

Если целые числа a и b взаимно просты, то их сумма a+ b и произведение ab также являются взаимно простыми числами.

Если целые числа a и b являются взаимно простыми, то

НОД (a + b; a- b) = 1

или

НОД (a + b; a- b) = 2.

Доказательство. Положим НОД (a + b; a- b) = d .

Тогда (a+ b) | d, (a - b) | d. Следовательно, сумма и разность чисел a+ b и а - b, равные соответственно 2a и 2b делятся на d. Но числа a и b по условию взаимно просты, поэтому 2 делится на d∶ 2 | d. Отсюда d = 1 или d = 2. Оба эти случая возможны. Действительно, d = 1, если числа a и b разной четности, и d = 2, если они нечетны.

Любые два последовательных натуральных числа взаимно просты.

Наибольший общий делитель любых двух последовательных четных натуральных чисел равен 2.

Любые два последовательных нечетных натуральных числа взаимно просты.

Если целые числа a и b являются взаимно простыми, то

НОД (a + b; a^2 - ab + b^2)

равен 1 или 3.

Если натуральные числа m и n взаимно просты, то

НОД (m + n; m^2 + n^2)

равен 1 или 2.

Доказательство. Пусть d - общий делитель чисел m + n и m^2 + n^2. Тогда на d делится также число (m + 〖n)〗^2, а значит, и число

(m + 〖n)〗^2-m^2 + =2mn.

Итак, d является общим делителем чисел m + n и 2mn. Но m + n и m не могут иметь общих делителей, отличных от 1 (так как m и n взаимно просты), и тоже справедливо для чисел m + n и n. Следовательно, d является делителем числа 2, т.е. d = 1 или d = 2.

Теорема 5. Пусть n - натуральное число и n =P_1^(K_1 )∙P_2^(K_2 )∙…∙ P_S^(K_S )- его каноническое разложение на простые множители. Тогда каждый натуральный делитель d числа n может быть записан в виде

d = P_1^(M_1 )∙P_2^(M_2 )∙…∙ P_S^(M_S ),

где M_I - целые числа, удовлетворяющие условиям

0≤ M_1 ≤ K_1,.,0 ≤ M_S≤ K_S.

Доказательство. Пусть d - какой- либо делитель натурального числа n. Так как каждый простой делитель числа d является делителем числа n, тогда в разложении d на простые множители могут встречаться только числа из множества {p_1,p_2,.,p_s }. Поэтому число d представимо в виде

d = P_1^(M_1 )∙P_2^(M_2 )∙…∙ P_S^(M_S ).

Теорема доказана.

Теорема 6. Пусть даны два натуральных числа a и b, а p_1,p_2,…,p_s-

простые числа, входящие в канонические разложения a и b. Представим числа a и b в виде

a= P_1^(K_1 )∙P_2^(K_2 )∙…∙ P_S^(K_S ) и

b= P_1^(M_1 )∙P_2^(M_2 )∙…∙ P_S^(M_S )

где M_I≥ 0,K_I ≥0 -целые числа. Тогда

(a b)= p_1^min⁡(k_1∙m_1 ) ∙p_2^min⁡(k_2∙m_2 ) ∙〖… ∙p〗_s^min⁡(k_s∙m_s ) ,

[a b]= p_1^max⁡(k_1∙m_1 ) ∙p_2^max⁡(k_2∙m_2 ) ∙〖… ∙p〗_s^max⁡(k_s∙m_s ) .

Например, пусть a = 2^3∙〖3 〗^2∙ 7,b = 2^4∙ 3 ∙ 5^2∙11. Запишем их в виде a = 2^3∙〖3 〗^2∙5^0 ∙7^1∙〖11〗^0,b = 2^4∙ 3^1 ∙ 5^2∙7^0∙〖11〗^1. Тогда

(a,b) = 2^3∙〖 3〗^1 = 24,

[a,b] = 2^4∙ 3^2∙ 5^2 ∙7^1 ∙〖11〗^1 = 277 200.

Замечание. Справедливо равенство (a,b) ∙ [a,b] = a ∙b.

Пример 6. Найти (5160,16920) и [5160,16920].

Решение. Напишем канонические разложения чисел 5160 и 16920:

5160 = ⏟(2∙5)┬10∙ ⏟(2∙2∙⏞(3∙43)┴129 )┬564 =2^3 ∙ 3∙ 5∙ 43,

16920 = ⏟(2∙5)┬10∙ ⏟(2∙2∙⏞(3∙47)┴423 )┬1692 = 2^3 ∙3^2 ∙ 5∙ 47.

Тогда

(5160,16920) = 2^3 ∙ 3^1∙ 5^1∙ 〖43〗^0∙ 〖47〗^0 = 120,

[5160,16920] = 2^3 ∙ 3^2∙ 5^1∙ 〖43〗^1∙ 〖47〗^1= 727560.

Ответ: 120,727560.

Существует еще один способ нахождения НОД двух чисел, называемый алгоритмом Евклида, использующий деление чисел с остатком.

Пример 7. Найти все пары натуральных чисел, наименьшее общее кратное которых равно 78, а наибольший общий делитель равен 13.

Решение. Пусть a и b - искомые числа, По условию (a,b) = 13. Значит

a = 13 ∙ a_1 и b = 13 ∙ b_1. Так как [a,b] = 78, а 78 = 6 ∙ 13 , то, используя равенство

(a,b) ∙ [a,b] = a ∙ b,

получаем a∙ b = 〖13〗^2∙a_1 ∙ b_1=〖13〗^2 ∙ 6. Отсюда получаем a_1 ∙ b_1 = 6 . Следовательно, возможны случаи a_1= 1,b = 6 и a_1= 2,b_1= 3 (или a_1 = 6,b_1 = 1 и a_1 = 3,b_1 = 2 ). Тогда получаем две пары чисел, удовлетворяющие условию задачи (13,78) и (26,39).

Ответ: (13,78),(26,39).