Теория чисел
.pdf
Теория чисел1
1.Основные понятия теории делимости
Îп р е д е л е н и е. Число a делится на ненулевое число b, если найдется такое целое число c, что выполняется равенство a = b · c.
Обозначения:
1)a . b a делится на b;
2)b | a b делит a;
3)a кратно (кратное) b, b делитель a.
Деление с остатком
Пусть даны два числа a è b, a Z, b N, ãäå Z множество целых чисел, а N множество натуральных чисел. Разделим a íà b с остатком a = b · q + r, ãäå r лежит в промежутке 0 ≤ r < b, q неполное частное, r остаток. Например, 7 = 2 · 3 + 1.
Теорема 1. Для любого целого a и натурального b представление
a = b · q + r, 0 ≤ r < b
единственно.
Ä î ê à ç à ò å ë ü ñ ò â î
1. Существование.
Рассмотрим бесконечное множество чисел {a − tb}, ãäå a, b фиксированные числа, t любое число, t Z. Из него мы выберем наименьшее неотрицательное число r = a − q · b. Докажем, что r лежит в пределах
0 ≤ r < b.
Пусть это число не принадлежит данному промежутку. Тогда оно больше или равно b. Построим новое число r′ = r−b=a−q·b−b=a−b(q+1).
Отсюда видно следующее:
1)r′ {a − tb};
2)r′ неотрицательное;
1С.В.Федоренко. Сентябрь 2012. Курс лекций и задачи. Распространяется свободно. Курс читался в СПбГУАП (1997 1999; 2008 2011) и СПбГПУ (2002 2005).
1
3) r′ < r.
Следовательно, не r, a r′ является наименьшим неотрицательным числом из множества {a − tb}, тогда предположение r ≥ b ложно.
Существование доказано.
2. Единственность.
Пусть существует другое представление a = bq′ + r′, при условии, что 0 ≤ r′ < b; a, b фиксированные числа, q Z. Т.е., мы можем разделить число a íà b двумя способами, тогда bq + r = bq′ + r′. Перенося слагаемые ñ q в одну сторону, а с r в другую, получаем b(q − q′) = r′ − r. Видно,
÷òî (r′ − r) . b. Каждый из остатков меньше b è
{
(r′ − r) . b . |r′ − r| < b
Следовательно, r′ − r = 0, а значит r′ = r è q = q′. Итак, доказали,
что одно число можно разделить на другое единственным способом. Теорема доказана.
Теорема 2. Если a . b è b . c, òî a . c, ãäå b, c ≠ 0. Ä î ê à ç à ò å ë ü ñ ò â î
{
a = b · q . b = c · t
Следовательно, a = c · qt. По определению видно, что a . c.
Теорема 3. Пусть выполняется равенство a1 + a2 = b1 + b2 и числа a1, a2, b1 . d, тогда b2 . d.
Ä î ê à ç à ò å ë ü ñ ò â î
a1 = d · t1, a2 = d · t2, b1 = d · t3. Выразим b2 из условия теоремы b2 = a1 + a2 − b1=d(t1 + t2 − t3). По определению делимости видно, что b2 . d.
2.Наибольший общий делитель
Îп р е д е л е н и е. Если число c является делителем чисел a è b, то число c называется общим делителем чисел a è b.
2
О п р е д е л е н и е. Наибольший из общих делителей чисел a è b называется наибольшим общим делителем (НОД) чисел a è b.
Обозначение: (a, b) = d, ãäå a è b числа, а d наибольший общий
делитель этих чисел.
Рассмотрим пример для чисел 12 и 9. Выпишем все делители 12 и все делители 9. Для 12: 1, 2, 3, 4, 6 и 12; для 9: 1, 3 и 9; видно, что у них есть общие делители 1 и 3. Выберем наибольший из них это 3. Таким образом, (12, 9) = 3.
О п р е д е л е н и е. Два числа a è b называются взаимно простыми, если их НОД равен 1.
Пример. Т.к. (10,9)=1, то 10 и 9 взаимно простые числа.
Это определение можно распространить на любое количество чисел. Если (a, b, c, . . .) = 1, то числа a, b, c, . . . взаимно простые. Например:
(12,9,2)=1.
Î ï ð å ä å ë å í è å. (a1, a2, ...an) попарно взаимно простые числа, если НОД любой пары равен единице (ai, aj) = 1, i ≠ j.
Например: 12,17,11 не только взаимно простые, но и попарно взаимно простые.
Теорема 1. Если a . b, òî (a, b) = b.
Ä î ê à ç à ò å ë ü ñ ò â î
Число b не может делиться на число больше самого себя. Следовательно, b является НОДом a è b.
Теорема 2. Пусть имеется представление a = bq + r (r не обязательно остаток), тогда (a, b) = (b, r).
Äî ê à ç à ò å ë ü ñ ò â î
1.Рассмотрим любой общий делитель a è b c. Åñëè a . c è b . c, òî
по теореме 1.3 r . c, ò.å. c является также общим делителем b è r. Любой общий делитель a è b является общим делителем b è r.
2. Любой общий делитель b è r является делителем a. Значит, общие делители a, b è b, r совпадают. Это верно и для НОД.
3
3.Алгоритм Евклида
Для любых чисел a è b с помощью алгоритма Евклида можно найти
ÍÎÄ.
Пусть a, b N входные данные алгоритма, а (a, b) = d N выходные.
|
1 |
a |
= bq0 |
+ r1 |
0 < r1 < b |
|
2 |
b |
= r1q1 |
+ r2 |
0 < r2 < r1 |
|
3 |
r1 |
= r2q2 |
+ r3 |
0 < r3 < r2 |
|
· · · |
|
· · · |
|
· · · |
|
i |
ri−2 |
= ri−1qi−1 |
+ ri |
0 < ri < ri−1 |
|
· · · |
|
· · · |
|
· · · |
|
n |
rn−2 = rn−1qn−1 + rn |
0 < rn < rn−1 |
||
|
n + 1 |
rn−1 = rnqn |
+ 0 |
|
|
Шаг 1. Делим a íà b с остатком a = bq0 +r1, ãäå 0 < r1 < b. По теореме 2.2 (a, b) = (b, r1).
Шаг 2. Делим b íà r1 с остатком b = r1q1 + r2, ãäå 0 < r2 < r1. Ïî теореме 2.2 (b, r1) = (r1, r2).
И так до тех пор, пока не разделится нацело. Из цепочки равенств
(a, b) = (b, r1) = (r1, r2) = (r2, r3) = ... = (rn−2, rn−1) = (rn−1, rn) = rn
следует, что последний ненулевой остаток rn будет наибольшим общим делителем d = rn = (a, b). Т.к. остатки убывают, то алгоритм завершится за конечное число шагов.
Теоремы, связанные с алгоритмом Евклида
Теорема 1. НОД двух чисел делится на любой общий делитель этих
чисел.
Åñëè (a, b) = d, òî (ac , cb ) = dc , ãäå c общий делитель a è b.
Äî ê à ç à ò å ë ü ñ ò â î
Âзаписи алгоритма Евклида a, b è âñå ri разделим на c. Получим
запись алгоритма Евклида с входными данными a b
÷òî ÍÎÄ a |
b |
c è c . Из нее видно, |
d |
||
c |
è c |
равен c . |
Теорема 2. Если два числа разделить на их НОД, то получим взаимно простые числа (ad , db ) = 1.
Ä î ê à ç à ò å ë ü ñ ò â î
4
Вместо c (из теоремы 1) подставим d.
{
(a, b) = 1, òî c . b. ac . b
Ä î ê à ç à ò å ë ü ñ ò â î
Для взаимно простых чисел a è b по теореме 7.1 существует представление ax + by = 1. Умножая это равенство на c, имеем ac ·x + byc = c,
íî ac = bq, bqx + byc = c, b(qx + yc) = c. Следовательно, c . b.
НОД нескольких чисел
(a1, a2, . . . , an) = dn (a1, a2) = d2
(d2, a3) = d3
. . .
(dn−1, an) = dn
4.Наименьшее общее кратное
Îп р е д е л е н и е. Общее кратное двух чисел a è b это такое число, которое делится на оба этих числа a è b.
Îп р е д е л е н и е. Наименьшее из общих кратных чисел a è b называется наименьшим общим кратным (НОК) чисел a è b.
Пусть M . a è M . b, тогда M общее кратное a è b. Наименьшее общее кратное чисел a è b обозначим как [a, b].
Теорема 1. НОК двух чисел равен отношению их произведения к
ÍÎÄó
[a, b] = (a,abb).
Ä î ê à ç à ò å ë ü ñ ò â î
Обозначим некоторое общее кратное чисел a è b через M, тогда M .
a è M . b. Кроме того, d = (a, b), a = a′d, b = b′d, причем (a′, b′) = 1. По определению делимости M = a · k, ãäå k Z
5
|
M |
|
= |
a · k |
Z, |
|
||||
|
b |
|
b |
|
||||||
ak |
|
= |
a′dk |
= |
a′k |
, |
||||
b |
b′d |
b′ |
||||||||
a′ не делится на b′, т.к. они взаимно простые, следовательно k . b′ ïî теореме 3.3
k = b′ · t = |
bt |
, t Z, |
||||
|
|
|||||
|
d |
|||||
тогда |
|
|
|
|
|
|
|
ab |
|
ab |
|||
M = a · k = |
|
t = |
|
t − |
||
d |
(a, b) |
|||||
вид любого общего кратного чисел a è b. Ïðè t = 1 M является НОК чисел a è b.
НОК нескольких чисел
[a1, a2, . . . , an] = Mn [a1, a2] = M2
[M2, a3] = M3 [M3, a4] = M4
. . .
[Mn−1, an] = Mn
Åñëè (a, b) = 1, òî [a, b] = ab. Ïðè (ai, aj) = 1, i ≠ j, M = a1a2 · . . . · an.
5.Простые и составные числа
Любое число делится на 1 и на само себя. Назовем эти делители тривиальными.
О п р е д е л е н и е. Число называется простым, если оно не имеет нетривиальных делителей. Число называется составным, если оно имеет нетривиальный делитель. Число 1 не является ни простым ни составным.
Теорема 1. Для любого натурального числа a и простого числа p
выполняется или (a, p) = 1 èëè a . p.
6
Äî ê à ç à ò å ë ü ñ ò â î
Óпростого числа p имеются два тривиальных делителя. Возможны
два варианта: a . p èëè a ̸. p. Åñëè a ̸. p, то НОДом a è p является 1. Следовательно, (a, p) = 1.
Теорема 2. Наименьший отличный от единицы делитель целого, большего единицы, есть простое число.
Ä î ê à ç à ò å ë ü ñ ò â î
Åñëè a ≠ 1, òî a = p·q, ãäå p наименьший нетривиальный делитель. Предположим, что p составное число. Это означает, что существует
такое число s, ÷òî p . s, но тогда a . s è p не является наименьшим делителем, что противоречит условию. Т.о. p простое число.
Теорема 3. Наименьший нетривиальный делитель составного числа не превосходит его корня.
Ä î ê à ç à ò å ë ü ñ ò â î
√
a = q · b, q ≤ b, q2 ≤ bq = a, q ≤ a.
Решето Эратосфена
Запишем множество натуральных чисел
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, . . .
Единица это особое число. С остальными числами поступаем следующим образом: берем число, объявляем его простым и вычеркиваем числа, кратные ему.
Например, 2 простое число, вычеркиваем числа, кратные двойке, следовательно, четных чисел не останется. Аналогично поступим и с тройкой. Нужно вычеркнуть 6, 9, 12, 15, 18, и т.д. Все оставшиеся числа являются простыми.
Теорема 4. Множество простых чисел бесконечно. Д о к а з а т е л ь с т в о
Пусть {2, 3, 5, . . . , P } конечное множество простых чисел и N = 2·3·5·. . .·P +1. N не делится ни на одно из простых чисел, т.к. при делении в остатке получается 1. Но наименьший нетривиальный делитель N по теореме 2 является простым числом ̸ 2{, 3, 5, . . . , P }. Следовательно, простых чисел не конечное множество, а бесконечное.
7
6.Каноническая форма числа
Теорема 1 (Основная теорема арифметики). Любое число, отличное от 1, единственным способом представляется в виде произведения простых чисел.
Ä î ê à ç à ò å ë ü ñ ò â î
1. Существование.
Число n по теореме 5.2 имеет простой делитель p1
n n1 = p1 .
Аналогичные рассуждения справедливы и для числа n1
n2 = n1 , p2
ãäå p2 простой делитель n1. И так будем продолжать до тех пор, пока не получим ni = 1.
2. Единственность.
Пусть число n имеет два разложения на простые числа
n = p1 · p2 · . . . · pl = q1 · q2 · . . . · qs.
Без ограничения общности примем l ≤ s. Если левая часть равенства делится на p1, то и правая тоже делится на p1. Значит, некоторое qi = p1. Пусть это q1 = p1. Разделим обе части равенства на p1
p2 · . . . |
· pl = q2 · . . . |
· qs. |
Аналогично, примем q2 = p2. Будем продолжать эту процедуру, пока выражение не примет вид
1 = ql+1 · . . . · qs.
Åñëè l < s, то произведение простых чисел не может быть равно 1. Следовательно, предположение о двух различных разложениях числа n невер-
íî. Åñëè s = l, òî pi = qi äëÿ i [1, l] и два разложения совпадают. Теорема доказана.
Любое число n N можно записать в канонической форме
n = p1s1 · . . . · plsl ,
8
ãäå pi простые числа, si N.
Каноническое представление позволяет выписать все делители числа и определить НОД и НОК.
Все делители c числа n имеют вид
c = p1i1 · p2i2 . . . plil , ãäå ij [0, sj].
Нахождение НОД и НОК
Пусть числа a è b представлены в виде
a = p1s1 · p2s2 · . . . · plsl b = p1t1 · p2t2 · . . . · pltl .
Это представление отличается от канонического тем, что некоторые si è ti могут быть равны 0.
Тогда наибольший общий делитель a è b
(a, b) = p1min(s1,t1) · p2min(s2,t2) · . . . · plmin(sl,tl),
а наименьшее общее кратное:
[a, b] = p1max(s1,t1) · p2max(s2,t2) · . . . · plmax(sl,tl).
Отсюда также видно, что (a, b) делится на любой общий делитель a è b.
7.Линейные диофантовы уравнения с двумя неизвестными
Îп р е д е л е н и е. Линейным диофантовым уравнением с двумя неизвестными называется уравнение вида
ax + by = c,
где коэффициенты a, b, c и неизвестные x, y целые числа, а a è b не равны нулю одновременно.
9
Теорема 1 (О линейном представлении НОД). Для любой пары чисел (a, b) ((a, b) ≠ (0, 0)) существуют такие x, y Z, ÷òî ax + by=(a, b).
Ä î ê à ç à ò å ë ü ñ ò â î
Рассмотрим множество чисел {ax + by} и из него выберем минимальное положительное число d = ax0 + by0.
Докажем, что d является делителем b.
Пусть d не делитель b, следовательно, b = d · q + r, ãäå 0 < r < d,
r = b − dq = b − (ax0 + by0)q = a(−x0q) + b(1 − y0q). Видно, что:
1)число r {ax + by};
2)r положительное;
3)r < d.
Но мы предположили, что d наименьшее положительное число из этого множества, следовательно, наше предположение, что r < d неверно, значит d делитель b.
Аналогично можно доказать, что a . d.
Из всего этого следует, что d является общим делителем a è b.
a . (a, b)
Èòàê, b . (a, b) d . (a, b), íî d общий делитель a è b, следова- тельно, d ÍÎÄ a è b.
Теорема 2. Уравнение ax + by = c имеет решение тогда и только тогда, когда c делится на (a, b).
Äî ê à ç à ò å ë ü ñ ò â î
1.Пусть c . (a, b), тогда по теореме 1 ax + by = (a, b). Умножим уравнение на c
(a,b)
a · (a,xcb) + b · (a,ycb) = c.
Пара чисел (x0, y0) будет решением исходного уравнения
{x0 = (a,bxc ) y0 = (a,byc ) .
2. Докажем, что если уравнение имеет решение, то c . (a, b).
a . (a, b) , следовательно, c тоже должно делиться на (a, b).
b . (a, b)
10