Понятие отношения делимости

Определение. Число а делится на число в тогда и только тогда, когда существует такое число q, что а = в × q. а в ( q N 0) [а = вq].

Обозначают: а в. Читают: «число а кратно числу в», «число в – делитель числа а», «а кратно в».

Равенство а=вq называют формулой кратности числа а числу в.

Число а, кратное 2, называют четным. Общий вид четного числа: а = 2n, n N 0 .

Число, кратное 3 имеет формулу: а = 3n, n N 0 .

Определение. Отношение делимости на множестве N 0 N содержит те и только те пары чисел (а, в), у которых первая координата кратна второй. Обозначают: « ».

« » = {(а, в)| (а, в) N 0 N а в}.

Если отношение делимости обозначить , то N 0 N ={(а, в)| (а, в) N 0 N а=вq}.

Теорема. Делитель в данного числа а не превышает этого числа, то есть, если а в в а.

Доказательство. Так как а в, то ( q N 0) [а = вq] а – в=вq-в=в(q – 1), так как q N q 1.

Тогда в (q – 1) 0 в а. Из определения отношения делимости и равенства а = 1 × а, следует, что 1 является делителем для любого натурального числа.

Следствие. Множество делителей данного числа конечно.

Например, делители числа 18 является конечное множество: {1, 2, 3, 6, 9, 18}.

Свойства отношения делимости

1. Отношение делимости рефлексивно, то есть любое натуральное число делится само на себя: ( а N) [(а,а) ], то есть а: а = 1.

Доказательство. ( а N)[а = а × 1] по определению отношения делимости а: а.

2. Отношение делимости антисимметрично, то есть для различных чисел а и в из того, что а в, следует, что в не кратно а. ( а, в N 0 N)[а в а в ].

Доказательство. Допустим, что в а, тогда в а. Но по условию а в, так как а в.

Неравенства в а а в истины только в том случае, если а = в. пришли к противоречию с условием. Следовательно, допущение, что в а Л. Таким образом, отношение делимости антисимметрично.

3. Отношение делимости транзитивно. ( а,в,с N 0 N)[а в в с а с].

Доказательство. Если а в ( q N)[а = вq] (1) Из того, что в с ( t N)[в = сt] (2)

Подставим в = сt в равенство (1), получим: а = (сt)q = c(tq), t,q N tq N tq = р а = ср, р N. А это значит, что а с.

Признаки делимости. Делимость суммы, разности, произведения

Определение. Признаком делимости называется предложение, в котором доказывается как можно предсказать делимость одного числа на другое, не выполняя деления этих чисел.

Теорема (признак делимости суммы). Если числа а и в делится на число n, то их сумма делится на это число, ( а,в, n N 0 N)[а n в n (а + в) n].

Доказательство. Из того что а n в n (по определению отношения делимости)

а=nq 1 (1), q 1 N. в=nq 2 (2), q 2 N. Преобразуем сумму (а + в) к виду:

а + в = nq 1 + nq 2 = n (q 1 + q 2) = nq,q = q 1 + q 2 . а + в = nq.

Следовательно, по определению отношения делимости, что (а + в) n.

Теорема (признак делимости разности). Если числа а и в делятся на число n и а в, то их разность а – в делится на число n, то есть

( а,в,n N 0 N)[а n в n а в (а – в) n].

Теорема (признак делимости произведения). Если один из множителей произведения делится на число n, то и все произведение делится на число n.

( а,в,n N 0 N)[а n (ав) n].

Доказательство. Из того, что а n а = nq (1). Умножим обе части равенства (1) на в N, получим: ав = nqв (по ассоциативности умножения) ав = n(qв) = nt, где t = qв ав = nt. А это значит, что ав n (по определению отношения делимости). Таким образом, для делимости произведения на число достаточно чтобы на данное число делился хотя бы один из множителей этого произведения.

Теорема. Если в произведении ав множитель а делится на натуральное число m, а множитель в делится на натуральное число n, то ав делится на mn.

( а,в,m,n N)[а m в n ав mn].

Доказательство. Из того, что а m а = mq 1 , q 1 N; в n в = nq 2 , q 2 N

ав = mq 1 × nq 2 , = mn(q 1 × q 2) = mnq, q 1 × q 2 = q N. ав = mnq ав mn.

Теорема (признак делимости на 2). Для того, чтобы число х делилось на 2 необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр: 0, 2, 4, 6, 8.

Доказательство. Пусть число х записано в десятичной системе счисления, то есть:

х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 , где а n , a n –1 , …, а 1 – цифры, принимающие значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 и а n 0, а 0 – принимает значения 0, 2, 4, 6, 8.

Докажем, что число х 2. Так как 10 2, то любая степень числа 10 2. Десятичную запись числа х представим в виде: х = (а n 10 n + a n –1 10 n –1 + …+a 1 10) + a 0

I слагаемое II слагаемое

В этой сумме первое слагаемое по признаку делимости суммы делится на 2. Второе слагаемое а 0 2 (по условию). Следовательно, по признаку делимости суммы на число х делится на 2.

Обратно, если число х делится на 2, то его десятичная запись оканчивается цифрой 0, 2, 4, 6, 8.

Запишем число х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 в виде: а 0 = х – (а n 10 n + a n –1 10 n –1 + …+a 1 10).

В этой разности число х 2 (по условию), вычитаемое (а n 10 n + a n –1 10 n –1 + …+a 1 10) 2 (по признаку делимости суммы). Следовательно, по теореме о делимости разности а 0 2. Чтобы однозначное число а 0 делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

Признак делимости на 2. На 2 делятся те и только те числа, в разряде единиц которых содержится число, делящееся на 2 или на 2 делятся те и только те числа, десятичная запись которых оканчивается одной из цифр 0, 2, 4, 6, 8.

Теорема (признак делимости на 5). Для того, чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.

Лемма . ( n N) .

Доказательство. Так как 100 = 4 × 25, то по признаку делимости произведения

100 4. Тогда ( n N n > 1) 10 n = 100 × 10 n–2 и по признаку делимости произведения 10 n 4.

Теорема (признак делимости на 4). Натуральное число х делится на 4 тогда и только тогда, когда две последние цифры его десятичной записи образуют двузначное число, делящееся на 4.

Пусть х = а n 10 n + a n –1 10 n –1 + …+a 1 10 + a 0 и пусть десятичная запись двух последних цифр a 1 10 + a 0 выражает число , которое делится на 4.

Доказательство. Представим число х в виде суммы двух слагаемых:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0),

I слагаемое II слагаемое

где первое слагаемое, по доказанной выше Лемме, делится на 4, второе слагаемое делится на 4 по условию. Следовательно, согласно признака делимости суммы на число, число х делится на 4.

Обратно, если число х 4, то – двузначное число, образованное последними цифрами его десятичной записи, делится на 4.

По условию х 4. Докажем, что (а 1 10 + а 0) 4.

Доказательство. Десятичная запись числа х имеет вид:

х = а n 10 n + a n –1 10 n –1 + …+а 2 10 2 + a 1 10 + a 0 , представим число х в виде суммы двух слагаемых:

