Делимость целых чисел

Наиболее популярными числовыми множествами являются следующие:

N – множество натуральных чисел,

Z – множество целых чисел,

Q – множество рациональных чисел,

R – множество вещественных чисел,

C – множество комплексных чисел.

Они связаны следующим отношением включения: N Z Q R C.

Отношения >, <, ³ и £ полностью упорядочивают множество R. Если A Í R и a Î A, то в дальнейшем будем обозначать A _{> a}, A _{< a}, A _{³ a} и A _{£ a} подмножества A, состоящие из всех чисел, больших a, меньших a, больших или равных a и меньших или равных a соответственно.

Множество целых чисел Z – счетное, состоит из элементов 0, ±1, ±2,…, ± n,… На нем определены две алгебраические операции – сложение и умножение. Эти операции обладают следующими общими свойствами (для любых a, b, c Î Z):

1. ассоциативность: , ;

2. коммутативность: , ;

3. существуют нейтральные элементы – 0 относительно сложения и 1 относительно умножения соответственно: , .

Кроме того, операция сложения обладает свойством:

4. для каждого существует единственное такое, что: .

Ясно, что здесь – противоположное целое. Это свойство позволяет ввести на Z вспомогательную операцию – вычитание. – целое число – разность чисел a и , получаемое вычитанием из a.

Умножение и сложение связаны свойством:

5. – закон дистрибутивности умножения относительно сложения.

Аналог свойства 4 для умножения выполняется лишь для двух целых чисел: 1 и –1.

Вообще говоря, для каждого целого существует обратное относительно умножения (то есть такое число , что ), но оно является рациональным и не обязательно целым числом. Следовательно, результат операции деления целого числа a на целое число есть число рациональное и в редких случаях является целым. В общем же случае имеет место следующая теорема.

Теорема 1.1.1 (о делении с остатком). Для любых целых чисел a и , , существуют единственные целые числа и , 0 £ r < | b |, такие, что

. (1.1.1)

Доказательство существования.

1. . В этом случае q = r = 0.

2. .

(вычитаем из a b столько раз, чтобы получилось число 0 или число r < b), .

3. .

, .

4. .

.

5. .

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

Пусть a = bq ₁ + r ₁ и a = bq ₂ + r ₂. Вычтем из 1-го равенства 2-е:

0 = bq ₁ – bq ₂ + r ₁ – r ₂,

b (q ₂ – q ₁) = r ₁ – r ₂.

Пусть q ₁ ¹ q ₂, тогда | r ₁ – r ₂ | ³ | b |, но 0 £ r ₁, r ₂ < | b |, Þ | r ₁ – r ₂ | < | b |. Значит, q ₁ = q ₂, поэтому и r ₁ = r ₂.

Определение 1.1.1. В равенстве (1.1.1) называют остатком, а – частным (неполным частным при ) от деления a на .

Для нахождения частного и остатка можно использовать метод деления «уголком».

Дата добавления: 2014-01-07