Определение. Пусть а, b, причём b Число а делится на число b, или а кратно b (пишут аb), если существует такое  c.  В этом случае число b называется делителем числа а. Если же такого с не существует, то говорят, что а не делится на b, или что а не кратно b .

 

Примеры: 124, поскольку 12=3*4;   

90 15, поскольку  -90=(—6)*15; 

143, поскольку не существует такого c ,что 14=с*3.

 

Как непосредственно следует из определения делимости, все числа, кратные b, имеют вид  сb, где c.

 

Свойство 1.   Если а с, b  с, то (а + b)  с, (а - b) с. 

Свойство 2.  Если a  c, b   с, то (а + b)  с, (а- b) с.

Свойство 3.  Если a   и , b   с, то а

Свойство 4.   Если a  c , то (ab)  с для любого b 

Упражнения

Известно, что а b, c d, Докажите, что (ac) (bd).

Докажите, что если а, то аnn для любого n N.

Докажите, что если а (а + b), то и b  (а+ b).

4. Какие из следующих утверждений верны, а какие -нет? (Верные утверждения необходимо доказать., а для неверных – привести  контрпримеры.)

а) Если а 15, b 15, то (а+b) 15. 

б) Если а 15, а21, то а (15*21).

в) Если а  15, b 15, то (а+b)  15. 

г) Если (а*b)  15, то а  15 или b15. 

5.    Пусть (а*b) с и (а + b)  с. Докажите, что 

a) (a2 + b2); б) (а4+b4)с.

6.     Известно, что m, п — нечётные числа. Докажите, что (m2 -n2)   8.

 

 

Определение. Разделить с остатком  целое число а на натуральное число b — значит представить а в виде 

 а  =qb + r,

где q, r   и 0 ≤ r<b

Число а называется делимым, b  - делителем,  q — частным,  r-остатком.

Подчеркнём ещё раз, что остаток от деления а на b равен 0 тогда и только тогда, когда а  b.

 

Приведём несколько примеров деления с остатком. 

 

1.  Разделите с остатком 100 на 14.

Решение. Очевидно, 100=7*14+2. Поскольку 0<2<14, то данное равенство и выражает результат деления с остатком 100 на 14. Частное в данном случае равно 7, а остаток равен 2. Ответ: 100 = 7*14+2.

 2.  Разделите с остатком  -132 на 5.

Решение. Очевидно, -132= (-27)*5+3. Поскольку 0<3<5, то в данном случае частное равно —27, а остаток равен 3, 

Ответ: 132=(-27)*5+3.

3 а м е ч а н и е. При решении задачи 2. было бы неправильно записать равенство

-132=(-26)*5+ (—2) и сделать вывод, что частное  равно -26   а остаток равен -2, так как остаток всегда должен быть неотрицательным!

Из школы вам хорошо известен способ деления с остатком «в столбик». Однако он годится лишь для случая, когда делимое — положительное число. Следующая задача помогает понять, как быть, если делимое отрицательно.

3. Целое число а даёт при делении на 7 частное q и остаток 2.  Какие частное и остаток даёт при делении на 7 число –а? 

Решение. По условию a=7q +2. Тогда  -a=-7q-2=-7*(q+1)+5=7*(-(q+1))+5.

Ответ: частное равно  -(q+1), остаток равен 5.

Как видно из решения приведённой задачи, частное и остаток от деления числа -а на некоторое число b можно определить, если известны частное и остаток от деления а на b.

 

4. Какой остаток даёт число n2+Зп+5 при делении на n+1  (здесь п — произвольное натуральное число)?

Р е ш е н и е. Заметим, что n2+Зn+5= (n+1) (n+2) + 3. Следовательно, если n+1>3 (т. е. n>2), то остаток равен 3. Рассмотрим случаи  n=1 и n=2.

Если n=1, то n2+Зn+5=9, n+1=2; искомый остаток равен 1.  Если же n=2, то n2+Зn+5=15, n +1 = 3, и искомый остаток равен 0. Ответ: 1 при n=1; 0 при 3 при n=2.

 

