Метод разложения на множители.

Содержание.

Введение 3

Основная часть

Глава 1 Общие сведения о решении уравнений в целых числах.

1.1 Диофантовы уравнения. 4

1.2 Историческая справка. 5

Глава 2. Способы решения уравнений в целых числах.

2.1 Способ перебора вариантов. 6

2.2 Алгоритм Евклида. 7

2.3 Цепные дроби. 10

2.4 Метод разложения на множители. 11

2.5 Решение уравнений в целых числах как квадратных относительно какой-либо переменной. 15

2.6 Метод остатков. 16

2.7 Метод бесконечного спуска. 17

Глава 2. Известные диофантовы уравнения.

3.1 Теорема Ферма. 19

3.2 Пифагоровы тройки. 21

3.3 Вокруг теоремы Пифагора. 22

3.4 Другие известные диофантовы уравнения. 23

Заключение. 25

Приложение. 26

Библиография. 28

Глава 1. Общие сведения о решении уравнений в целых числах.

Диофантовы уравнения.

Диофантовы уравнения – алгебраические уравнения с целыми коэффициентами или системы таких уравнений, у которых разыскиваются целые или рациональные решения.

Названы по имени древнегреческого учёного Диофанта (3 век до н. э.), в книге которого «Арифметика» впервые обстоятельно исследовались такие уравнения.

Задачи диофантовой «Арифметики» решаются с помощью уравнений, а проблемы решения уравнений относятся скорее к алгебре, чем к арифметике, но они имеют свои особенности:

1) они сводятся к уравнениям или системам уравнений с целочисленными коэффициентами. Как правило, эти системы неопределённые, т. е. число уравнений в них меньше числа неизвестных

2) решения требуется найти только целые, часто натуральные.

При решении уравнений в целых и натуральных числах можно условно выделить следующие методы:

1. Способ перебора вариантов.

2. Алгоритм Евклида.

3. Цепные дроби.

4. Метод разложения на множители.

5. Решение уравнений в целых числах как квадратных относительно какой-либо переменной.

6. Метод остатков.

7. Метод бесконечного спуска.

Глава 2. Способы решения уравнений в целых числах.

Способ перебора вариантов.

Задача 1.

Допустим, в аквариуме живут осьминоги и морские звёзды. У осьминогов по 8 ног, а у морских звёзд – по 5. Всего конечностей насчитывается 39. Сколько в аквариуме животных?

Решение.

Пусть х - количество морских звёзд, у – количество осьминогов. Тогда у всех осьминогов по 8у ног, а у всех звёзд 5х ног. Составим уравнение: 5х + 8у = 39.

Заметим, что количество животных не может выражаться нецелым или отрицательным числами. Следовательно, если х – целое неотрицательное число, то и у=(39 – 5х)/8 должно быть целым и неотрицательным, а, значит, нужно, чтобы выражение 39 – 5х без остатка делилось на 8. Простой перебор вариантов показывает, что это возможно только при х = 3, тогда у = 3.

Ответ:(3; 3)

Алгоритм Евклида.

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

Чтобы доказать это утверждение, представим описанный процесс в виде следующей цепочки равенств: если a>b, то

a = bq0 + r1

b = r1q1 + r2

r1 = r2q2 + r3 (1)

. . . . . . . . . . . .

rn – 1 = rnqn

Затем r1, . . . , rn - положительные остатки, убывающие с возрастанием номера. Из первого равенства следует, что общий делитель чисел a и b делит r1 и общий делитель b и r1 делит a, поэтому НОД (a,b) = НОД (b, r1) = НОД (r1, r2) = … = НОД (rn -1, rn)= = НОД (rn, 0) = rn.

Утверждение доказано. Приведённый способ нахождения НОД носит название метода последовательного деления с остатком или алгоритма Евклида, поскольку впервые он был изложен в его «Началах».

