Тема 2. Действия над натуральными числами. Принцип Дирихле.

 

Свойства действий сложения, вычитания, умножения и деления натуральных чисел хорошо известны (см. учебник). Например, если а, b, c, d - числа, то верны следующие равенства: a+b=b+a, a×b=b×a, (a+b)+c=a+(b+c), (a×b)×c=a×(b×c), a×(b+c)=a×b+a×c, a×(b-c)=a×b-a×c, a×(b+c+d)=a×b+a×c+a×d, a×(b+c-d)=a×b+a×c-a×d и многие другие. Если мы хотим вычислить сумму из трех слагаемых S=a+b+c, то, расставляя скобки и переставляя слагаемые, эту сумму можно найти тремя различными способами: S=(a+b)+c или S=(b+c)+a или S=(a+c)+b.

 

Задача 1. Сколькими способами, расставляя скобки и переставляя слагаемые, можно вычислить сумму четырех чисел a, b, c и d ?

 

Рассмотрим равенство a×(b+c)=a×b+a×c, где a, b, c - некоторые числа. Вычисление выражения a×(b+c) требует выполнения двух действий: сложения чисел b и c, а затем умножения полученной суммы на число а. В тоже время вычисление равного выражения а+b=a×c требует выполнения трех действий: умножения а на b, умножения а на c, а затем сложения двух полученных произведений. Ясно, что первый способ вычисления более рационален, чем второй.

 

Задача 2. Укажите более рациональные способы вычисления следующих числового и буквенного выражений: a) 1997×1998+1996×1997-1996×1997; б) a×b×c-a×c×d+a×b-a×d.

 

Пусть a, b и q - такие натуральные числа, что а=b×q. Тогда говорят, что число а делится нацело (или без остатков) на число b и пишут а:b (читается: “a делится на b”). Также в этом случае говорят, что b делит нацело (или без остатка) число а пишут b½a (читается: “b делит a”). При этом число а называется делимым, число b - делителем, а число q - частным.

 

Задача 3. Делимое в шесть раз больше делителя, а делитель в шесть раз больше частного. Чему равны делимое, делитель и частное ?

 

Указание: пусть а=bq, тогда по условию b=6q и т.д¼

По десятичному представлению натуральных чисел можно определить делятся ли они нацело на 2, 3, 4, 5, 9, 10 или 100, что бывает полезным при решении многих задач. Сформулируем некоторые признаки делимости натуральных чисел: число делится на 2 , если его последняя цифра четная, т. е. равна 0, 2, 4 , 6 или 8; число делится на 4, если  число, образованное его последними двумя цифрами, делится на 4, например, 123456 делится на 4 так как 56 делится на 4, а число 12345678 не делится на 4 так как 78 не делится на 4; число делится на 5, если его последняя цифра 0 или 5; число делится на 3, если сумма его цифр делится на 3; число делится на 9, если сумма его цифр делится  на 9. Ясно, что если число оканчивается на 0, то оно делится на 10, а если на 00, то делится на 100 и т. д¼

 

Задача 4. Ученик младшего лицейского класса Саша Пушкин придумал новые две теоремы : a) если натуральное число делится на 27, то и сумма его цифр тоже делится на 27;

б) если сумма цифр натурального числа делится на 27, то и само число делится на 27. Сможет ли Саша доказать свои теоремы ?

 

Указание: найдите числовые примеры, когда эти  два утверждения не верны.

Отметим, что натуральное число делится на 6, если оно делится на 2 и на 3; делится на 15, если оно делится на 3 и на 5. однако, если число делится на 2 и на 6, то совсем необязательно, чтобы оно делилось на 12. Например, 18 делится на 2 и на 6, но оно не делится на 12.

В общем случае, если натуральное число n делится нацело на натуральные числа a и b, которые имеют только один общий натуральный делитель единицу, то  n(ab).

 

