ЭЛЕМЕНТЫ ТЕОРИИ ЧИСЕЛ

Основные определения и понятия темы

Отношение делимости на множестве целых чисел, наибольший общий делитель целых чисел, наименьшее общее кратное целых чисел, простые и составные числа, взаимно простые числа, числовые функции τ(n), σ(n), φ(n), каноническое разложение натурального числа, систематические числа, сравнимость чисел a и b по модулю m.

Основные теоремы и утверждения темы

Теорема о делении с остатком, теорема о нахождении наибольшего общего делителя с помощью алгоритма Евклида, теорема о нахождении НОД и НОК целых чисел с помощью разложения этих чисел на простые множители, теорема о вычислении наименьшего общего кратного, теорема о линейном представлении наибольшего общего делителя целых чисел, теорема о свойствах простых чисел, основная теорема арифметики, теоремы о вычислении числовых функций, критерий сравнимости двух чисел по модулю, свойства сравнений.

Рекомендуемая литература

1. Алгебра и теория чисел. Под ред. Н.Я. Виленкина. Часть 3. М: Просвещение, 1974, - 200 с.

2. А.А. Бухштаб. Теория чисел. М: Просвещение, 1966, - 384 с.

3. В.У. Грибанов, П. И. Титов. Сборник упражнений по теории чиcел. М: Просвещение, 1964, - 144 с.

4. А.А. Кочева. Задачник-практикум по алгебре и теории чисел. Часть 3. М: Просвещение, 1984, - 41 с.

Задание 2.1. Даны целые числа a и b. Найти:

а) наибольший общий делитель a и b;

b) линейное представление наибольшего общего делителя a и b;

с) наименьшее общее кратное a и b.

1.a=2576, b=154.

2.a=1073, b=3683.

3.a=2585, b=7975.

4.a=4598, b=1474.

5.a=9163, b=2737.

6.a=529, b=1817.

7.a=2346, b=646.

8.a=2223, b=1767.

9.a=1232, b=1672.

10. a=9639, b=2737.

11. a=1541, b=1817.

12. a=476, b=1258.

13. a=1491, b=2247.

14. a=2227, b=9911.

15. a=1541, b=529.

16. a=731, b=663.

17. a=629, b=1445.

18. a=3653, b=3107.

19. a=6919, b=1443.

20. a=1786, b=705.

Задание 2.2. Найти натуральные числа a и b, если:

1.

2.

3.

4.

5.

6.

7.

8.

9.

10.

11.

12.

13.

14.

15.

16.

17.

18.

19.

20.

Задание 2.3. Для натурального числа n найти:

a)число τ(n) всех натуральных делителей;

b)сумму σ(n) всех натуральных делителей;

c)количество φ(n) натуральных чисел, меньших n и взаимно простых с n.

1.n=1542.

2.n=1440.

3.n=1575.

4.n=1404.

5.n=1224.

6.n=20825.

7.n=22869.

8.n=4320.

9.n=2925.

10. n=7875.

11. n=9016.

12. n=19600.

13. n=15092.

14. n=11424.

15. n=1500.

16. n=1890.

17. n=18144.

18. n=5040.

19. n=2310.

20. n=3963.