- •1.2. Наибольший общий делитель н наименьшее общее кратное
- •1.3. Вычисление наибольшего общего делителя
- •1.3.1. Алгоритм Евклида
- •1.4. Простые числа
- •1.4.2. Распределение простых чисел
- •Глава 2 сравнения с одним неизвестным
- •2.1. Отношение сравнимости
- •2.2. Решение сравнений
- •2.2.1 Сравнения первой степени
- •2.2.2. Китайская теорема об остатках
- •2.2.3. Сравнения произвольной степени по простому модулю
- •2.3. Сравнения второй степени
- •2.3.1. Символы Лежандра и Якоби
- •Решение сравнений для случаев простого модуля.
- •Случаи составного модуля
Определение 1. Множество натуральных чисел N определяется с использованием аксиом Пеана
- последующее для
Если некоторое подмножество является таким, что
Сложение:
должны выполняться законы:
a+1=
(a+b)+c=a+(b+c) – ассоциативность
a+b=b+a – коммутативность
Если a+b=a+c, то b=c
Умножение:
можно единственным образом сопоставить им произведение
a*b=(….(a+a)+…+a) - b раз
a*1=a
a*=ab+a
(ab)c=a(bc)
ab=ba
(a+b)c=ac+bc
Если ab=ac, то b=с
выполняется 1 из 3 транзитивных отношений: a>b, a<b, a=b
Определение 2. Множество Z целых чисел определяется как объединение множеств N, отрицательных N и нуля
Определение 3. Пусть над некоторым множеством R произвольной природы определены операции сложения и умножения. Множество R называется кольцом, если выполняются следующие условия:
a+b=b+a
Определение 4. Если в кольце R умножение коммутативно (ab=ba), то кольцо R называется коммутативным
Определение 5. Если в кольце R умножение ассоциативно( (ab)c=a(bc)), то кольцо R называется ассоциативным
Определение 6. Если в кольце R существует единичный элемент e, такой что ae=ea=a, то R называется кольцом с единицей
Определение 7. Если в ассоциативном, коммутативном кольце R с единицей
то кольцо называется полем
Говорят, что целое число a делится нацело на целое число b>0, если существует целое число c, такое что a=bc. Число а называют кратным числа b, число b — делителем числа а, число с — частным от деления а на b.
Свойства деления:
Нуль делится на любое целое число
Если a1 делится на b, a2 делится на b, то а1 ± а1 делится на b
Если a1 ± a2 делится на b и а1 делится на и, то a2 делится на b
Любое целое число делится на 1
Если a делится на b и b делится на c, то a делится на c
Если 1 делится на a, то a=±1
Определение 1.5. Пусть числа а и b целые и b≠ 0. Разделить а на b с остатком — значит представить а в виде a=qb + r, где q,rZ и 0<r<|b|. Число q называется неполным частным, число r — остатком от деления а на b.
Теорема 1.1 (о делении с остатком). Для любых a,bZ, b≠0, существует единственная пара таких чисел q,r Z, что a = qb + r; 0<r<|b|.
Доказательство. Сначала докажем теорему для случая а ≥0, b > О,
N = {nN }.
Множество N «непусто» поскольку 0 Кроме того, для любого п Nвыполняется неравенство п≤ nb, а значит, п ≤ а. Таким образом, вес элементы множества N ограничены сверху числом а, и в множестве N существует наибольший элемент q. Но тогда qb ≤ а < (q + 1)b. Обозначим r = a-qb,тогда получаем требуемое неравенство для r:
0≤r = a-qb<(q + 1)b-qb = b.
Теперь найдем требуемую пару чисел q и r для а < 0, b >0. Согласно предыдущему случаю, для -а > 0 и b существуют целые числа такие, что -а = b + . При = 0 полагаемq = -,r = 0. При > 0 полагаем
q= -(q' + l), r=b-
При b < 0 нужно разделить с остатком а на |b| согласно одному из рассмотренных случаев: а = q'|b| + r, а затем положить q = -
Единственность докажем от противного. Пусть существуют две такие пары целых чисел q1,r1,q2,r2 что
a=q1b + r1 =q2b + r2,
где 0≤r1 ,r2 < |b|. Тогда
(q1-q2)b=-(r1-r2)
откуда следует
|q1-q2||b|=|r1-r2|<|b| , 0≤|q1-q2|<1
а так как числа q1 и q2 целые, то |q1-q2|=0 , q1=q2, r2=r1.
1.2. Наибольший общий делитель н наименьшее общее кратное
Определение 1.6. Целое число d≠0 называется наибольший общим делителем целых чисел а1, а2, ...,ак (обозначается d = НОД(а1, а2, .... ak)), если выполняются следующие условия:
каждое из чисел а1, a2,.... ak делится на d;
если d1≠ 0 — другой общий делитель чисел а1, а2,...ak, то d делится на d1
Ненулевые целые числа а и b называются ассоциированными (обозначается а ~ b), если а делится на b и b делится на а.
Теорема 1.2 (об ассоциированных числах). Числа а и b ассоциированы тогда и только тогда, когда а = ±b.
Доказательство. Пусть а делится на b, тогда существует такое целое число с, что а=bс. Поскольку |c| ≥ 1, получаем |a|= |b|*|c|≥|b|*1=|b|, то есть |a|≥|b|
В то же время b делится на а. Проводя аналогичные выкладки, получаем |b|≥ |а|. Таким образом, |a| = |b|, то есть а = ±b.
Теорема 1.3 (о единственности наибольшего общего делителя). Пусть числа a1, а2, .... ak целые и d1—их наибольший общий делитель. Целое число d2 является наибольшим общим делителем чисел а1, а2,.... аk тогда и только тогда, когда d2 ~d1.
Доказательство. Число d1 — наибольший общий делитель чисел a1, a2… ak, а d2 — общий делитель этих чисел. Значит, по определению наибольшего общего делителя, d1 делится на d2. Точно так же, если рассматривать d2 как наибольший общий делитель чисел a1, a2,…ak, a d1— как общий делитель этих чисел, то d2 делится на d1. Таким образом, d1 ~ d2. Необходимость доказана.
Теперь докажем достаточность. Пусть d2 ~ d1. Тогда, по определению наибольшего общего делителя, каждое из чисел а1, а2,... ak делится на d1. Кроме того, числа d1 и d2 ассоциированы, поэтому d1 делится на d2. Значит, каждое из чисел а1, a2, .... ak делится на d2. Таким образом, d2 — общий делитель чисел а1, а2, ...,ak. Покажем теперь, что он наибольший.
Пусть δ — некоторый общий делитель чисел а1, а2,...ak. По условию d1 = НОД(a1, а2 …ak) , тогда d1 делится на δ. А раз d2 ~ d1, то d2 делится на d1, значит d2 делится на δ и d2 = НОД(a1, а2, …ak).
Учитывая теоремы 1.2, 1.3, далее для определенности наибольший общий делитель целых чисел будем считать положительным числом.
Теорема 1.4 (о существовании и линейном представлении наибольшего общего делителя). Для любых целых чисел а1, а2, .... ak существует наибольший общий делитель d, и его можно представить в виде линейной комбинации этих чисел: d= c1a1 + c2a2 + ... + ckak, где сi Z.
Доказательство [I]. Пусть A = { c1a1 + c2a2 + ... + ckak | сi Z} — множество всевозможных целочисленных линейных комбинаций чисел а1, а2,.... аk. Будем считать, что не вес числа а1, а2,… аk нулевые, тогда в множестве А существует наименьший положительный элемент. Обозначим его d. Покажем, что множество А совпадает с множеством всех целых чисел, кратных d. Поскольку число d может быть представлено в виде линейной комбинации чисел а1, а2, ....ak то и любое число вида xid где xZ, может быть представлено в виде линейной комбинации этих чисел.
Обратно, любая линейная комбинация чисел а1, а2 …аk делится на d. Действительно, применим к числу d и произвольному элементу у А теорему о делении с остатком: существуют такие целые числа q и r, что y=qd+ r, причем 0≤r<d. Число r=y — qd является элементом множества А. поскольку у Аи d А. Но d — наименьший неотрицательный элемент множества А, значит, r = 0 и y=qd. Таким образом, A={xd|xi}.
Осталось доказать, что d — это наибольший общий делитель чисел a1, а2…ak. Каждое из этих чисел имеет вид xid, где хZ (достаточно рассмотреть линейную комбинацию вида 0*a1 + 0*a2 + … + 0 * ai-1 + 1*аi, + 0 *ai+1 +… + 0 * аk). Таким образом, d — общий делитель чисел а1, а2,.... ak.
Пусть с — любой другой делитель этих чисел. Тогда по свойству 2 делимости с делит каждую линейную комбинацию вида с1а1 + c2a2 + ... + ckak, в том числе и ту, которая равна d. □
Определение 1.7. Целые числа а1, a2, .... ак называются взаимно простыми в совокупности, если НОД(а1, а2,.... аk) = 1. Целые числа а и b называются взаимно простыми, если НОД(а, b)=1.
Определение 1.8. Целые числа а1 а2, .... ak называются попарно взаимно простыми, если НОД(ai, аj)= 1 для всех 1 ≤ i≠j ≤ k.
Взаимно простые числа обладают следующими свойствами.
Для того чтобы целые числа а1, а2, .... ak были взаимно простыми в совокупности, необходимо и достаточно, чтобы существовали такие целые числа с1, с2,…сk, что c1a1 + c2a2 + ... + сkаk= 1
Доказательство. Необходимость следует из теоремы о существовании и линейном представлении наибольшего общего делителя. Докажем достаточность. Пусть целые числа с1,c2…сk таковы, что c1a1 + c2a2 + ... + сkаk=1 и пусть d= НОД(a1 ,a2,…, ak). Тогда, по определению наибольшего общего делителя, каждое из чисел а1, а2, ..., ак делится на d. Значит, по свойству 2 делимости, и сумма c1a1 + c2a2 + ... + сkаk делится на d, то есть 1 делится на d, следовательно, по свойству 6 делимости, d = 1. Таким образом, 1 = НОД(a1, а2,..., аk) и числа ai взаимно просты в совокупности.
1’. Для того чтобы целые числа а, b были взаимно простыми, необходимо и достаточно, чтобы существовали такие целые числа m, п, что та + nb = 1.
Пусть произведение ab делится на с и НОД(а, с) = 1. Тогда b делится на с.
Доказательство. Числа а и с взаимно просты, тогда, по свойству 1’, существуют такие целые числа т, n, что та + пс =1. Домножим обе части последнего равенства на b:
mab + ncb = b.
Первое слагаемое в левой части равенства делится на с по условию. Второе слагаемое, очевидно, делится на с. Значит, и b делится на с.
□
3. Если НОД(а, b) = 1, НОД(а, с) = 1, то НОД(a, bс) = 1.
Доказательство. Числа а и b взаимно просты, поэтому по свойству 1' число 1 можно представить в виде 1 = та + пb, где числа т и n целые. Умножим обе части этого равенства на с, получим
с = mac + nbc.
Пусть d — наибольший общий делитель чисел а и bc. Тогда оба слагаемых в правой части равенства делятся на d, а значит и число с делится на d. Но 1 — наибольший общий делитель чисел а и с, то есть 1 делится на d и d= 1. □
Если НОД(a,b1)=1, НОД(а,b2)=1, .... НОД(а,bk)=1, то
НОД(а,b1b2..bk)= 1.
Пусть целые числа а1, а2, .... аl, b1, b2, .... bk таковы, что НОД(аi,bj)=1 для всех 1≤ i≤ l, 1≤ j≤ k. Тогда НОД(a1a2..al,b1,b2...bk)=1.
Пусть целое число а делится на b1 и на b2, НОД(b1 b2) = 1. Тогда a делится на произведение b1b2.
Доказательство. Число а делится на b1 поэтому существует такое целое число с, что a = cb1.
Так как а делится на b2. то произведение cb1 делится на b2 Но поскольку НОД(b1 b2) = 1, значит, по свойству 2 взаимно простых чисел, с делится на b2, то есть существует такое целое число d. что с = db2. Отсюда а = cb1 = db1b2, то есть а делится на b1b2, □
Если а делится на каждое из попарно взаимно простых чисел b1, b2,...bk, то а делится на произведение b1b2...bk.
Определение 1.9. Целое число М называется наименьшим общим кратным целых чисел а1, а2,…,аk, аi≠0 для i=1, 2, .... k (обозначается М=НОК(a1, а2, .... ak)), если выполняются следующие условия:
М делится на каждое из чисел а1,а2, ....ak;
если Mt — другое общее кратное чисел a1, а2,.... ak, то Mt делится на М.
Наибольший общий делитель и наименьшее общее кратное двух положительных целых чисел связаны соотношением:
НОД(а, b) • НОК(а, b) = аb.