Комбинаторика и теория вероятности. Решение задач.

Из правила (4.4.4) вытекает, что если а и b взаимно простые, то их произведение равно их наибольшему общему кратному; действительно, в этом случае D(a, b)= 1 и поэтому ab = К(а,b).

Система задач 4.4.

1. Найдите наибольшее общее кратное пар чисел в системе задач 4.1 (с. 49).

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

ГЛАВА 5

ЗАДАЧА ПИФАГОРА

§ 1. Предварительные замечания

Во введении (§ 3, гл. 1) мы упоминали об одной из древнейших теоретико-числовых задач: найти все прямоугольные треугольники с целочислен ными сторонами, т. е. найти все целочисленные ре шения уравнения

x2 + y2 = z2.                        (1)

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

(х, у, z),        (2)

удовлетворяющая уравнению (1), называется пи фагоровой тройкой. Отбросим тривиальный случай, когда одна из сторон треугольника равна нулю.

Ясно, что если множество (2) является пифа горовой тройкой, то любая тройка чисел

(kx, ky, kz),  (3)

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

(6, 8, 10), (15, 20, 25)

являются пифагоровыми тройками, получающимися из простейшего решения (3, 4, 5).

В простейшей тройке (х, у, z) не существует об щего множителя для всех трех чисел. В действительности справедливо более сильное утверждение: ни какие два числа из простейшей тройки не имеют об щего множителя, т. е.

D(x,y) = 1, D(x,z) = 1, D(y, z)= 1. (4)

Чтобы доказать это, предположим, что, например, х и у имеют общий делитель. Тогда они имеют общий простой делитель р. В соответствии с (1) число р должно также делить и z. Итак, (х, у, z) не может быть простейшей тройкой. Такие же рассуждения применимы для доказательства остальных двух утверждений.

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

х=2а+1, у = 2b+1.

После возведения в квадрат этих чисел и сложения их, получим число

х2 + у2 = (2а + 1 )2 + (2b + 1 )2 =

= 2 + 4 а + 4а2 + 4b + 4b2 = 2 + 4 (а + а2 + b + b2),

делящееся на 2, но не делящееся на 4. В соответ ствии с (1) это означает, что z2 делится на 2, но не делится на 4, но это невозможно, так как если z2делится на 2, то и z делится на 2, но тогда z2 делится на 4.

Так как одно из чисел х и у — четное, а другое — нечетное, то z — также нечетное. Для определенно сти будем считать, что в наших обозначениях число х — четное, а у — нечетное.

§ 2. Решение задачи Пифагора

Чтобы найти простейшие решения урав нения Пифагора (1), перепишем его в виде

x2=z2-y2 = (z+y)(z-y). (2.1) ■

Вспоминая, что х — четное, а у и z — оба нечетные, получаем, что все три числа

x, z + у, z - y

четные. Тогда мы можем разделить обе части урав нения (2.1) на 4 и получить

(1/2 x)2 = 1/2(z + y)1/2(z-y).        (2.2)

Обозначим

m1 = 1/2 (z + у), п1 = 1/2 (z — у);        (2.3)

тогда уравнение (2.2) перепишется как

(1/2 x)2=m1n1        (2.4)

Числа m1 и n1 взаимно простые. Чтобы это уви деть, предположим, что

d = D(m1n1)

есть наибольший общий делитель чисел m1 и n1. То гда, как это следует из п. 1 гл. 4, число d должно делить оба числа

m1+n1=z, m1-n1 = у.

По единственным общим делителем чисел z и у в простейшей тройке может быть только 1, поэтому

d = D(m1 n1) = 1.        (2.5)

Так как произведение (2.4) этих двух взаимно простых чисел является квадратом, то можно исполь зовать результат, изложенный в конце § 2 гл. 4 (стр. 50), согласно которому числа m1 и n1 являются квадратами

m1 = m2, n1 = n2, D (m, n ) = 1.       (2.6)

Здесь мы можем без нарушения общности считать, что m > 0, n > 0. Теперь подставим m2 и n2 вместо m1 и n1 соответственно в уравнения (2.3) и (2.4); получим

m2 = 1/2 z + 1/2 у, n2 = 1/2 z - 1/2 у,  m2n2=1/4 x2

т. е.

х = 2mn, у = m2 — n2, z= m2 + n2. (2.7)

Проверка показывает, что эти три числа всегда удов летворяют соотношению Пифагора х2 + у2 = z2.

Осталось определить, какие целые положительные числа m и n в действительности соответствуют про стейшим треугольникам. Докажем, что следующие три условия на числа m иn являются необходимыми и достаточными:

1)        (m, n)=1,

2)        m > n,        (2.8)

3)         одно из чисел m и n четное, а другое — нечетное.

Доказательство. Сначала покажем, что если числа х, у,z образуют простейшую тройку, то усло вия (2.8) выполняются. Мы уже показали, что условие (1) является следствием того, что числа х, у, z взаимно простые. Условие (2) следует из того, что числа х, у, z — положительны. Чтобы увидеть, что условие (3) необходимо, заметим, что если m иn оба нечетные, то в соответствии с (2.7) у и z были бы оба четные, в противоречие с результатами, полу ченными в конце предыдущего параграфа.

Наоборот, если условия (2.8) выполнены, то со отношения (2.7) определяют простейшую тройку: условие (2) обеспечивает положительность чисел х, у и z.

Могут ли какие-нибудь два из этих трех чисел иметь общий простой множитель р? Такое простое число р, делящее два из них, должно также делить и третье в силу соотношения х2 + у2 = z2. Если чис ло р делит х, то оно в соответствии с (2.7) должно делить 2mn. Число р не может равняться 2, потому что у и z нечетные в соответствии с условием (3) и (2.7). Предположим, что р ≠ 2 — нечетное простое число, делящее m. Тогда условие (1) и выражение (2.7) показывают, что р не может делить у и z. Та кие же рассуждения применимы и для случая, если р делит число n.

Найдя необходимые и достаточные условия (5.2.8) для того, чтобы m иn давали простейший треуголь ник, можно вычислить все такие треугольники с по мощью соотношения (2.7). Например, пусть

m = 11, n = 8.

 Наши условия выполнены, и мы находим, что х= 176, у = 57, z =185.

В табл. 1 приведены все простейшие треугольники x, у, z для нескольких первых значений чисел т и n.

Таблица 1

 Задачи для самостоятельной работы:

1. Продлите таблицу для всех значений m ≤ 10.
2. Могут ли два разных набора значений чисел m и n, удовлетворяющих условию (2.8), дать один и тот же треугольник?
3. Найдите все пифагоровы треугольники, у кото рых длина гипотенузы не превосходит 100.

§ 3. Несколько задач

о треугольниках Пифагора

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

Одним из естественных вопросов о простейших треугольниках является следующий. Пусть задана одна из сторон простейшего треугольника Пифагора, как найти остальные? Первым рассмотрим случай, когда известна сторона у. В соответствии с (5.2.7)

у = т2 — п2 = (m + n) (т — n), (5.3.1)

где m и n—числа, удовлетворяющие условиям (5.2.8).

В уравнении (5.3.1) множители (т + n) и (т—n) взаимно простые. Чтобы в этом убедиться, заметим, что эти множители        

a= т+п, b = т — п        (5.3.2)