х = (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) + (а 1 10 + а 0) и запишем равенство в виде:

х – (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) = а 1 10 + а 0 , где х 4 (а n 10 n + a n –1 10 n –1 + …+a 2 10 2) 4 (по лемме).

Следовательно, по признаку делимости разности а 1 10 + а 0 4. выражение а 1 10 + а 0 = – есть запись двузначного числа, образованного последними цифрами записи числа х.

Признак делимости на 4. На 4 делятся те и только те числа, две последние цифры десятичной записи которых образуют число, делящееся на 4.

Теорема. Для того чтобы число х делилось на 25 необходимо и достаточно, чтобы на 25 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х.

Доказывается аналогично.

Признак делимости на 25. На 25 делятся те и только те числа, у которых две последние цифры в записи числа 00, 25, 50, 75.

Лемма. ( n N) [(10 n – 1) 9].

Докажем методом математической индукции.

1. Проверим справедливость утверждения для n = 1, И 3

Признак делимости на 3. На 3 делятся те и только те числа, сумма цифр которых делится на 3.

Определение. Пусть даны натуральные числа а и b. Говорят, что число а делится на число b, если существует такое натуральное число q, что а = bq.

В этом случае число b называютделителем числа а , а число а - кратным числа b.

Например , 24 делится на 8, так как существует такое q = 3, что 24 = 8×3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8.

В том случае, когда а делится на b, пишут: а M b. Эту запись часто читают и так: «а кратно b».

Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 - делитель, но 5 не является делителем числа 18. Если 18 делят на 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.

Из определения отношения делимости и равенства a = 1 × а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.

Теорема 1. Делитель b данного числа а не превышает этого числа, т. е. если а M b, то b £ а.

Доказательство. Так как а M b, то существует такое qÎ N, что а = bq и, значит, а - b = bq - b = b ×(q - 1). Поскольку qÎ N, то q ³ 1. . Тогда b ×(q - 1) ³ 0 и, следовательно, и b £ а.

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. Они образуют конечное множество {1,2,3,4,6,9,12,18,36}.

В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.

Определение. Простым числом называется такое натуральное число, большее 1, которое имеет только два делителя - единицу и само это число.

Например , 13 – простое, поскольку у него только два делителя: 1 и 13.

Определение. Составным числом называется такое натуральное число, которое имеет более двух делителей.

Так число 4 составное, у него три делителя: 1, 2 и 4. Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.

Чисел, кратных данному числу, можно назвать как угодно много, - их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, .... и все они могут быть получены по формуле а=4q, где q принимает значения 1, 2, 3,... .

Нам известно, что отношение делимости на множестве N обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимости, мы можем доказать эти и другие его свойства.

Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.

Доказательство. Для любого натурального а справедливо ра­венство а=а× 1. Так как 1 Î N то, по определению отношения дели­мости, аMа.

Теорема 3 . Отношение делимости антисимметрично, т.е. если а M b и а ¹ b, то .

Доказательство. Предположим противное, т. е. что bMа. Но тогда а£b, согласно теореме, рассмотренной выше.

По условию а M b и а ¹ b. Тогда, по той же теореме, b £ а.

Неравенства а £ b и b £ а.будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следовательно, наше предпо­ложение неверное и теорема доказана.

Теорема 4. Отношение делимости транзитивно, т.е. если а M b и b M с, то а M с.

Доказательство. Так как а M b, q, что а = b q , а так как bM с, то существует такое натуральное число р , что b = ср. Но тогда имеем: а = b q = (ср)q = с(рq). Число рq - натуральное. Значит, по определению отношения делимости, а. M с.

Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а 1, а 2 ,…а п делится на натуральное число b, то и их сумма а 1 + а 2 + … + а п делится на это число.

Например , не производя вычислений, можно сказать, что сумма 175 + 360 +915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Теорема 6 (признак делимости разности). Если числа а 1 и а 2 де­лятся на b и а 1 ³ а 2 , то их разность а 1 - а 2 делится на b.

Теорема 7 (признак делимости произведения). Если число а делится на b, то произведение вида ах, где х е N. делится на b.

Из теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b.

Например , произведение 24×976×305 делится на 12, так как на 12 делится множитель 24.

Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.

Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся сумма на число b не делится.

Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так как 34:2,376: 2,124: 2,но 125 не делится на 2.

Теорема 9. Если в произведении аb множитель а делится на натуральное число т, а множитель b делится на натуральное число п то а b делится на тп.

Справедливость этого утверждения вытекает из теоремы о делимости произведения.

Теорема 10. Если произведение ас делится на произведение bс, причем с - натуральное число, то и а делится на b.

2. Простые и составные числа

Простые числа играют большую роль в математике - по существу они являются «кирпичами», из которых строятся составные числа.

Это утверждается в теореме, называемой основной теоремой арифметики натуральных чисел, которая приводится без доказательства.

Теорема. Любое составное число можно единственным образом представить в виде произведения простых множителей.

Например , запись 110= 2×5×11 есть представление числа 110 в виде произведения простых множителей или разложение его на простые множители.

Два разложения числа на простые множители считают одинаковыми, если они отличаются друг от друга лишь порядком множителей. Поэтому представление числа 110 в виде произведения 2×5×11 или произведения 5×2×11 есть, по существу, одно и то же разложение числа 110 на простые множители.

Раскладывая числа на простые множители, используют признаки делимости на 2, 3, 5 и др. Напомним один из способов записи разложения чисел на простые множители. Разложим, например, на множители число 90. Число 90 делится на 2. Значит, 2 есть один из про­стых множителей в разложении числа 90. Разделим 90 на 2. Число 2 запишем справа от знака равенства, а частное 45 - под числом 90. Число 45 делим на простое число 3, получаем 15. Делим 15 на 3, получаем 5. Число 5 - простое, при делении его на 5 получаем 1. Разложение на множители закончено.

При разложении числа на простые множители произведение одинаковых множителей представляют в виде степени: 90=2×3 2 ×5; 60=2 2 × 3× 5; 72=2 3 ×3 2 . Такое разложение числа на простые множители называют каноническим.

Греческий математик - Евклид доказал, что множество простых чисел бесконечно.

Действительно, предположим, что множество простых чисел конечное и исчерпывается числами 2, 3, 5, 7, ...,р, где p - самое большое простое число. Перемножим все простые числа и их произведение обозначим через а. Прибавим к этому числу 1. Каким будет полученное число а + 1 - простым или составным?

Простым число а+1 быть не может, потому что оно больше само­го большого простого числа, а по предположению таких простых чисел не существует. Но составным оно тоже быть не может: если а+1 составное, то оно должно иметь хотя бы один простой делитель q. Так как число а = 2×3×5 ×...×р также делится на это простое число q, то и разность (а + 1) - а, т.е. число 1, делится на q, что невозможно.

Итак, число а не является ни простым, ни составным, но этого тоже не может быть - всякое число, отличное от 1, либо простое, либо составное. Следовательно, наше предположение о том, что множество простых чисел конечное и есть самое большое простое число, неверно, и значит, множество простых чисел бесконечное.