Упражнения

7. Разделите с остатком: а) 1005 на 13; б) 1001 на 11; 

в) 4531945 на 761;  г) -150 на 9;  д) 54321 на 4.

8. Нарисуйте числовую ось и отметьте на ней все целые числа, лежащие в промежутке от —20 до 20, которые дают остаток 3 при делении на 7.

9. Число а даёт остаток 7 при делении на 10. Чему равен остаток от деления а на 5?

10.  Может ли число делиться на 8 и давать остаток 10 при делений на 12?

11. Число а даёт при делении на 9 остаток 5, число b- остаток 8. Какой остаток даёт при делений на 9 число 

а) а+ b; б) аb.

12. а) Среди всех чисел, больших 2000 и дающих остаток 4 при делении на 13, найдите наименьшее,

б) Найдите наибольшее число, не превосходящее 10000 и дающее остаток 46 при делении на 94,

13. Найдите наименьшее шестизначное число, которое делится на 321.

14. Число 41 даёт остаток  6 при делении на b, Найдите все возможные значения числа b.

15. Число а даёт остаток 2 при делении на 3 и остаток 1 при делении на 4, Найдите остаток от деления а на 6.

16.Остатки от деления числа п на 3, 5, 7 равны а, b, с соответственно . Докажите, что (70а +21b +15c-n)  105.

17. В одном из подъездов восьмиэтажного дома на первом этаже расположены квартиры с 97 по 102. На каком этаже и в каком подъезде этого дома расположена квартира 178 (все подъезды дома устроены одинаково; на всех этажах одинаковое количество квартир) ?

18.  Было 10 листов бумаги, Некоторые из них разрезали на 7 частей, и так несколько раз. Могло ли в результате получиться а) 2007 листов; б) 2008 листов?

У к а з а и и е. Подумайте, как изменяется число листов после каждого разрезания. Запишите, сколько получится 

листов  после п разрезаний.

19.  Какой остаток даёт число а при делении на b, где

а) а=n2+5n-3, b =n+4 в) а==4n+5, b=2n+3;

б) a=4n+7, b =2n+1; г) а=n2+1, b=4

если n — произвольное натуральное число?

II р и м е  ч а н и е. Ответ в этой задаче зависит от n. Следует записать его аналогично ответу к примеру 4.

20. Найдите все целые числа n такие, что значение данного выражения является целым числом:

а) ; б   ;    в) 

21. а) Докажите, что из восьми целых чисел всегда можно выбрать два, разность которых делится на 7.

б) Верно ли, что из восьми целых чисел всегда можно выбрать два, сумма которых делится на 7?

в) Докажите, что из пяти целых чисел всегда можно выбрать два, разность квадратов которых делится на 7,

22.  Какое наибольшее количество целых чисел можно выбрать, если требуется, чтобы сумма и разность любых двух из них не делилась на 16?

23.  Найдите какое нибудь натуральное число, дающее остаток 1 при делении на 2, остаток 2 при делении на 3, остаток 3 при делении на 4, остаток 4 при делении на 5, остаток 5 при делении на 6, остаток 6 при делений на 7,

24.  1 января 2007 г. пришлось на понедельник. Определите, каким днём недели будет 31 декабря 2050 г.

 

 

Напомним, что целое число b≠0 называется делителем целого числа а, если а  b. Здесь мы будем рассматривать лишь натуральные числа и их натуральные делители.

Выпишем все  например все натуральные делители числа 48:

1, 2, 3, 4, 6, 8, 12, 16, 24, 48,

Несложно заметить, что множество этих делителей обладает определенной симметрией: 1*48=48, 2*24=48, 3*16=48, 4*12=48, 6*8=48. Это легко объяснить: если число а≠0  имеет делитель b, то по определению a=cb, где c. Значит, число с тоже является делителем числа а; таким образом, для любого делителя b найдется парный ему делитель с такой, что произведение b и с равно данному числу а. Такие два делителя называются дополнительными.  В приведенном примере все делители числа 48 разбиваются на пары дополнительных делителей. Однако так бывает не всегда. Рассмотрим, числа 36:

