Теория чисел

Теория чисел

1. Делимость

(в этой главе все числа у нас будут целыми) Скажем, что число a (a ≠ 0) делит число b, если b = ac .

Обозначается как a | b. Так же можем сказать, что b делится на a или b кратно a.

Так как 0 = 0 ·a, то a | 0, для любого a.

Свойства:

1) Если a|b и b ≠ 0, то |a| ≤ |b|;

2) Если a|b и a|c тогда a|αb + βc для любых α и β; 3) Если a|b и a|b ± c тогда a|c

4) a|a;

5) Если a|b и b|c, тогда a|c;

6) Если a|b и b|a, тогда |a| = |b|;

Теорема: Для любых чисел a и b, существует

единственная пара неотрицательных чисел (q, r), такие что

b = aq + r, r < a.

Пример1: Докажите, что для любого натурального 21�� + 4 

числа n, - целое.

14�� + 3

Док-во: Из равенства

2(21n + 4) − 3(14n + 3) = −1

следует, что 21n + 4 и 14n + 3 не имеют общих делителей, кроме 1.

Следовательно, выражение в условии не может быть целым числом.

Пример2: Докажите, что для любого нечетного числа p > 2 и положительного целого числа n, p делит следующую сумму:

����2����(�� − 1)���� 

1 + + · · · +

��

Док-во: Обозначим через k = �� и заметим, что k - нечетное число. Тогда

����+ (�� − ��)��= ��[����−1 − ����−2(�� − ��) + ... + (�� − ��)��−1] Суммируя такую сумму для d = 1 … (p - 1) / 2, получим, что p ��2��(�� − 1)�� 

делит 1 + + · · · +

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

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

Замечание: Любое натуральное число n > 1 имеет хотя бы один простой делитель. Если число n - простое, то его простым делителем является он сам.

Теорема: Простых чисел бесконечно много.

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

α1· ��2α2· . . . · ����α�� ����α�� 

n = �� , где - разные простые числа, - 1

положительные числа.

α1· ��2α2· . . . · ����α�� 

Замечание: Пусть n = �� . Тогда 1

сумма всех делителей числа n, вычисляется по формуле: 1��12��1α1 ��21��22��2α2 ����1����2

(1 + �� + + . . . + )(1 + + + . . . + ) . . . (1 + + + . 1

. . + �� )��α�� 

А количество делителей вычисляется по формуле: (α1 + 1) · (α2 + 1) ···· (α�� + 1)

Пример1: Найти все простые числа a, b, c, такие что ab + bc + ac > abc.

Решение: Предположим, что a ≤ b ≤ c. Если a ≥ 3, то