3. Признаки делимости

Рассмотренные в свойства отношения делимости позволяют доказать известные признаки делимости чисел, записанных в десятичной системе счисления, на 2, 3, 4, 5, 9.

Признаки делимости позволяют установить по записи числа делится ли оно на другое, не выполняя деления.

Теорема 11 (признак делимости на 2) . Для того чтобы число х делилось на 2, необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр 0, 2, 4, 6, 8.

Доказательство. Пусть число х записано в десятичной системе счисления, т.е. х=а п 10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0, где а п,а п-1 , …, а 1 принимают значения 0, 1,2, 3, 4, 5, 6, 7, 8, 9, а п ¹0 и а 0 принимает значе­ния 0,2,4,6,8. Докажем, что тогда х M 2.

Так как 10M2, то 10 2 M2, 10 3 M2, ..., 10 п M2 и, значит, а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10M2. По условию а 0 тоже делится на 2, и поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 2. Следовательно, согласно признаку делимости суммы, число х делится на 2.

Докажем обратное : если число х делится на 2, то его десятичная запись оканчивается одной из цифр 0, 2, 4, 6, 8.

Запишем равенство х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 в таком виде: а 0 =х-(а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10). Но тогда, по теореме о делимости разности, а 0 M2, поскольку хM2 и (а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10)M2. Чтобы однозначное число а 0 делилось на 2, оно должно принимать значения 0, 2, 4, 6, 8.

Теорема 12 (признак делимости на 5). Для того чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5.

Доказательство этого признака аналогично доказательству признака делимости на 2.

Теорема 13 (признак делимости на 4). Для того чтобы число х делилось на 4, необходимо и достаточно, чтобы на 4 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х.

Доказательство . Пусть число х записано в десятичной системе счисления, т.е. х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 и две последние цифры в этой записи образуют число, которое делится на 4. Докажем, что тогда хM4.

Так как 100M4, то (а п ×10 п +а п-1 ×10 п–1 +…+а 2 ×10 2)M4. По условию, а 1 ×10+а 0 (это и есть запись двузначного числа) также делится на 4. Поэтому число х можно рассматривать как сумму двух слагаемых, каждое из которых делится на 4. Следовательно, согласно признаку делимости суммы, и само число х делится на 4.

Докажем обратное , т.е. если число х делится на 4, то двузначное число, образованное последними цифрами его десятичной записи, тоже делится на 4.

Запишем равенство х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 в таком виде: а 1 ×10+а 0 =х-(а п ×10 п +а п-1 ×10 п–1 +…+а 2 ×10 2). Так как хM4 и (а п ×10 п +а п-1 ×10 п–1 +…+а 2 ×10 2), то по теореме о делимости разности (а 1 ×10+а 0)M4. Но выражение а 1 ×10+а 0 есть запись двузначного числа, образованного последними цифрами записи числа х.

Например , число 157872 делится на 4, так как последние две цифры в его записи образуют число 72, которое делится на 4. Число 987641 не делится на 4, так как последние две цифры в его записи образуют число 41, которое не делится на 4.

Теорема 14 (признак делимости на 9) . Для того чтобы число х делилось на 9, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилась на 9.

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

Докажем сначала, что числа вида 10 п -1 делятся на 9. Действительно,

10 п -1=(9×10 п-1 +10 п–1)-1=(9×10 п-1 +9×10 п-2 +10 п–2)-1=(9×10 п-1 +9×10 п-2 +...+10)-1=

9×10 п-1 +9×10 п-2 +...+9. Каждое слагаемое полученной суммы делится на 9, значит, и число 10 п -1 делится на 9.

Пусть число х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 и (а п +а п-1 +…+а 1 +а 0)M 9. Докажем, что тогда хM9.

Преобразуем сумму а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 , прибавив и вычтя из нее выражение а п +а п-1 +…+а 1 +а 0 и записав результат в таком виде:

х=(а п ×10 п -а п)+(а п-1 ×10 п–1 -а п-1)+...+(а 1 ×10-а 1)+(а 0 -а 0)+(а п +а п-1 +…+а 1 +а 0)= =а п (10 п-1 -1)+а п-1 (10 п-1 -1)+...+а 1 × (10 п-1 -1)+(а п +а п-1 +…+а 1 +а 0).

В последней сумме каждое слагаемое делится на 9:

а п (10 п-1 - 1)M9, так как (10 п-1 -1)M9,

а п-1 (10 п-1 -1)M9, так как (10 п-1 - 1)M9 и т.д.

(а п +а п-1 +…+а 1 +а 0)M 9 по условию.

Следовательно, хM9.

Докажем обратное , т.е. если хM9, то сумма цифр его десятичной записи делится на 9.

Равенство х=а п ×10 п +а п-1 ×10 п–1 +…+а 1 ×10+а 0 запишем в таком виде:

а п +а п-1 +…+а 1 +а 0 =х-(а п (10 п -1)+а п-1 (10 п–1 -1)+...+а 1 (10-1)).

Так как в правой части этого равенства и уменьшаемое, и вычитаемое кратны 9, то по теореме о делимости разности (а п + а п-1 + …+ а 1 + а 0)M9, т.е. сумма цифр десятичной записи числа х делится на 9, что и требовалось доказать.

Например, число 34578 делится на 9, так как сумма его цифр, равная 27 делится на 9. Число 130542 не делится 9, так как сумма его цифр, равная 15, не делится на 9.

Теорема 15 (признак делимости на 3). Для того чтобы число х делилось на 3, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилось на 3.

Доказательство этого утверждения аналогично доказательству признака делимости на 9.

Мы рассмотрели признаки делимости чисел на 2, 3, 4, 5, 9. Из школьного курса математики известен еще ряд других, например, на 10 и 25. Конечно, этого недостаточно, чтобы решать вопросы делимости. Существует общий признак делимости для чисел, записанных в любой позиционной системе счисления, открытый в XVII веке французским математиком Паскалем. Мы рассмотрим его для случая, когда осно­ванием системы счисления является число 10.

Теорема 16 (признак делимости Паскаля ). Число х = а п × 10 п + а п-1 × 10 п –1 + …+ а 1 × 10 + а 0 делится на число b тогда и только тогда, когда на b делится сумма а п × r п + а п-1 × r п –1 + …+ а 1 × r 1 + а 0 , где r 1 , r 2 ,…,r n - остатки от деле­ния на bразрядных единиц 10, 10 2 ,..., 10 n .

Используя этот признак, выведем, например, известный признак делимости на 3 в десятичной системе счисления.

Найдем остатки от деления разрядных единиц на 3:

10 =3×3+1(r 1 =1);

10 2 = 3×33 + 1 (r 2 = 1);

10 3 = 10 2 10= (3×33 + 1) × (3×3 + 1) =3q 3 + 1 (r 3 = 1).

