Similar presentations:
Делимость натуральных чисел
1. Делимость натуральных чисел
Лекция 52 курс
2. Замечание:
1. Вопрос о существовании разности намножестве натуральных чисел
решается очень просто: достаточно,
чтобы уменьшаемое было больше
вычитаемого.
a-b существует, если a>b,
a, b N
где
3.
2. Для операции деления такогопростого признака нет.
Поэтому и возникла в математике теория
делимости натуральных чисел.
4. Определение отношения делимости натуральных чисел
• Пусть даны натуральные числа a и b.a; b N
Говорят, что число a делится на b, если
существует такое натуральное g , g N
что
a b g
5.
b называют делителем числа a, числоa – кратным b
Обозначают
a b
Читают : a кратно b
6.
• Что общего и что различного впонятиях?
• 1. «делитель данного числа»
• 2. « делитель»
7.
• 24 : 5 - число 5 есть делитель. Компонентдействия деления.
• 24 : 6 число 6 – не только делитель
(компонент действия деления), но и делитель
числа 24, так как 24=6·4.
• Число b называется делителем числа a тогда,
когда число a есть кратное b.
8. Уточним понятие «отношение делимости»
• 1. Единица (число 1) являетсяделителем любого натурального числа,
так как a=1·a.
• 2. Теорема №1.
• Делитель b данного числа a не
превышает этого числа.
• Если a b, то b a
9.
• Доказательство:• Так как
a b , то существует такое
g N , что a = b·g
Значит, a - b =b·g – b = b ·(g -1)
Так как g N, то g ≥ 1
Тогда, b·(g-1) ≥ 0
Следовательно, b ≤ a
10. Следствие:
• Множество делителей данного числаконечно.
• Например:
• Делители числа 36 образуют конечное
множество
A 1,2,3,4,6,9,12,18,36
11. Сопутствующие понятия Простые и составные числа
• Определение:• Простым числом называется такое
натуральное число, большее 1, которое
имеет только два делителя – единицу и
само это число.
12. Например:
• Число 7 – простое.• Число 2 – простое.
(единственное простое четное число).
• Числа 3,11,19, 23, 117 ... являются
простыми, так как эти числа имеют по
два делителя.
• Число 1 ……?
13.
• Определение:• Составным числом называется
натуральное число, которое имеет
более двух делителей.
• Например: 4,6,12,121, 45, 225 –
составные числа.
• Число 1- составное?
14.
• Чисел кратных данному числу,бесконечное множество.
• Например:
Числа кратные 6 образуют множество:
A 6,12,18,24,30,36,42,48...
15.
• Общий вид чисел, кратных 6:x=6·n, где n N
• Общий вид чисел, кратных 5:
x=5·n, где n N
• Общий вид чисел, кратных k:
x=k·n, где n N
16. Классификация натуральных чисел
• Основание классификации - признак: бытьпростым числом
Множество
натуральных
чисел
Число 1
Простые
натуральные
числа
Составные
натуральные
числа
17. Свойства отношения делимости
• 1. Отношение делимости рефлексивно,антисимметрично и транзитивно.
• 2. Отношение делимости есть
отношение нестрогого порядка
18. Теорема 1.
• Отношение делимости рефлексивно.(любое натуральное число делится само
на себя).
• Если отношение делимости
обозначить –R, а элемент –n, то свойство
рефлекcивности имеет вид: n R n
19. Доказательство
• Для любого натурального aсправедливо равенство a=a·1.
1 N ,
по определению делимости
a a
Что и требовалось доказать.
20. Теорема 2
• Отношение делимости антисимметрично (если a кратно b, то b не кратно a)• Если отношение делимости
обозначить –R, а элементы отношения –
a и b, то свойство антисимметричности
имеет вид:
если a R b, то b R a
21. Доказательство: (доказательство осуществляется методом от противного)
• Предположим обратное.Пусть b a, но тогда a ≤ b.
По условию
a b.
Следовательно, a ≥ b
Неравенства a ≤ b и a ≥ b
справедливы, если a=b. Противоречие.
Значит наше предположение не верно.
22. Теорема 3
• Отношение делимости транзитивно.Если a b и b c , то a c
Если отношение делимости
обозначить –R, а элементы отношения – a,b,c
то свойство транзитивности имеет вид:
если a R b и b R c, то a R c .
23. Доказательство
• Еслиa b, то
( g N ),
такое, что
a=b·g
•Если
b c, то ( p N ),
такое, что
b c p
ассоциативный
•Тогда имеем: a = b·g = (c·p)·g = c·(p·g)
•Число p · g – натуральное. Значит :
a c
24. Признак делимости суммы Теорема 4
• Если каждое из натуральных чиселa1 , a 2 ,..., a n
делится на натуральное число b, то
сумма (a1 a2 ... an )
делится на это число.
25. Доказательство
• Если• Если
a1 b,
a2 b,
то ( g1 N ), что a1 b g1
то ( g2 N ), что a2 b g2
--------------------------------------------------
• Если
a n b,
то ( g n N ), что an b g n
26.
• Преобразуем сумму чиселдистрибутивный
a1 a2 ... an b g1 b g 2 ... b g n
b ( g1 g 2 ... g n ) b g
Так как сумма натуральных чисел есть натуральное
число, то ее можно заменить натуральным числом g.
Следовательно,
g1 g 2 ... g n g
А это значит, что сумма
a1 a2 ... an
делится на b.
27. Замечание
• Обратная теорема: если сумма натуральныхчисел кратна натуральному числу c, то
каждое слагаемое кратно этому числу c.
• Обратная теорема не верна.
25=12+13
25 5, а 12 5 и 13 5
• Теорема о делимости суммы есть
необходимое условие, но не достаточное
28. Признак делимости разности Теорема 5
• Если уменьшаемое a и вычитаемое bделятся на число c, то и разность (a-b),
где a>b, делится на c.
a, b, c N , если a b и a c, и b c, то(a b) c
Доказать самостоятельно!
29. Обобщение теоремы 5
• Теорема:Разность двух натуральных чисел a и b
делится на натуральное число с, тогда и
только тогда, когда a при делении на c и
b при делении на c дают одинаковые
остатки.
30. Краткое условие теоремы
• Дано: a>b иa, g, c, p N , таких, что a c g p
b, g1, c, p N ,
Доказать, что
таких, что b c g1 p
a b c
31. Доказательство
• Рассмотрим разность чисел a и b.a b c g p c g1 p
c g p c g1 p c g c g1
c g g1 c k
Следовательно, (a-b) кратно с
32. Например:
• Задание: Не выполняя вычислений,определите делится ли разность чисел
247 и162 на 5.
• 247 при делении на 5 дает остаток 2 и
• 162 при делении на 5 дает остаток 2.
• Значит разность 247-162 кратна 5.
• Действительно 247-162=85,
85:5=17
33. Признак делимости произведения Теорема 6
• Если число a делится на b, топроизведение вида a·x, где x –
натуральное число, делится на b.
a, b, x N , если a b, то(a x) b
34. Доказательство
• Так какa b , то ( g N ), что a b g
Умножим обе части этого равенства на натуральное
число x
Тогда a x b g x b g x
g x натуральное число
Следовательно, (a x) b
35. Следствие:
• Если один из множителей произведенияделится на натуральное число, то и все
произведение делится на это
натуральное число.
• Например:
• 24·978:12=(24:12)·978=2·978=
• =2·(900+70+8)=1800+140+16=1956
36. Еще три теоремы о делимости
• Теорема 1• Если в сумме одно слагаемое не
делится на b, а все остальные
слагаемые суммы делятся на b, то и вся
сумма на b не делится.
37. Доказательство
• Пустьs a1 a2 ... an c
И известно, что
a1 b, a2 b, a3 b,..., an b, но c b
Докажем , что s b
Доказательство проведем методом
«от противного»
38.
• Предположим противное.• Пусть
s b
Имеем:
Преобразуем сумму s
c s a1 a2 ... an
Применим теорему о делимости разности.
Так как s b и a1 b, a2 b, a3 b,..., an b
Следовательно: c b. Противоречие
Значит наше предположение не верно. Что и
требовалось доказать.
39.
• Теорема 2. (задача)• Если в произведении a·b множитель a
делится на натуральное число m, а
множитель b делится на натуральное
число n, то произведение a·b делится
на m·n.
Доказать самостоятельно!
40.
• Теорема 3.• Если произведение a·c делится на
произведение b·c, причем cнатуральное число, то a делится на b.
41. Доказательство
• Так какa c b c , то существует
ассоциативный
a c b c g b g c
Значит
g N
a b g. Следовательно, a b