Презентация на тему Презенация по математике Делимость

Z, m ∈ N.
Числа a и b называются

сравнимыми по модулю m, если (a−b) делится на m. Иными словами, a сравнимо с b по модулю m, если числа a и b имеют одинаковые остатки при делении на m.
Обозначение a ≡ b (mod m).
Примеры: 13 ≡ 37 (mod 6) ;
−12 ≡ 3 (mod 5) ;
13 ≡ 5 (mod 4).

c ≡ d (mod m).
Тогда a + c

≡ b + d (mod m) ;
a − c ≡ b − d (mod m) ;
ac ≡ bd (mod m).

Доказательство:
Пусть a − b = pm, c − d = qm, где p, q ∈ Z.
Тогда
(a + c) − (b + d) = a + c − b − d = (a − b) + (c − d) = pm + qm = m (p + q) . Это выражение делится на m.
(a − c) − (b − d) = a − c − b + d = (a − b) − (c − d) = pm − qm = m (p − q) делится на m;
ac − bd = ac − bc + bc − bd = c (a − b) + b (c − d) = cpm + bqm = m (cp + bq) делится на m.
Значит a + c ≡ b + d (mod m) ; a − c ≡ b − d (mod m) ;
ac ≡ bd (mod m).

Тогда
a ² ≡ b ² (mod m) ;

a ³ ≡ b ³ (mod m) ;
· · ·
≡ (mod m), n ∈ N.
Иначе говоря, обе части сравнения можно возводить в любую натуральную степень.
Примеры:
16 ≡ 9 (mod 7) ⇒ 256 ≡ 81 (mod 7) ;
5 ≡ 2 (mod 3) ⇒ 125 ≡ 8 (mod 3) ;
10 ≡ 3 (mod 7) ⇒ 10000 ≡ 81 (mod 7).

б)

в)

Решение: а)



б)




в)

делится на 27.
Число 10 бессмысленно

сравнивать по модулю 27, поэтому представим

Заметим, что 100 ≡ 19 ≡ −8 (mod 27), откуда получаем

на 19

Заметим, что

Ответ: 11.

простое число, тогда для любого натурального а

или

Доказательство. Рассмотрим два случая: a делится на p; a не делится на p.
1) a делится на p;
Тогда используя сравнения запишем:
a ≡ 0 (mod p);
ap ≡ 0 (mod p);
Или ap ≡ a (mod p)
В этом случае теорема доказана.








.

2a, 3a,...,(p - 1)a (*).
Покажем, что эти числа дают

разные остатки при делении на p. Очевидно, остаток также не может быть 0.
Докажем от обратного.
Пусть какие-то два числа ka, na имеют одинаковые остатки при делении на p (пусть k > n). Тогда разность ka - na делится на p. Значит (k - n)a делится на p. Но a не делится на p, а разница k - n меньше p и отлична от нуля, потому также не делится на p. Мы пришли к противоречию - наше предположение, что числа (*) могут давать одинаковые остатки при делении на p ошибочно. Запишем это:
a ≡ r1 (mod p);
2a ≡ r2 (mod p);
...
(p - 1)a ≡ rp - 1 (mod p);
Используя свойства сравнения перемножаем предыдущие сравнения. Так как всего множителей p - 1, а все остатки при делении на p разные, то справа будет (p - 1)!
ap - 1(p - 1)! ≡ (p - 1)! (mod p);
(ap - 1 - 1)(p - 1)! ≡ 0 (mod p);
Но (p - 1)! не делится на p, так как p - простое, а все множители факториала меньше p. Значит (ap - 1 - 1) делится на p.
(ap - 1 - 1) ≡ 0 (mod p); ap - 1 ≡ 1 (mod p); ap ≡ a (mod p);
Что и требовалось доказать.

делится на 143
Решение. Докажем, что

и
По теореме Ферма

По свойствам делимости, если и

то

17. Докажите, что либо  n8 + 1,  либо  n8

– 1  делится на 17.

Решение.

По теореме Ферма



а значит один из множителей делится на 17.

число a561- a делится на 561.
Решение
По малой теореме

Ферма, при любом целом a и простом p число
ap - a делится на p (или ap-1-1 делится на p при a, не делящемся на p). Также будем пользоваться тем фактом, что xn-1 делится на x-1 при любом целом x и любом натуральном n. (Это следует из разложения xn - 1=(x - 1)(xn-1 + xn-2 + ... + x + 1).) Прямо теоремой Ферма воспользоваться нельзя, так как 561=3*11*17 - составное число. Докажем вначале, что a561 - a делится на 17. Если a делится на 17, то все ясно. Если нет, то a561-a = a(a560-1) = a((a16)35-1) делится на a16-1, что в свою очередь делится на 17 по теореме Ферма (можно в этом убедиться и непосредственно, перебирая остатки от деления на 17). Таким же образом, используя, что 561 - 1=560 делится на11-1=10 и 3 - 1=2, доказываем, что a561-a делится на 11 и на 3. Если число делится на 17, на 11 и на 3, то оно делится на 561=3*11*17.

соседними цифрами,
делится на 17 или на 23. Последняя

цифра числа 1.
а) Делится ли данное число на 3?
б) Какова первая цифра числа?