Обратимся к системе (1). Из первого равенства, выразив остаток r1 через a и b, получим r1 = a – bq0. Продолжая этот процесс, мы можем выразить все остатки через a и b, получим r1 = a – bq0. Подставляя его во второе равенство, найдём r2 = b(1 + q0q1) – aq1. Продолжая этот процесс дальше, мы сможем выразить все остатки через a и b, в том числе и последний: rn = Aa + Bb. В результате нами доказано предложение: если d – наибольший общий делитель натуральных чисел a и b, то найдутся такие целые числа A и B, что d = Aa + Bb. Заметим, что коэффициенты A и B имеют разные знаки; если НОД (a,b) = 1, то Aa + Bb = 1. Как найти числа A и B, видно из алгоритма Евклида.

Перейдем теперь к решению линейного уравнения с двумя неизвестными. Оно имеет вид:

ax + by = c (2)

Возможны два случая: либо число c делится на d = НОД(a,b), либо нет. В первом случае можно разделить обе части уравнения на d и свести задачу к решению в целых числах уравнения a1x = b1y = c1, коэффициенты которого a1 = a/d и b1 = b/d взаимно просты. Во втором случае уравнение не имеет целочисленных решений: при любых целых x и y число ax + by делиться на d и поэтому не может равняться числу c, которое на d не делится.

Итак, мы можем ограничиться случаем, когда в уравнении (2) коэффициенты a и b взаимно просты. На основании предыдущего предложения найдутся такие целые числа х0 и у0, что ax0 + by0 = 1, откуда пара (сх0, су0) удовлетворяет уравнению (2). Вместе с ней уравнению (2) удовлетворяет бесконечное множество пар (х, у) целых чисел, которые можно найти по формулам

х = сх0 + bt, y = cy0 – at. (3)

Здесь t – любое число. Нетрудно показать, что других целочисленных решений уравнение ах + by = c не имеет. Решение, записанное в виде (3), называется общим решением уравнения (2). Подставив вместо t конкретное целое число, получим его частное решение.

Задача 2.

Найдём, например, целочисленные решения уравнения 2x + 5y = 17. Решение.

Применив к числам 2 и 5 алгоритм Евклида, получим 2 * 3 – 5 = 1. Значит, пара сх0 = 3 * 17, су0 = - 1 * 17 удовлетворяет уравнению 2х + 5у = 17. Поэтому общее решение усходного уравнения таково:

x = 51 + 5t, у = - 17 – 2t, где t принимает любые целые значения. Очевидно, неотрицательные решения отвечают тем t, для которых выполняются неравенства

ì51 + 5t ³ 0

î - 17 - 2t ³ 0

Отсюда найдём – 51/5 £ t £ - 17/2. Этим неравенством удовлетворяют числа - 10, - 9. Соответствующие частные решения запишутся в виде пар: (1,3), (6, 1).

Задача 3.

Сколько можно купить на 100 монет петухов, кур и цыплят, если всего надо купить 100 птиц, причём петух стоит 5 монет, курица – 4, а 4 цыплёнка – одну монету?

Решение.

Пусть х – искомое число петухов, у – кур, а 4z – цыплят. Составим систему ìх + у + 4z = 100

î 5x + 4y + z = 100, которую надо решить в целых неотрицательных числах. Умножив первое уравнение системы на 4 , а второе – на (-1) и, сложив результаты, придём к уравнению -x + 15z = 300 с целочисленными решениями x = -300 + 15t, z = t. Подставляя эти значения в первое уравнение, получим y = 400 - 19t. Значит, целочисленные решения системы имеют вид x = -300 + 15t,

y = 400 - 19t, z = t. Из условия задачи вытекает, что

ì -300 + 15t ³ 0

í 400 – 19t ³ 0

î t ³ 0 , откуда 20 £ t £ 21 1/19, т. е. t = 21 или t = 20.

Ответ.

На 100 монет можно купить 20 кур и 80 цыплят, или 15 петухов, 1 курицу и 84 цыплёнка.

Задача 4.