Задача 5. а) Замените в числе 645*723 звездочку цифрой так, чтобы получившееся число делилось нацело на 3. Сколько решений имеет эта задача ?

б) Найдите все четырехзначные числа вида 71*1*, которые делятся нацело на 45.

 

Задача 6. Докажите, что всякое трехзначное число, записанное одинаковыми цифрами, делится на 37.

 

Указание: число aaa представимо в виде произведения числа a на число…

Каждое натуральное число имеет натуральные делители. Например, число 45 имеет только следующие делители: 1, 3, 5, 9, 15 и 45. А число 7 имеет только два делителя : 1 и 7, таким же свойством обладают числа: 11, 73, 101, 1103, 109619 и др¼ Все числа с таким свойством называются простыми, т. е. натуральное число называют простым, если оно имеет ровно два натуральных делителя - единицу и самого себя. Натуральные числа, имеющие больше двух натуральных делителей, называют составным. Например, 4 - составное число, так как имеет три делителя 1, 2  и  4, а число 1 не является  простым  и не является составным,  так как имеет только один делитель 1. Первыми простыми числами, не превосходящими 50, являются 2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47.Число 2 наименьшее простое число, оно является четным в то время, когда все другие простые числа являются нечетными. Древнегреческому ученому Евклиду в 3-ем веке до нашей эры ( приблизительно 2350 лет назад) удалось доказать, что простых чисел бесконечно много. Простые числа имеют большое значение, так как всякое натуральное число можно представить в виде произведения простых множителей и такое представление единственно с точностью до порядка следования множителей. Например, 30=2×3×5=2×5×3=3×2×5=5×3×2. Разложение числа на простые множители можно осуществлять постепенно, например, 180=2×90=2×2×45=2×2×3×15=2×2×3×3×5. Итак, 180=2×2×3×3×5.

 

Задача 7. Разложить на простые множители числа, если известно, что их простые множители не превосходят 50: a) 2370; б) 27720; в) 1529385.

 

Задача 8. а) Выпишите все простые числа в порядке возрастания, не превосходящие 100. б) Выпишите все составные числа, не превосходящие 100, и найдите их разложения на простые множители. в) Какое из составных чисел, не превосходящих 100, имеет наибольшее число простых делителей ?

 

Если удалось натуральное число представить в виде произведения простых чисел, то легко выписать все его делители. Например, 18=2×3×3, следовательно все делители числа 18 получаются комбинированием всевозможных произведений из чисел 1, 2, 3, 3, то есть числа 1, 2, 3, 6, 9, и 18 исчерпывают все натуральные делители числа 18.

 

Задача 9. Найти все делители числа 6545, если известно, что все его простые делители не превосходят 50.

 

Чем больше натуральное число, тем в общем случае труднее его разложить на простые множители. Например, 4294967297 - составное число, являющиеся произведением двух простых чисел 641 и 6700417 (проверьте это), но этот факт не был в свое время обнаружен знаменитым математиком П. Ферма (1601-1665) и он посчитал это число простым !

Деление одного  натурального числа нацело на другое, может выполнятся например, любое нечетное число не делится нацело на четное. При делении натуральных чисел на 3 получаем: 1=3×0+1; 2=3×0+2; 3=3×1+0; 4=3×1+1; 5=3×1+2; 6=3×2+0; 7=3×2+1; 8=3×2+2; 9=3×3+0 и т. д¼ Отсюда заключаем, что при делении на 3 могут получаться  остатки 0, 1 и 2 , а частное q может принимать значение 0, 1, 2, 3, 4 и т. д. Числа, делящиеся на 3, имеют вид 3q; числа, дающие при делении на 3 остаток 1 имеют вид 3q + 1; а числа, дающие при делении на 3 остаток  2, имеют вид 3q+2.

 

Задача 10. Какие остатки могут давать натуральные числа при делении на 4 ? Какой вид имеют натуральные числа, дающие одинаковые остатки при делении на 4 ?

 