На основании рассмотренных случаев можно предположить, что ("n Î N) 10 n =3q n +1. Убедиться в истинности этого утверждения можно, если воспользоваться методом математической индукции.

Таким образом, доказано, что число делится на 3 тогда и только тогда, когда сумма цифр его десятичной записи делится на 3.

Используя признак делимости Паскаля, можно доказать следующий признак делимости чисел на 11: для того чтобы число делилось на 11, необходимо и достаточно, чтобы разность между суммой его цифр, стоящих на нечетных местах, и суммой цифр, стоящих на четных местах, делилась на 11. Обычно при нахождении разности из большего числа вычитают меньшее.

Например, число 540309 делится на 11, так как (4 + 3 + 9) - (5 + 0 + 0) = 11, а 11: 11. Число 236 не делится на 11, поскольку (2 + 6) - 3 = 5, но 5 не кратно 11.

4. Наименьшее общее кратное и наибольший общий делитель

Рассмотрим известные из школьного курса математики понятия наименьшего общего кратного и наибольшего общего делителя натуральных чисел, сформулируем их основные свойства, опустив все доказательства.

Определение. Общим кратным натуральных чисел а и b называется число, которое кратно каждому из данных чисел.

Наименьшее число из всех общих кратных чисел а и b называется наименьшим общим кратным этих чисел.

Наименьшее общее кратное чисел а и b условимся обозначать К(а, b). Например, два числа 12 и 18 общими кратными являются: 36, 72, 108, 144, 180 и т.д. Число 36 - наименьшее общее кратное чисел 12 и 18. Можно записать: К(12,18) = 36.

Для наименьшего общего кратного справедливы следующие утверждения:

1. Наименьшее общее кратное чисел а и b всегда существует и является единственным.

2. Наименьшее общее кратное чисел а и b не меньше большего из данных чисел, т.е. если а > b, то К(а, b) ³ а.

3. Любое общее кратное чисел а и b делится на их наименьшее общее кратное.

Определение. Общим делителем натуральных чисел а и b называется число, которое является делителем каждого из данных чисел.

Наибольшее число из всех общих делителей чисел а и b называется наибольшим общим делителем данных чисел. Наибольший общий делитель чисел а и b условимся обозначать D(а, b).

Например , для чисел 12 и 18 общими делителями являются числа: 1,2,3,6. Число 6 - наибольший общий делитель чисел 12 и 18. Можно записать: D(12,8)=6.

Число 1 является общим делителем любых двух натуральных чисел а и b. Если у этих чисел нет иных общих делителей, то D(а, b) = 1, а числа а и b называются взаимно простыми.

Например, числа 14 и 15 - взаимно простые, так как D (14, 15) = 1.

Для наибольшего общего делителя справедливы следующие утверждения:

1. Наибольший общий делитель чисел а и b всегда существует и является единственным.

2. Наибольший общий делитель чисел а и b не превосходит меньшего из данных чисел, т.е. если а < b, то D (а, b) £ а.

3. Наибольший общий делитель чисел а и b делится на любой общий делитель этих чисел.

Наименьшее общее кратное чисел а и b и их наибольший общий делитель взаимосвязаны: произведение наименьшего общего кратного и наибольшего общего делителя чисел а и b равно произведению этих чисел, т.е.

К(а, b)×D(а,b)=а×b.

Из этого утверждения вытекают следующие следствия:

а) Наименьшее общее кратное двух взаимно простых чисел равно произведению этих чисел, т. е. D(а,b) = 1 ÞК(а,b)=а× b.

Например, чтобы найти наименьшее общее кратное чисел 14 и 15, достаточно их перемножить, так как D (14, 15) = 1.

б) Для того чтобы натуральное число а делилось на произведение взаимно простых чисел m и n, необходимо и достаточно, чтобы оно делилось и на m, и на n.

Это утверждение представляет собой признак делимости на числа, которые можно представить в виде произведения двух взаимно простых чисел.

Например, так как 6=2× 3 и D(2,3)=1, то получаем признак делимости на 6: для того чтобы натуральное число делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3.

Заметим, что данный признак можно применять многократно. Сформулируем, например, признак делимости на 60: для того чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось и на 4, и на 15. В свою очередь, число будет делиться на 15 тогда и только тогда, когда оно делится и на 3, и на 5. Обобщая, получаем следующий признак делимости на 60: для того чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось на 4, на 3 и на 5.

Определение. Пусть даны натуральные числа а и b. Гово­рят, что число а делится на число b, если существует та­кое натуральное число q, что a = bq.

В этом случае число b называют делителем числа а, а число а - кратным числа b.

Например, 24 делится на 8, так как существует такое q =3, что 24 = 8·3. Можно сказать иначе: 8 - это делитель числа 24, а 24 есть кратное числа 8. В том случае, когда а делится на b, пишут: а: . b. Эту запись »« читают и так: «а кратно b». Заметим, что понятие «делитель данного числа» следует отличать от понятия «делитель», обозначающего то число, на которое делят. Например, если 18 делят на 5, то число 5 -делитель, но 5 не является делителем числа 18. Если 18 делят 6, то в этом случае понятия «делитель» и «делитель данного числа» совпадают.

Из определения отношения делимости и равенства а = 1·а, справедливого для любого натурального а, вытекает, что 1 является делителем любого натурального числа.

Выясним, сколько вообще делителей может быть у натурального числа а. Сначала рассмотрим следующую теорему.

Теорема 1. Делитель b данного числа а не превышает этого числа, т.е. если

а: . b, то b < а.

Доказательство. Так как а: . b, то существует такое q Є N,что a = bq u, значит, a-b = bq – b= b·(q - 1). Поскольку q Є N,тоq≥ 1. Тогда b· (q - 1) ≥ 0 и, следовательно, b ≤ а.

Из данной теоремы следует, что множество делителей данного числа конечно. Назовем, например, все делители числа 36. образуют конечное множество {1,2,3,4,6,9,12,18,36}.

В зависимости от числа делителей среди натуральных чисел различают простые и составные числа.

Определение. Простым числом называется такое нату­ральное число, которое имеет только два делителя - единицу и само это число.

Например, число 13- простое, поскольку, у него только два делителя: 1 и 13.

Определение. Составным числом называется такое нату­ральное число, которое имеет более двух делителей.

Так число 4 составное, у него три делителя: 1,2 и 4.

Число 1 не является ни простым, ни составным числом в связи с тем, что оно имеет только один делитель.

Чисел, кратных данному числу, можно назвать как угодно много, - их бесконечное множество. Так, числа, кратные 4, образуют бесконечный ряд: 4, 8, 12, 16, 20, 24, …, и все они могут быть получены по формуле а = 4q, где q принимает значения 1, 2, 3,....

Нам известно, что отношение делимости обладает рядом свойств, в частности, оно рефлексивно, антисимметрично и транзитивно. Теперь, имея определение отношения делимо­сти, мы можем доказать эти и другие его свойства.

Теорема 2. Отношение делимости рефлексивно, т.е. любое натуральное число делится само на себя.

Доказательство. Для любого натурального а справед­ливо равенство а = а·1. Так как 1 Є N, то, по определению отношения делимости, а: . а.