Крестьянка несла на базар корзину яиц. Неосторожный всадник, обгоняя женщину, задел корзину, и все яйца разбились. Желая возместить ущерб, он спросил у крестьянки, сколько яиц было в корзине. Она ответила, что число яиц не знает, но когда она раскладывала их по 2, по 3, по 4, по 5 и по 6, то каждый раз одно яйцо оставалось лишним, а когда она разложила по 7, лишних яиц не осталось. Сколько яиц несла крестьянка на базар?

Решение.

Пусть х – число яиц. Так как х – 1 делится на 2, на 3, на 4, на 5, на 6, то оно делится на их НОК, равное 60. Значит, х имеет вид 60у + 1. Поэтому для ответа на вопрос задачи надо решить в натуральных числах уравнение 60у + 1 = 7z. С помощью алгоритма Евклида находим у0 = -2, z0 = - 17, откуда все целочисленные решения уравнения имеют вид у = -2 + 7t, z = -17 + 60t, где t – любое целое число. Наименьшее положительное решение получаем при t = 1. В этом случае у = 5, z = 43. Итак, крестьянка несла на базар 301 яйцо.

Ответ.

Крестьянка несла на базар 301 яйцо.

Цепные дроби.

Следующий метод связан с непрерывными или цепными дробями.

Обратимся вновь к алгоритму Евклида. Из первого равенства системы (1) вытекает, что дробь a/b можно записать в виде суммы целой части и правильной дроби: a/b = q0 + r1/b. Но r1/b = 1/b/r1, и на основании второго равенства той же системы имеем b/r1 = q1 + r2/r1. Значит, a/b=q0+1/(q1+r2/r1). Далее получим a/b=q0 + 1/(q1+1/(q2+r3/r2)). Продолжим этот процесс до тех пор. Пока не придём к знаменателю qn

В результате мы представим обыкновенную дробь a/b в следующем виде: a / b = q0 + 1 / (q1 + 1 / (…+ 1 / qn)). Эйлер назвал дроби такого вида непрерывными. Приблизительно в тоже время в Германии появился другой термин – цепная дробь. Так за этими дробями и сохранились оба названия. Ввиду громоздкости развёрнутой записи цепной дроби применяют компактную запись [q0; q1, q2, …,qn].

Задача 5.

Представить дробь 40/31 в виде цепной.

Решение.

40/31 = 1 + 9/31 = 1 + 1/3 /9 = 1 + 1/(3 + 4 / 9) = 1 + 1 / (3 + 1 / 9 / 4) = =1 + 1 / (3 + 1 / (2 +1 / 4)) = [1; 3, 2, 4]

Удобство применения цепных дробей заключается в том, что их свойства не связаны ни с какой системой счисления. По этой причине они эффективно используются в теоретических исследованиях. Но широкого практического применения цепные дроби не получили, так как для них нет удобных правил выполнения арифметических действий.

Метод разложения на множители.

Задача 6.

Решите уравнение в целых числах: x² - y² = 91.

Решение.

Разложим левую часть данного уравнения на множители: (х–у)(х+у)= =91. Так как 91= 1 * 91 =91 * 1=(-1) * (-91) = (-91) * (-1) = 7 * 13 =

= 13 * 7 = (-7) * (-13) = (-13) * (-7), то решение данного уравнения сводится к решению восьми систем:

1)ìx – y = 1

îx + y = 91

(46; 45)

2)ìx – y =- 1

îx + y =- 91

(-46; -45)

3)ìx – y = -91

îx + y = 1

(46; -45)

4)ìx – y = -91

îx + y = -1

(-46; 45)

5)ìx – y = 7

îx + y = 13

(10; 3)

6)ìx – y = -7

îx + y = -13

(-10; -3)

7)ìx – y = 13

îx + y = 7

(10; -3)

8)ìx – y = -13

îx + y = -7

(-10; 3)

Ответ.

(46; 45),(46; - 45),(-46; -45),(-46; 45),(10; 3),(10; -3),(-10; -3),(-10; 3).

Задача 7.

Решите в целых числах х³ + 91 = у³.

Решение.