В общем случае при делении натурального числа а на натуральное число b получаем остаток r и частное q такие, что 0<r<b и а=bq+r (еще пишут a:b=q(ост. r)). Если r=0, то а=bq и значит число а делится нацело на число b. Обычно деление а на b ( нахождение частного q и остатка r) осуществляется путем деления чисел столбиком. Например, пусть а=258 и b=17. Тогда (см. рядом), деля столбиком 528 на 17, получаем 528:17=31 (ост. 1) или  528=17×31+1, то есть q=31 и r=1.

 

Задача 11. При делении числа а на 121 получили частное q=101 и остаток r=100. Найдите частное и остаток при делении числа а на 200.

 

Задача 12. Какие цифры надо поставить вместо звездочек в делимом, частном и остатке, чтобы в результате деления получился наибольший из возможных остатков в равенстве 6*=17×*+**?

 

Указание: r=16.

Если числа а и с(а>с) при делении на b дают одинаковый остаток, тогда их разность (а-с) делится нацело на b. Действительно, при а=bq+r и c=bs+r получаем а-с=(bq+r)-(bs+r)=(bq-br)+(r-r)=b×(q-s)+0, то есть b делит нацело число (a - c).

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

Доказательство. Сначала сформулируем так называемый принцип Дирихле: если имеется n клеток, в которые посадили не менее n+1 кроликов, то в какой-то клетке окажется не менее двух кроликов. Действительно, если бы в каждой клетке было бы не более одного  кролика, то во всех клетках было бы не более n кроликов, что противоречит условию.

Теперь рассмотрим три натуральных числа а, b и  c. Положим, что эти числа - кролики, при этом в один ящик будем рассаживать только четные числа, а во второй - нечетные. Согласно принципу Дирихле в каком-то ящике из этих трех чисел - кроликов окажется не менее двух чисел, т. е. мы обязательно найдем два числа, которые при делении на 2 имеют одинаковые остатки (или, что то же самое, имеют одинаковую четность). Как было отмечено ранее перед упражнением, разность этих чисел делится на 2, т. е. четное число.

 

Задача 13. Докажите, что среди любых 1998 натуральных чисел можно найти два числа, разность которых делится на 1997.

 

Вернемся к принципу Дирихле. Допустим в 8 клеток мы рассадили 26 кроликов. Если бы в каждой клетке было не более трех кроликов, то во всех восьми клетках было бы не более 8×3=24 кроликов, что противоречит условию (мы рассадили 26 кроликов!). Полученное противоречие означает, что в какой-то клетке находится не менее четырех кроликов !

К такому же выводу мы придем, если попытаемся равномерно рассадить кроликов по клеткам. Так как 26=8×3+2, то даже если мы посадим в восемь клеток по три кролика, у нас останется еще два кролика, из которых нам придется хотя бы одного посадить в клетку с тремя кроликами, и опять мы найдем клетку, в которой не менее четырех кроликов. В общем случае, если в b клетках сидит а кроликов, где а>b и а=bq+r (q - частное, а r - остаток при делении а на b), то при r=0 найдется клетка, в которой будет не менее q кроликов, а при r=0 найдется клетка, в которой будет не менее q+1 кроликов. Этот факт называют обобщенным принципом Дирихле по фамилии немецкого математика Л. Дирихле (1805- 1859), который применял этот принцип в своих работах.

Упражнение 2. Семь школьников съели коробку конфет, в которой 16 конфет. Докажите, что хотя бы один школьник съел не менее трех конфет.

Доказательство. Так как 16=7×2+2(а=16, b=7, q=2 и r=2), то считая школьников “клетками”, а конфеты “кроликами”, по обобщенному принципу Дирихле какой-то школьник съел не менее q+1=3 конфет.

 

Задача 14. Какое наименьшее число учеников должно быть в классе, чтобы, не зная в каком месяце родился каждый ученик, наверняка можно было бы сказать: “ В классе не менее трех учеников, родившихся в один и тот же месяц” ?