Теорема 3. Отношение делимости антисимметрично, т.е. если а: . b и а ≠ b,

то b ⁞͞ a.

Доказательство. Предположим противное, т.е. что b⁞ a. Но тогда а ≤ b, согласно теореме, рассмотренной выше.

По условию и а ⁞ . b и а ≠ b. Тогда, по той же теореме, b ≤ а.

Неравенства а ≤ b и b ≤ а будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следова­тельно, наше предположение неверное и теорема доказана.

Теорема 4 . Отношение делимости транзитивно, т.е. если а⁞ b и b⁞ с, то а⁞ с.

Доказательство. Так как а: . b, то существует такое нату­ральное число q, что a = bq, а так как b⁞ с, то существует такое натуральное число р, что b = ср. Но тогда имеем: a = bq = (cp)q = c(pq)- Число pq - натуральное. Значит, по определе­нию отношения делимости,

а⁞ с.

Теорема 5 (признак делимости суммы). Если каждое из натуральных чисел а 1 , а 2 , ...,а п делится на натуральное число b, то и их сумма a 1 + а 2 + ... + а n делится на это число.

Доказательство. Так как а 1 ⁞ b, то существует такое на­туральное число q 1 , что а 1 =bq 1 . Так как а 2 ⁞ b, то существует такое натуральное число q 2 , что а 2 = bq 2 . Продолжая рассуж­дения, получим, что если а n: . b, то существует такое натуральное число q n , что а п = bq n . Эти равенства позволяют преобразовать сумму а 1 + а 2 + ... +а п в сумму вида bq 1 + bq 2 + ... + bq n . Вынесем за скобки общий множитель b, а получившееся в скобках натуральное число q 1 + q 2 + ... + q n обозначим буквой q. Тогда a 1 + a 2 + ... + a n = b(q 1 + q 2 +... + q n) = bq, т.е. сумма а 1 + а 2 +… + а п оказалась представленной в виде произведения числа b и некоторого натурального числа q. А это значит, что сумма а 1 + а 2 +… + а п делится на b, что и требовалось доказать.

Например, не производя вычислений, можно сказать, что 175 + 360 + 915 делится на 5, так как на 5 делится каждое слагаемое этой суммы.

Теорема 6 (признак делимости разности). Если числа а 1 и а 2 делятся на b и а 1 ≥ а 2 , то их разность а 1 - а 2 делится на b.

Доказательство этой теоремы аналогично доказательству признака делимости суммы.

Теорема 7 (признак делимости произведения). Если число а делится на b, то произведениe вида ах, где х Є N, делитcя на b.

Доказательство. Так как а: . b, то существует такое натуральное число q, что a = bq. Умножим обе части этого равенства на натуральное число х. Тогда ах=(bq)x, откуда на основании свойства ассоциативности умножения (bq)x = b(qx)и, значит, ax = b(qx), где qx - натуральное число. Согласно определению отношения делимости, ax: . b, что и требовалось доказать.

Из доказанной теоремы следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b. Например, произведение 24·976·305 делится на 12, так как на 12 делится множитель 24.

Рассмотрим еще три теоремы, связанные с делимостью суммы и произведения, которые часто используются при решении задач на делимость.

Теорема 8. Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся cумма на число b не делится.

Доказательство. Пусть s = а 1 + а г + ... + а п +" с и известно, что а 1: . B, а 2: . B,

а 3: . b, … а n: . b, но с: . b. Докажем, что тогда s: . b

Предположим противное, т.е. Пусть s: . b. Преобразуем сумму s к виду с = s- (а 1 + а 2 +… + а n ). Так как s: . b по предположению, (а 1 + а 2 +… + а n ) : . b согласно признаку делимости суммы, то по теореме делимости разности с: .b

Пришли к противоречию с тем, что дано. Следовательно, s: . b.

Например, сумма 34 + 125 + 376 + 1024 на 2 не делится, так 34: .2,376: .2,124: .2, но 125 не делится на 2.

Теорема 9 . Если в произведении ab множитель a делится на натуральное число т, а множитель b делится на натуральное число n,то ab делится на mn.

Справедливость этого утверждения вытекает из теоремы о делимости произведения.

Теорема 10. Если произведение ас делится на произведе­ние bс, причем с - натуральное число, то и а делится на b.

Доказательство. Так как ас делится на bc, то существует такое натуральное число q, что ас = (bc)q, откуда ас = (bq)c и, следовательно, а = bq, т.е. а : .b.

Упражнения

1. Объясните, почему число 15 является делителем числа 60 и не является делителем числа 70.

2. Постройте граф отношения «быть делителем данного числа», заданного на множестве Х = {2, 6,. 12, 18, 24}. Как от­ражены на этом графе свойства данного отношения?

3. Известно, что число 24 - делитель числа 96, а число 96 -делитель числа 672. Докажите, что число 24 делитель числа 672, не выполняя деления.

4. Запишите множество делителей числа.

а) 24; 6)13; в) 1.

5 .На множестве X ={1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11; 12} задано отношение «иметь одно и то же число делителей». Является ли оно отношением эквивалентности?

6 .Постройте умозаключение, доказывающее, что:

а) число 19 является простым;

б) число 22 является составным.

7. Докажите или опровергните следующие утверждения:

а) Если сумма двух слагаемых делится на некоторое число, то и каждое слагаемое делится на это число.

б) Если одно из слагаемых суммы не делится на некоторое число, то и сумма не делится на это число.

в) Если ни одно слагаемое не делится на некоторое число, то и сумма не делится на это число.

г) Если одно из слагаемых суммы делится на некоторое число, а другое не делится на это число, то и сумма не делится на это число.

8. Верно ли, что:

а) а: . ти b: . n =>ab: .mn

б) а: .п и b: .n => ab: .n;

в) ab: .n => а: .п или b: .n.

Отношение делимости и его свойства Определение Пусть а и b N. Число а делится на число b, если существует такое натуральное число q, что а = bq а b q N , что а = bq В этом случае число b называют делителем числа а, а число а – кратным числа b 24 8, т. к. 3 N , что 24 = 8 3

Различают понятия «b делитель числа а» и «b – делитель» В выражении « 25: 8» число 8 делитель (как компонент деления), а в выражении « 24: 8» число 8 делитель числа 24 Теорема 1 1 является делителем любого натурального числа т. к. для а N а = 1· а Теорема 2 Если а b, то b а

Доказательство Так как а b, то q N, что а = bq а – b = bq – b = b · (q – 1). Поскольку а N, то q 1. Тогда b · (q – 1) 0, т. е. разность а – b 0 b а Из Теоремы 2 следует: Множество делителей данного числа а конечно – все делители меньше числа b Все делители числа 36 образуют конечное множество {1, 2, 3, 4, 6, 9, 12, 18, 36}

Свойства отношения делимости Теорема 3 (а N) а а, т. е. отношение делимости рефлексивно Доказательство (а N) а = а · 1. Так как 1 N делимости, а а