Перепишем данное уравнение в следующем виде у³ - х³ = 91, разложим левую часть на множители (у – х)(у² + ху + х²) = 91. Заметим, что у² + ху + х² = (у + х/2)² + ¾х² ³ 0 при уÎR.

Значит, решение данного уравнения сводится к решению следующих систем

1)ìу – х = 1

î у² + ху + х² = 91 решая данную систему, получаем (5; 6),(-6; -5);

2)ìу – х = 1

î у² + ху + х² = 1 система не имеет решения в целых числах;

3)ìу – х = 13

î у² + ху + х² = 7 решений в целых числах нет;

4)ìу – х = 7

î у² + ху + х² = 13 решая данную систему, получаем (-3; 4),(-4;3).

Ответ.

(5; 6), (-6; -5), (5; 6), (-6; -5).

Задача 8.

Решите в целых числах ху=х+у

Решение.

Перепишем уравнение в следующем виде ху – х – у + 1 = 1. Левую часть данного уравнения разложим на множители, применяя способ группировки. х(у – 1) – (у – 1) = 1; (у – 1)(х – 1) = 1. Следовательно,

ìу – 1 = 1

îх – 1 = 1

(2; 2)

ìу – 1 = -1

îх – 1 = -1

(0; 0)

Ответ.

(2; 2), (0; 0).

Задача 9.

Решите в натуральных числах 2х² + 5ху – 12у² = 28.

Решение.

Разложим левую часть данного уравнения на множители, для этого перепишем уравнение в следующем виде: 2х² - 3ху + 8ху – 12у² = 28.

Применяя способ группировки, получим (2х – 3у)(х + 4у) = 28. Так как х, у – натуральные числа, то (х + 4у)ÎN и х + 4у ³ 4, тогда возможны следующие случаи:

1)ì 2х – 3у = 1

îх + 4у = 28

(8; 5);

2)ì 2х – 3у = 4

îх + 4у = 7

решений в натуральных числах нет;

3)ì 2х – 3у = 1

îх + 4у = 28

решений в натуральных числах нет.

Ответ.

(8; 5).

Задача 10.

Решите в целых числах 2ху = х² + 2у.

Решение.

Перепишем уравнение в следующем виде х² - 2ху + 2у = 0. Данное уравнение также решается методом разложения на множители, однако, с помощью формулы разности квадратов или способа группировки мы не сможем разложить на множители левую часть этого уравнения, поэтому целесообразнее использовать метод выделения полного квадрата.

(х² - 2ху + у²) - у² + 2у – 1 + 1 = 0, (х – у)² - (у – 1)² =-1.

(х – у – у + 1)(х – у + у – 1) = -1, (х – 2у + 1)(х – 1) = -1.

Решение этого уравнения сводится к решению следующих систем:

ì х – 2у + 1= -1илиìх – 1= -1

í í

î х – 1= 1 î х – 2у + 1= 1

(2; 2) решений в нат. числах нет

Ответ.

(2; 2)

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

Теперь рассмотрим более сложные уравнения.

Задача 11.

Решите в натуральных числах х² - 4ху – 5у² = 1996.

Решение.

Перепишем уравнение в виде (х²-4ху+4у²)–9у²=1996, (х-4у)²–9у²=1996.

Разложим левую часть на множители (х – 5у)(х + у) = 1996.

1996=1 * 1996=2 * 998=4 * 499= -1 * (-1996)= -2 * (-998) = -4 * (-499).

Так как х Î N, yÎN, то (х + у) Î N, причём (х + у) > 1. Если (х + у)ÎN и (х + у)(х – 5у) = 1996, то (х – 5у) Î N. Тогда решение получившегося уравнения сводится к решению следующих систем

1)ìх - 5у = 1

îх + у = 1996

решений в натуральных числах нет

2)ìх - 5у = 499 или ìх - 5у = 4

í í

îх + у = 4îх + у = 499

системы решений в натуральных числах не имеют

3)ìх - 5у = 2 или ìх - 5у = 988

í í

îх + у =998 îх + у =2

(832; 166)решения в натуральных числах нет

Ответ.