Решение. Выпишем все двузначные числа, делящиеся на 17 или 23. Это 17, 34, 51, 68, 85, 23, 46, 69, 92. У всех этих чисел последние цифры различны, значит, искомое число мы сможем восстановить однозначно.
Последняя цифра 1, значит, соответствующее двузначное чисто 51, т.е. предыдущая
цифра в числе 5.

Эта цифра 5 соответствует двузначному числу 85, следовательно, перед ней стоит цифра 8.

числа: 692346851.
Набор 92346 будет теперь всё время повторяться.

Всего же цифр 1992, в том числе: 3 последние, 5 цифр из периода, встречающиеся 397 раз, и ещё 4 цифры — последние 4 цифры периода, они же — первые 4 цифры числа. Таким образом, первая цифра искомого числа 2.
Найдем сумму цифр этого числа:
2 + 3 + 4 + 6 + 397(9 + 2 + 3 + 4 + 6) + 8 + 5 + 1 = 9557.
Это число не делится на 3, значит и данное в условии число не делится на 3.
 
Ответ: а) нет; б) 2.

что нечётное число не делится на чётное, а значит,

не может стоять в окружении чисел одинаковой чётности. Отсюда следует, что нечётные числа стоят парами. Однако среди чисел 1, 2, ..., 9 нечётных чисел пять, и поэтому из них нельзя образвать пары.
 
Ответ: а) да; б) нет.

что a > b > c . Среднее арифметическое

этих чисел делится на 13.
а) Найдите наименьшую сумму а+b + с          такую, что она является квадратом натурального числа.
б) Найдите наибольшее значение числа c, если
a =32 и сумма а+b + с   имеет наименьшее значение.
в) Найдите наименьшее число b, если известно, что числа c, b и а   в указанном порядке составляют арифметическую прогрессию с разностью n.  
г) Если известно, что числа c, b и a в указанном порядке составляют возрастающую арифметическую прогрессию с разностью n   при котором число c  будет наименьшим , и все члены арифметической прогрессии будут являться квадратами натурального числа.

где k   – натуральное.

Значит,

a + b + c = 39k. Таким образом, a + b +c  является квадратом и делится на 39 = 13    3 поэтому минимальное возможное значение a + b + c = 39² =1521                       

б) Из пункта а) получаем, что b + c = 39k - 32. Если сумма
a + b + c    минимальна, то и b + c  минимально, значит
k = 1    и b + c = 7  Вспомнив, что по условию b < c получаем, что c   < 3  

в) По условию a + b + c = 39k, а из того, что c, b, a — арифметическая прогрессия, следует равенство  
b – c = a – b или 2b = a + c или a + b + c = 3b Значит, 3b=39k или b=13k . b должно быть минимально, поэтому b=13        

= r² .Тогда 2q² = r² + p² .
Из

предыдущего пункта q  кратно 13. Если n  и c  минимально, то и b   должно быть минимально, значит p² + q² = 2 169 = 338. Подбором получаем, что единственная пара чисел (p, q) такая, что p 

каждой стороне — произведение чисел, записанных в её концах,

а внутри треугольника — произведение чисел, записанных в его вершинах. Сумма всех семи чисел равна 1000. Какие числа записаны в вершинах треугольника?
Решение.
Пусть в вершинах треугольника стоят числа a, b и с . Из условия следует равенство:
 a + b +c + ab + bc + ac + abc = 1000
Добавим к обеим частям единицу:
  a + b +c + ab + bc + ac + abc+1 = 1001
(c+1)+(c+1)a+(c+1)b+(c+1)ab=1001
 (c+1)(1+a+b+ab)=7 11 13
(c+1)(a+1)(b+1)= 7 11 13
 

 

 

единицы, а все множители в правой части — простые

числа. Значит, с точностью до перестановки, числа a + 1 , b +1 и с+1 равны 7, 11, 13. Значит числа в вершинах треугольника на единицу меньше и равны 6, 10, 12.
 

которых равно 720 и
а) пять из них; б) три

из них
образуют геометрическую прогрессию?
Решение.
Предположим, что существует пять чисел, образующих геометрическую прогрессию и произведение их равно 720, т.е.

но 720 не является пятой степенью никакого целого числа.
Разложим 720 на множители:
Из этих чисел только три могут образовать
геометрическую прогрессию 1, 2, 4
Получим произведения пяти чисел:

Вася дописывает на доску одно число: либо вдвое большее

какого-то из чисел на доске, либо равное сумме каких-то двух чисел, написанных на доске (таким образом, через одну минуту на доске появится второе число, через две ― третье и т.д.).
а) Может ли в какой-то момент на доске оказаться число 2012?
б) Может ли в какой-то момент сумма всех чисел на доске равняться 63?
в) Через какое наименьшее время на доске может появиться число 784?

на 7. Действительно, исходное число делится на 7, в

случае удвоения числа делящегося на 7, получится число, делящееся на 7. А при сложении чисел, делящихся на 7, также получится число, делящееся на 7. Таким образом, все числа на доске будут делиться на 7, а 2012 на 7 не делится, следовательно, оно не может появиться на доске .
2. В условии не сказано, что одно число нельзя удваивать несколько раз, поэтому получим:

или
7+14+14+14+14=63