Теорема 4 (а b и а b) b а, т. е. отношение делимости антисимметрично Доказательство (от противного) Пусть неверно, что b а а b (по теореме 2) По условию а b и а b b а (по теореме 2) Неравенства а b и b а будут справедливы лишь тогда, когда а = b, что противоречит условию теоремы. Следовательно, наше предположение неверно

Теорема 5 а b и b с а с, т. е. отношение делимости транзитивно Доказательство Так как а b q N, что а = bq Так как b с р N, что b = ср а = bq = (ср)q = c(pq). Число pq N. Значит, по определению отношения делимости, а с

Теорема 6 (признак делимости суммы) Если каждое из натуральных чисел а 1, а 2, . . . , аn делится на натуральное число b, то и их сумма а 1 + а 2 +. . . + аn делится на это число Доказательство Так как а 1 b, то q 1 N, что а 1= b q 1 Так как а 2 b, то q 2 N, что а 2= b q 2 ……………………. Так как аn b, то qn N, что аn= b qn

а 1 + а 2 +. . . + аn = b (q 1 + q 2 +. . . + qn) = bq q = q 1 + q 2 +. . . + qn , т. е. q N т. е. сумма а 1 + а 2 +. . . + аn есть произведение числа b и натурального числа q. Следовательно, сумма а 1 + а 2 +. . . + аn делится на b Пример Сумма (175 + 360 + 915) 5, т. к. 175 5 и 360 5 и 915 5

Теорема 7 (признак делимости разности) Если а 1 b, а 2 b и а 1 > а 2, то (а 1 – а 2) b Доказательство аналогично доказательству теоремы 6

Теорема 8 (признак делимости произведения) Если а b, то ах b, где х N Доказательство Так как а b, то q N, что а = bq на х ах = (bq)x = b(qx), т. е. ах = b(qx), где qx N по определению отношения делимости ax b

Из теоремы 8 следует, что если один из множителей произведения делится на натуральное число b, то и все произведение делится на b Пример Произведение (24 · 976 · 305) 12, так как 24 12 Теорема 9 Если в сумме одно слагаемое не делится на число b, а все остальные слагаемые делятся на число b, то вся сумма на число b не делится

Пример Сумма (34 + 125 + 376 + 1024) 2, так как 34 2, 376 2, 124 2, но 125 2 Теорема 10 Если в произведении ab множитель а делится на натуральное число m, а множитель b делится на натуральное число n, то ab делится на mn Доказательство основано на теореме 8

Теорема 11 Если ас bс и с N, то а b Доказательство Так как ас bс, то q N такое, что ас = (bc)q ас = (bq)c, следовательно, а = bq, т. е. a b

Признаки делимости Теорема 12 (признак делимости на 2) Для того чтобы число х делилось на 2, необходимо и достаточно, чтобы его десятичная запись оканчивалась одной из цифр 0, 2, 4, 6, 8 Доказательство 1) Пусть число х записано в десятичной системе счисления: х = аn · 10 n + аn-1 · 10 n – 1 +. . . + а 1 · 10 + а 0 , где аn, аn-1, . . . а 1 принимают значения 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, аn 0 и а 0 принимает значения 0, 2, 4, 6, 8

х = аn· 10 n+аn-1· 10 n -1+. . . + а 1· 10 + а 0 = = (аn· 10 n-1 + аn-1· 10 n -2+. . . + а 1) · 10 + а 0 делится на 2, т. к. 10 2 а 0 тоже делится на 2, т. к. по условию заканчивается на 0, 2, 4, 6 или 8

2) Докажем, что, если число х 2, то а 0 приминимает значения 0, 2, 4, 6 или 8 х = аn· 10 n + аn-1· 10 n -1 +. . . + а 1· 10 + а 0 = х – (аn· 10 n + аn-1· 10 n -1+. . . + а 1· 10) делится на 2, т. к. 10 2 Число х 2 по условию а 0 2

Теорема 13 (признак делимости на 5) Для того чтобы число х делилось на 5, необходимо и достаточно, чтобы его десятичная запись оканчивалась цифрой 0 или 5 Доказательство аналогично признака делимости на 2 доказательству

Теорема 14 (признак делимости на 4) Для того чтобы число х делилось на 4, необходимо и достаточно, чтобы на 4 делилось двузначное число, образованное последними двумя цифрами десятичной записи числа х Доказательство 1) х = аn· 10 n+аn-1· 10 n -1+. . . а 2 102 + а 1· 10 + а 0 = = (аn· 10 n-2 + аn-1· 10 n -3+. . . + а 2) · 102 + а 1 10 + а 0 делится на 4, т. к. 102 4 делится на 4 по условию

2) Докажем, что, если число х 4, то (а 1 10 + а 0) образует двузначное число, которое делится на 4 х = аn· 10 n + аn-1· 10 n -1+. . . + а 2 10 2 + а 1· 10 + а 0 = х – (аn· 10 n + аn-1· 10 n -1+. . . + а 2 10 2) делится на 4, т. к. 102 4 Число х 4 по условию (а 1· 10 + а 0) 4

Пример 1) Число 1 5 7 8 7 2 4 72 4 2) Число 9 8 7 6 4 1 4 41 4

Теорема 15 (признак делимости на 9) Для того чтобы число х делилось на 9, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилось на 9 Доказательство 1) Докажем, что (10 n – 1) 9

10 n – 1 = 10 10 n-1 – 1 = (9 + 1) 10 n-1 – 1 = = (9 · 10 n - 1 + 10 n - 1) – 1 = = (9 · 10 n - 1 + 9 · 10 n - 2 + 10 n - 2) – 1 = = (9 · 10 n-1 + 9 · 10 n-2 +. . . + 10) – 1 = = 9 · 10 n-1 + 9 · 10 n-2 + 10 n-2 +. . . + 9 = 9 · (10 n-1 + 10 n-2 + 10 n-2 +. . . + 1) делится на 9 (10 n – 1) 9

2) К десятичной записи числа х: х = аn · 10 n + аn-1 · 10 n – 1 +. . . + а 1 · 10 + а 0 прибавим и вычтем выражение (аn+ аn-1+. . . + а 0) Получим: х = (аn· 10 n – аn) + (аn-1 · 10 n-1– аn-1) +. . . + (а 1· 10 – а 1) + (а 0 – а 0) + (аn +аn-1 +. . . + а 1 + а 0) = делится на 9, т. к. каждое слагаемое содержит множитель (10 n – 1) = аn· (10 n – 1) + аn-1· (10 n-1 – 1)+. . . + а 1· (10 – 1) + + (аn + аn-1 +. . . + а 1 + а 0) делится на 9 по условию

3) Докажем, что, если число х 9, то (аn+ аn-1+. . . + а 0) 9 Равенство запишем в виде: х = (аn· 10 n – аn) + (аn-1 · 10 n-1– аn-1) +. . . + (а 1· 10 – а 1) + + (а 0 – а 0) + (аn +аn-1 +. . . + а 1 + а 0) аn +аn-1 +. . . + а 1 + а 0 = = х – (аn· (10 n – 1) + аn-1 ·(10 n-1 – 1) +. . . + а 1· (10 – 1)) В правой части этого равенства уменьшаемое и вычитаемое кратны 9, то по теореме о делимости разности (аn +аn-1 +. . . + а 1 + а 0) 9