1, 2, 3, 4, 6, 9, 12, 18, 36.

Видим, что 1*36=36, 2*18=36, 3*12=36, 4*9=36. А вот число 6 осталось без пары. Разгадка проста: ведь 6*6=36 — т. е. к делителю 6 будет он сам.

 

Упражнения

Во всех задачах этого раздела речь идёт о натуральных числах и их натуральных делителях.

25. Приведите пример натурального числа, имеющего ровно а) 5делителей ; б) 6 делителей.

26. Докажите, что число имеет нечётное количество делителей только тогда, когда оно является полным квадратом.

27. Пусть а — чётное число, не делящееся на 4, Докажите, что у а поровну чётных и нечётных делителей.

28. Пусть к — количество делителей натурального числа n. Докажите, что к2<4п.

Указание. Разбейте все делители числа n на две группы: в первую отнесите все делители не превосходящие  , а во вторую  - все остальные.

29. Пусть d1,d2,…., dn — все делители некоторого числа а. Докажите, что если d1+d2+,. ,+dn =2a, то 

 

 

О п р е д е л е н и е . Пусть т — произвольное натуральное число. Два целых числа а и b называются сравнимыми по модулю т, если а и b дают одинаковые остатки при делении на т. Пишут ab (mod т). Если же числа а и b не являются сравнимыми по модулю т, то пишут а (mod m).

 Примеры: 7  13 (mod 6);  -8 122 (mod 5); 

400 (mod 9).

 

Можно сформулировать определение иначе.

Определение. Два целых числа а и b называются сравнимыми по модулю т, если (а - b)\т.

Рассмотрим основные свойства сравнений по модулю.

Теорема 2. Если ab (mod m), bc (mod m), то ас (mod m).

Теорема 3. Если а (mod m), c (mod m), то: 

1) а+c b+d (mod m), а a-c-d (mod m); 

2) acbd (mod m).

 

Следствие, Если аЬ (mod m), то ann(mod m) для любого n N.

Как следует из теоремы 3, сравнения по одному и тому же модулю можно складывать, вычитать и умножать. Однако сравнения нельзя делить: так, например, 

10 (mod 8), однако 51 (mod 8),

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

1. Какие остатки может давать квадрат целого числа при делении на 3?

Решенне. Рассмотрим произвольное целое число а. В зависимости от того, какой остаток оно дает при делении на 3, возможны три случая:

а0 (mod 3). Тогда а202-0 (mod 3),

а1 (mod 3). Тогда а212   =1(mod 3).

а2 (mod 3). Тогда а22 1(mod 3),

Итак, возможны два варианта:а20(mod 3) и а2(mod 3).

Это значит возможные остатки от деления а2 на 3 равны 0 и 1.

Ответ: 0; 1

Решим задачу посложнее.

2.  Докажите, что (122n+1 + 11n+2)133 при любом nN.

Решение. Имеем: 122n+1 =12*122n=12*144n. Заметим, что 14411 (mod 133); тогда 144nn(mod 133) и 12 *144n 12*11n (mod 133). Далее, 11n+=112*11n=121*11n       Поскольку 121-12 (mod 133), 

то 121 *11n=-12* 11n(mod 133). 

Тогда 121*44n+121*11n(-12)*11n=0 (mod 133), а это и значит, что(122n+1 + 11n+2)133 , ч.т.д.

Сравнения по модулю позволяют обнаружить  интересную закономерность, связанную с остатками степеней целых чисел. Рассмотрим 2°, 21, 22, 23, .,. Посмотрим, какие остатки дают члены этой последовательности при делении например на5:

2°=1, 21=2, 22=4, 23=83(mod 5), 24=161 (mod 5),

25=32 2(mod 5), 26=644 (mod 5), 27 = 1283 (mod 5), ..

Видно, что, начиная с 24, остатки начали повторяться, Будут ли и дальше? Будут ли они повторяться, если взять другое основание степени вместо 2 и другое  число вместо 5?

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

