Доказательство. Обозначение: d|a – d делит a, – a делится на d.

Лекция №15-16

Теория делимости.

Определение.

Пусть a и d – целые числа. Говорят, что d – делитель a, или что d делит a, или что a кратно d, или что a делится на d, если существует такое число c, что a = d ∙ c.

Обозначение: d|a – d делит a, – a делится на d.

Пример 1.

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

Доказательство.

Так как d|a, то существует целое число такое что . Так как d|b, то существует целое число , такое что . Рассмотрим a+b=d· +d· =d( + )=d· , где – целое число. Итак, a+b= d· . Значит d|(a+b) (по определению). Аналогично доказывается, что d|(a-b).