Пример Число 34578 9, так как 3 + 4 + 5 + 7 + 8 = 27, 27 9 Число 130542 не делится 9, так как 1 + 3 + 0 + 5 + 4 + 2 = 15, 15 не делится на 9

Теорема 16 (признак делимости на 3) Для того чтобы число х делилось на 3, необходимо и достаточно, чтобы сумма цифр его десятичной записи делилось на 3 Доказательство аналогично доказательству признака делимости на 9

Наименьшее общее кратное и общий делитель наибольший Определение Общим кратным натуральных чисел а и b называется число, которое кратно каждому из данных чисел Наименьшее число из всех общих кратных чисел а и b называется наименьшим общим кратным этих чисел Наименьшее общее кратное чисел а обозначают К(а, b) и b

Общими кратными чисел 12 и 18 являются: 36, 72, 108, 144, 180 … Число 36 – наименьшее общее кратное чисел 12 и 18 Пишут: К(12, 18) = 36 Свойства К(а, b) 1. Наименьшее общее кратное чисел а и b всегда существует и является единственным 2. Наименьшее общее кратное чисел а и b не меньше большего из данных чисел, т. е. если а > b, то К(а, b) > а 3. Любое общее кратное чисел а и b делится на их наименьшее общее кратное

Определение Общим делителем натуральных чисел а и b называется число, которое является делителем каждого из данных чисел Наибольшее число из всех общих делителей чисел а и b называется наибольшим общим делителем данных чисел. Наибольший общий делитель чисел а и b обозначают D(a, b) Общими делителями чисел 12 и 18 являются числа: 1, 2, 3, 6 Число 6 – наибольший общий делитель чисел 12 и 18 Пишут: D(12, 18) = 6

Число 1 является общим делителем любых двух натуральных чисел а и b Определение D(a, b) = 1, то числа а и b называются взаимно простыми Пример Числа 14 и 15 – взаимно простые, так как D(14, 15) = 1

Свойства D (а, b) 1. Наибольший общий делитель чисел а и b всегда существует и является единственным 2. Наибольший общий делитель чисел а и b не превосходит меньшего из данных чисел, т. е. если а

Произведение наименьшего общего кратного и наибольшего общего делителя чисел а и b равно произведению этих чисел, т. е. К(a, b) · D(a, b) = а · b Следствия 1) Наименьшее общее кратное двух взаимно простых чисел равно произведению этих чисел, т. е. D(a, b) = 1 K(a, b) = a · b Например, К(14, 15) = 14 15, так как D (14, 15) = 1

2) Признак делимости на составное число: Для того чтобы натуральное число а делилось на произведение взаимно простых чисел m и n, необходимо и достаточно, чтобы оно делилось и на m, и на n Пример 6 = 2 · 3 и D(2, 3) = 1, то получаем признак делимости на 6: для того, чтобы натуральное число делилось на 6, необходимо и достаточно, чтобы оно делилось на 2 и на 3 Данный признак можно применять многократно

Задача Сформулируйте признак делимости на 60 Для того, чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось и на 4, и на 15, где D(4, 15) = 1. В свою очередь, число будет делиться на 15 тогда и только тогда, когда оно делится и на 3, и на 5, где D(3, 5) = 1 Таким образом признак делимости на 60: Для того, чтобы число делилось на 60, необходимо и достаточно, чтобы оно делилось на 4, на 3 и на 5

3) Частные, получаемые при делении двух данных чисел на их наибольший общий делитель, являются взаимно простыми числами Например, проверим, является ли число 12 наибольшим общим делителем чисел 24 и 36. Для этого разделим 24 и 36 на 12. Получим соответственно числа 2 и 3, где D (2, 3) = 1, т. е. 2 и 3 являются взаимно простыми. Следовательно, D(24, 36) = 12

Простые и составные числа Определение Простыми называются числа, которые делятся только на себя и на единицу Определение Составными называются числа, которые имеют более двух делителей Единица не относится ни к простым, ни к составным числам Числа 2, 5, 17, 61 и т. д. – простые, числа 4, 25, 102 и т. д. – составные

Свойства простых чисел 1. Если простое число p делится на некоторое натуральное число n, где n ≠ 1, то оно совпадает с n Действительно, если p ≠ n, то число р имеет три делителя: 1, n и p, а тогда оно не простое 2. Если p и q – простые числа и р ≠ q, то p не делится на q Если p – простое число, то оно имеет только два делителя: 1 и р. По условию q тоже простое, значит q ≠ 1 и q ≠ р Следовательно, q не является делителем числа p Числа 17 и 11 – простые, значит 17 не делится на 11

3. Если натуральное число a не делится на простое число p, то а и p взаимно просты, т. е. D (а, р) = 1 Например, 25 не делится на 7, значит 25 и 7 – взаимно просты 4. Если произведение двух натуральных чисел а и b делится на простое число p, то хотя бы одно из них делится на p Например, 25 39 = 975. Число 975 делится на 3, т. к. 9 + 7 + 5 = 21. Но число 25 не делится на 3, следовательно, 39 делится на 3

5. Если натуральное число больше 1, то оно имеет хотя бы один простой делитель Действительно, все простые числа имеют простые делители – сами эти числа, составные числа можно раскладывать на множители до тех пор, пока они не станут простыми числами Например, 240 > 1, значит имеет хотя бы один простой делитель, это число 2 (или 5)

6. Наименьший простой делитель составного числа а не превосходит Доказательство Пусть а – составное число, а р – его наименьший простой делитель. Тогда а = рb. При этом р b, т. к. иначе простой делитель числа b был бы меньше, чем р, а тогда а имело бы простые делители, меньшие чем р. Умножим обе части неравенства на р. Получим, р2 рb рb = а. Поэтому, р2 а, т. е. р

Теорема – Основная теорема арифметики Любое составное число можно единственным образом представить в виде произведения простых множителей где а 1, а 2, а 3, …, аk – простые числа, n 1, n 2, n 3, … , nk – показатели, с которыми входят простые числа в разложение числа х Такое разложение числа на простые множители называют каноническим

Пример 110 = 2 · 5 · 11 – произведение простых множителей есть разложение числа 110 на простые множители Два разложения числа на простые множители считают одинаковыми, если они отличаются друг от друга лишь порядком множителей 110 = 2 · 5 · 11 = 5 · 11 · 2 - одно и то же разложение

Способ разложения числа на простые множители 90 2 45 3 15 3 5 5 только простые числа 1 Таким образом, 90 = 2 · 3 · 5 · 1 = 2 · 32 · 5 60 = 22 · 3· 5; 72 = 23 · 32

Решето Эратосфена Эратосфеном (III в. до н. э.) был придуман способ получения простых чисел, не превышающих натурального числа а (решето Эратосфена) Найдем все простые числа до 50

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