Рассмотренную закономерность можно применять для решения некоторых задач,

3.  Найдите остаток от деления 2222007 на 7,

Решение. Поскольку 222=31*7+5, то 2225 (mod 7), тогда 2222007 52007 (mod 7). Найдём остатки от деления на 7 первых нескольких степеней числа 5;

5° = 1, 

51=5, 

52=254 (mod 7),

 53=52*54 *5=206 (mod 7), 

54=53*55=302 (mod 7), 

55=54*52*5=103 (mod 7), 

56=55*53*5=151 (mod 7),

Как видно, 565° (mod 7), а следовательно, длина периода, с которым повторяются остатки от деления 5n на 7, равна 6, Это значит, что 56k+r5r (mod 7) для любых к, rN0. Заметим, что 2007=334*6+3; тогда 52007=5334*6+3536 (mod 7). Ответ: 6.

 

4.Найдите остаток от деления числа 22007 на 3.

Решение. Очевидно, 21 (mod 3); следовательно, 22007 (—1)2007= -12 (mod 3). Таким образом, искомый остаток равен 2. Ответ: 2.

Обратите внимание на то, что при решении задачи 4 мы свели основание степени к —1. Сведение основания к 1 или — 1 часто упрощает вычисления, поскольку lnl (mod к) для любых n и  k N, При помощи этого приёма можно, например, предложить более простое решение задачи 3. Заметим, что 5 -2 (mod 7); тогда 52007  (-2)2007 (mod 7), Далее, заметим, что 23=8l (mod 7). Тогда  22007=23*669 = (23)6691669=1 (mod 7). Следовательно, 52007 -22007-16 (mod 7). Таким образом, искомый остаток равен 6.

 

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

 

5. Докажите, что (аn—bn) (а—b) при любых n N, а, bZ, a b.

Решение. Положим для определённости, что а>6. Очевидно, (а-b)(a-b), т.е. ab (mod (а-b)). Следовательно,

an bn (mod (a—b)), т. е, (an-bn) (а-b), что и требовалось доказать.

 

Упражнения

30. Какие остатки может давать полный квадрат при делении на а) 4;  б) 5;  в) 6;  г) 7;  д) 8?

31. а) Докажите, что  а²+1 не делится на 3 ни при каком 

a Z,

б) Докажите, что а2+2 не делится на 5 ни при каком aZ,

32. Число а даёт остаток 3 при делении на 5. Чему равен остаток от деления на 5 числа а2—4а?

33.  Докажите, что числа a) 104 и 106; б) 105 и -1; в) -123456789 и 9876543210 дают одинаковые остатки при делении на 11.

34.  Докажите, что если а2+b2 делится на 7, то числа а и b делятся на 7.

35. Докажите, что число вида 9n+1, где n N, не может оканчиваться более, чем одним нулём.

Указание. Используйте сравнения по модулю 4,

Имеет ли уравнение Зx2—4у2=13 целочисленные решения?

36. Докажите, что уравнение x2+4x—8y=11 не имеет решений в целых числах.

37. Докажите, что (25n-2+5n-1 *Зn+1) 17 при любом n N.

38.  Докажите, что (52n+1*2n+2+3n+2*22n+1) 19 при любом no

39.  Найдите остаток от деления числа 7100+11100 на 13.

40.  Найдите последнюю цифру числа 20072007.

41.  На какую цифру оканчивается число  ?

42.  Найдите две последние цифры числа 

Указание. Число, образованное двумя последними цифрами числа n, — это остаток от деления n на 100.

43.  Найдите остаток от деления 10! на 13.

Примечание. Если n N, то через n! (читается «эн факториал») обозначается произведение всех натуральных чисел от 1 до n , n! = 1*2*3*…*п. Также полагают, что 0!=1

44.  Докажите, что (an+bn)  (а+Ь) при любом нечётном nN.

45.  Докажите, что (а2n—b2n)  (а+b) при любом n.