Файл: Войтишек В.В. Курс лекций по математике для слушателей подготовительного отделения.pdf

Правая часть этой разности сравнила

с нулём по модулю 3

и 9.

Значит,

з

дает

при делении на 3(9)

тот

же остаток,

что

и л .

Отсюда,

если л

делится

на 3 ( 9 ), то

и у

делится

на

3(9) .

ОБРАТНАЯ ТЕОРЕМА.

Если S делится на 3 ( 9 ),

то

и .г

делится

на 3 ( 9 ) .

Доказательство следует из рассмотрения той же разности

и

замечания,

что г

я -s

дают один и тот

же остаток при делении на

3 ( 9 ) . Тогда, если S

делится на 3(9)

(что ^ано

по условию), то

и

л делится на 3 ( 9 ), тогда и только тогда, когда делится на 3(9)

сумма его цифр.

Наконец, с

конечными множествами

связана и о с н о в н а я

т е о р е м а

а р и ф м е т и к и

(приводим доказательство

рии 'чисел, например, Виноградов,

Основы теории чисел).

Каждое натуральное число п.

, которое больше единицы, может

число, допускающее два различных разложения,

то существует и

наименьшее

число

тп

,

обладающее

этим

свойством,

ш

запишем в

таких двух

видах:

.

171 - Р,

Рг

■■■

Рг-

и

m

=я, Яа,

■■■

Ъ

>

гае

pt 4 р&

£ р3 л

.. . d /V ,

Я,* Яя^Яз* - -

простые числа. Заметим,

что

р

f-

f

. ибо m. - наименьшее

по предположению. Следовательно,

или

pt

,

или

pf > Я,

•

Пусть

Р,

* Я,

■

Рассмотрим

целое

число

<*}

^

т- (Р, Ял Яз

.

тогда либо ‘

Of >f)

/=

(p'Pf,. . -Р^-СрЯл ■■■Яз> = Р, (Рц-

Рг-Яе

- Яз ) ,

либо

<***)

1 = Ц Я і » - ? і ) - ( в Я я " - Ъ ) = (ЯгР, >9я--- Ъ-

Из равенства

(ff

х- *)

следует, что

I>о

,

из

равен­

ства сЮ

следует, что

Итак,

Но тогда

жению),

Из

равенства с # * )

видим,

что

р

является множителем

і .

Тогда из

равенства

с* * #)

вытекает,

что р

входит множи­

телем или в

cqf - р, ) ,

Или ъ

q3

■■■qs

(ибо

если

р

входит множителем в произведение

t

= а 6 ,

то

оно непременно

входит множителем или в а ,

или

в 6 \

см.

следствие). Но в

qs qy ..qs

pt

входить не может, так как все

<7.

больше

чем р , .

Поэтому

остается,

что

/>

-

множитель в

разности

<7,-/5

,

и <77?

делится на

р

или, другими

словами,

существует

такое

натураль­

ное

число

/і

, что

cq - fi ) =

к

р,

=>

. Я,=Р,

с ь + о .

Получим,

что

<7

делится на pf

, однако по

предположению

<7 -

число простое. Противоречие. •

Следствие. Если

простое

число

входит множителем

в

произве­

дение ab

,

то оно

непременно входит множителем или в

а

или в

6.

•

Доказательство. Если бы р

не входило

ни в а

,

ни в Ь

то,

перемножая разложения

а.

и

Ь

на

простые множители,

мы получили

бы разложение

а б

на множители,

в котором

нет р.

Но по

предполо­

жению существует такое натуральное число t

,

что

a è = p t .

Поэтому,

перемножая р

и

разложение t

на простые множители,

мы

получим

разложение a b

на простые множители,

с о д е р ж а щ е е

ч и с л о / )

м н о ж и т е л е м .

То

есть

имеем два

разных раз­

ложения а б ,

что противоречит основной теореме (подумайте,

нет

ли в приведенном рассуждении "порочного

кңгга"?).

Со множеством простых чисел связан еще

один факт

(теорема

о бесконечности этого множества). Однако мы сначала рассмотрим

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

Это задачи

целочисленного

программирования.

Задачи целочисленного программирования

5р’ _і е -

Диспетчер обладает

следующими данными:

БагаяПочто­

Плац­

Купей­

Мягкие

ные

вые

картные

ные

I .

Экспресс

I

0

5

-

6

3

2 .

Скорый

I

I

8

4

I

3 . Число мест

в вагоне

0

0

58

40

32

4. Наличный состав

12

8

81

70

27

,

вагонов

Задача. Сколько надо

сделать

экспрессов

( х

) и

скорых

поездов ( у

) , чтобы отправить

на них наибольшее

число

пассажи-

ров?

Решение. I) Учет ограничений из таблиц:

а)

х

+ ц

а

12,

-

число

багажных вагонов;

б)

о х + и і

$

,

.

т . е .

ш $

- число

почтовых

вагонов;

в) 5 х + 8 у 4

Sf

-

число

плацкартных

вагонов;

г ) 6 х

+ 4 y é ?0

-

число

купейных вагонов;

Д) З х

t у

Д 2,7

-

число

мягких вагонов.

Экспресс

вмещает

/■ S i + 6-4Ö + 3 5 2

-

б&ь

пассажиров

Скорый поезд вмещает

s-dS

+ Ч-чо+зг,

= ь з ь

пассажиров

Можно отправить

z

=J(x,u) = в е . б х

+ 656 4

пассажиров.

Найти такую пару целых чисел

( х , у ) ,

чтобы z

стало наибольшим,

одновременно удовлетворяя условиям

(

, / , d ,

£

) ,

а также

из

условия понятно,

что

х > о ,

<j>o.

Каждое из

условий

определяет

полуплоскость. Система условий

£ > ;

х у о ,

у у о

определяет

на плоскости многоуголь­

ник. Всякая точка

этого

многоугольника

(а

нас интересуют только

линейных неравенств.

В теории целочисленного

программирования

показано (см.

І26І),

что крайнее значение функции

Z

= б 2 6 х + ь 5 Ь у

следует

искать

в

вершинах многоугольника. Таких вершин шесть:

( о ; О );

( o j ) ;

( j i i ) i

(S U ) ; ( f ; § ) ; (9;o)

- это

результат решения

некоторых систем двух уравнений (мы же ищем точки пересечения

прямых),

получаемых из семи

ограничительных неравенств. Общее число