Бесконечность множества простых чисел Теорема, доказанная Евклидом Множество простых чисел бесконечно Доказательство Пусть множество простых чисел конечно и состоит из чисел: 2, 3, 5, 7, . . . , p, где р – наибольшее простое число. Найдем произведение всех простых чисел 2 3 5 7 . . . p = а. Прибавим к а единицу. Число а + 1 простым не является, т. к. а + 1 > р наибольшего простого числа (по предположению)

Пусть а + 1 – составное число (а + 1) должно иметь хотя бы один простой делитель q р. Так как число а = 2 · 3 · 5 · р также делится на это простое число q, то и разность (а + 1) – а делится на q, т. е. число 1, делится на q, что невозможно Итак, число а не является ни простым, ни составным. Но этого тоже не может быть – всякое число, отличное от 1, либо простое, либо составное. Следовательно, предложение о том, что множество простых чисел конечное и есть самое большое простое число, неверно, и значит, множество простых чисел бесконечное

Способы нахождения наибольшего общего делителя и наименьшего общего кратного чисел 1 способ Чтобы найти НОД двух чисел, можно перечислить все их общие делители и выбрать из них наибольший Пример Даны числа 120 и 486 Делители числа 120: 1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120 Делители числа 486: 1, 2, 3, 6, 9, 27, 54, 81, 162, 243, 486 Общие делители: 1, 2, 3, 6 Наибольшим общим делителем является число 6

Чтобы найти НОК двух чисел, можно перечислить некоторые их общие кратные и выбрать из них наименьший Пример Даны числа 60 и 48 Кратные числа 60: 60, 120, 180, 240, 300, 360, 420, 480, 540, . . . Кратные числа 48: 48, 96, 144, 192, 240, 288, 336, 384, 432, 480, . . . Общие кратные чисел 60 и 48: 240, 480, . . . Наименьшим общим кратным является число 240

2 способ – основан на разложении данных чисел на простые множители Алгоритм нахождения наибольшего общего делителя данных чисел: 1) представить каждое данное число в каноническом виде; 2) образовать произведение общих для всех данных чисел простых множителей, каждый с наименьшим показателем, с каким он входит во все разложения данных чисел; 3) найти значение этого произведения – оно и будет наибольшим общим делителем данных чисел

Пример Даны два числа 3600 и 288 Каноническое разложение этих чисел: 3600 = 24 32 52; D(3600, 288) = 24 32 = 144 288 = 25 32

Алгоритм нахождения наименьшего общего кратного данных чисел: 1) представить каждое данное число в каноническом виде; 2) образовать произведение всех простых множителей, находящихся в разложениях данных чисел, каждый с наибольшим показателем, с каким он входит во все разложения данных чисел; 3) найти значение этого произведения – оно и будет наименьшим общим кратным данных чисел

Пример Даны два числа 3600 и 288 Каноническое разложение этих чисел: 3600 = 24 32 52; 288 = 25 32 K(3600, 288) = 25 32 52 = 7200

3 способ – алгоритм Евклида Алгоритм Евклида основан на следующих утверждениях: 1. Если а делится на b, то D(a, b) = b 2. Если a = bq + r и r

Src="https://present5.com/presentation/3/71306524_41475257.pdf-img/71306524_41475257.pdf-55.jpg" alt="Пусть а > b Если а делится на b, то D(a, b) = b"> Пусть а > b Если а делится на b, то D(a, b) = b Если при делении а на b, получается остаток r, то а = bq + r и D(a, b) = D(b, r) Найдем D(b, r) Если b делится на r, то D(b, r) = r и тогда D(a, b) = r Если при делении b на r получается остаток r 1, то b = rq 1 + r 1, и тогда D(r, r 1) = D(b, r) = D(a, b) Найдем D(r, r 1)

Продолжая описанный процесс, получаем все меньшие и меньшие остатки. В результате получим остаток, на который будет делиться предыдущий остаток. Этот наименьший, отличный от нуля, остаток и будет наибольшим общим делителем чисел а и b Найти НОК и НОД чисел можно по формуле: К(a, b) · D(a, b) = а · b К(а, b) = а · b: D(a, b) = а · b: К(а, b)

Пример Найдите по алгоритму Евклида наибольший общий делитель чисел 2585 и 7975 = 2585 3 + 220 2585 = 220 11 + 165 220 = 165 1 + 55 165 = 55 3 + 0 Значит, D(7975, 2585) = 55, К(7975, 2585) = = (7975 2585) : 55 = = 20615375: 55 = 374825

7975 7555 2585 220 385 220 165 165 0 55 3 165 1 220 11 2585 3

Говорят, что целое число a делится на целое число b, отличное от 0, если такое целое число с, определенное однозначно, что a=b*c.

Свойства: евклид лемма арифметика позиционный

• 1) Отношение делимости рефлексивно, т.е. . Действительно, число 1, а=а*1
• 2) Отношение делимости транзитивно, т.е. если

Из этого следует, что a=(c*k)*t=c*(k*t)=c*m

А это значит, что ас

• 3) Если аb, то (-a)b, (-a)(-b), a(-b)
• 4) Если ac и bc, то (ab)c

a=c*t, b=c*k (ab)=c*tc*k=c*(tk)(ab)c

НО: обратное утверждение неверно.

• 5) Если ab и cZ (произвольное число), то (a*c)b
• 6) Если каждое из чисел a1, a2…an делится на b, то (r1a1+…+rnan)b, где r1,…,rnZ
• 7) Если ac, b неc, то (a+b)нес

Пусть (a+b)=t и tc, t-a=b это противоречит условию.

• 8) 0на любое число, 0
• 9) Всякое целое число1, т.к. всякое число можно записать в виде а=1*а
• 10) На 0 делить нельзя: а=0*с, если а0, то это равенство неверно; если а=0, то имеем 0=0*с, сZ - в этом случае нарушается условие единственности определения с.
• 11) Если ab,то. a=b*c, где b,cZ

Теорема о делении с остатком

Разделить целое число а на целое число b0, это значит найти такие целые числа q и r, что a=bq+r, 0

Теорема: в кольце целых чисел всегда возможно выполнение деления с остатком и причем единственным образом.

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

1) Существование:

Рассмотрим целые числа кратные b. Это числа -2b,-b,b,2b… и пусть bq-последнее кратное b, не превышающее число а, тогда оно является наибольшим среди записанных кратных. В этом случае b(q+1)>a. Получили:

bqa

Пусть a-bq=r. Тогда получим: a=bq+r, причем 0r<

Это доказательство проходит для случая b>0.

Теперь пусть b<0,тогда (-b)>0.

Тогда a=(-b)*q+r, a=b*(-q)+r, где 0r<-b, -b=, где b<0, 0r<

Таким образом, деление с остатком возможно при любых а и b0

2) Единственность:

Предположим, что это не так:

a=bq1+r1 и a=bq2+r2;

b(q1-q2)=r2-r1; где 0r1,r2<;

Где 0r2-r1<, r2>r1.

Равенство возможно, если, =>q1=q2, r1=r2.

Следовательно, деление с остатком однозначно: q-неполное частное, r-остаток.