Основы теории делимости чисел
Делимость целых чисел Рассмотрим множество целых чисел Z. Операция деления выполняется не для всех пар чисел из Z. Определение. Число а∈ Z делится на число b∈Z (b≠0), если существует такое число q∈Z, что a=bq. Замечание. Вместо выражения «а делится на b» очень часто используется фраза «число b делит число а» и при этом применяется запись . a|b Если а делится на b, то b называется делителем а, само а называется кратным числа b. Число q называется частным от деления а на b. Число 0 делится на любое b≠0. Если a≠0, то, очевидно, что множество всех делителей а конечно. Рассмотрим простейшие свойства делимости целых чисел. 1. Если с│b и b│a, то с│а. 2. Если m=a+b, d│a и d│a то d│b. Замечание. Аналогично доказывается, что если m=a1+a2+…+an-1+an и d делит числа m, a1, a2, … an-1, то d│an . Определение. Общим делителем чисел a1, a2, … an∈Z называется число d∈Z, являющееся делителем каждого из этих чисел. Общий делитель данных чисел называется их наибольшим общим делителем, если он делится на всякий общий делитель этих чисел. 3. Если a, b, c ∈Z, НОД(a,b)=1 и b|ac, то b│c. 4. Если b∈Z взаимно просто с каждым из a1, a2, … an∈Z , то b взаимно просто с их произведением a1*a2*…*an.
Slaidy.com
