Контрольная работа по теории чисел (ЗФПМ51)
5 семестр
Задание 1
Найти НОД и НОК следующих чисел:
1) 1073, 3683, 34481; 2) 420, 126, 525;
3) 529, 1541, 1817; 4) 528, 628, 124.
Задание 2
Найти число и сумму натуральных делителей натурального числа:
1) 1524; 2) 1640; 3) 1280; 4) 2488.
Задание 3
Представить число в виде цепной дроби:
1) 
; 2) 
; 3) 
; 4) 
.
Задание 4
Сократите дробь при помощи разложения в конечную цепную дробь:
1) 
; 2) 
; 3) 
; 4) 
.
Задание 5
Решить в целых числах уравнение:
1) 
; 2) 
;
3) 
; 4) 
.
Задание 6
Вычислить значение функции Эйлера от данного числа:
1) 960; 2) 628; 3) 640; 4) 1228.
Задание 7
Найти остаток от деления числа:
1) 
на 7; 2) 
на 14; 3) 
на 26; 4) 
на 6.
Задание 8
Решить сравнение:
1) 
; 2) 
;
3) 
; 4) 
.
Пример выполнения контрольной работы
Задание 1
Найти наименьшее общее кратное чисел 624, 416 и 748.
Решение. Согласно теореме 2, [624, 408, 748] = [[624, 408], 748]. По теореме 1 
. Найдем (624, 408), применив к этим числам алгоритм Евклида: 624 = 408∙1+216, 416 = 216∙1+200, 216 = 200∙1+16, 200=16∙12+8, 16 = 8∙2. Следовательно, (624, 408) = 8, поэтому 
. Тогда [624, 408, 748] = [31824,748] 
. Найдем (31824, 748): 31824 = 748∙42 + 408, 748 = 408∙1 + 340, 408 = 340∙1 + 68, 340 = 68∙5. Следовательно, (31824, 748) = 68 и [624, 408, 748] = 
.
Задание 2
Найти число и сумму натуральных делителей натурального числа 1028.
Решение. Если 
, 
, - каноническое разложение числа 
на произведение простых множителей, то число его натуральных делителей 
, а сумма всех натуральных делителей числа ,
.
Представим число 1028 в виде произведения простых натуральных чисел: 1028 = 23
131. Число натуральных делителей 1028 
, а их сумма 
.
Задание 3
Представить число 
в виде цепной дроби.
Решение. Применим к числам -27, 25 алгоритм Евклида:
-27 = 25∙(-2) + 23, 25 = 23∙1 + 2, 23 = 2∙11 + 1, 2 = 1∙2 + 0.
Из этих равенств следует, что
.
Задание 4
При помощи разложения в цепную дробь сократить 
.
Решение. Представим число в виде конечной цепной дроби. Для этого применим к числам 5726, 6240 алгоритм Евклида:5726 = 06240 + 6240,
6240 = 15726 +514, 5726 = 11514 + 72, 514 = 727+10, 72 = 710 + 2, 10=25. 
, 
, 
, 
,
- элементы цепной дроби, 
. Числители и знаменатели подходящих дробей цепной дроби 
взаимно простые целые числа и последняя подходящая дробь 
. Найдем подходящую дробь
. Для этого составим таблицу
s | 0 | 1 | 2 | 3 | 4 | 5 |
qs | 0 | 1 | 11 | 7 | 7 | 5 |
Ps | 0 | 1 | 11 | 78 | 557 | 2863 |
Qs | 1 | 1 | 12 | 85 | 607 | 3120 |
Из таблицы следует, что 
, 
.
Задание 5
Найти общее решение уравнения 8х+19у=10 в целых числах.
Решение. Так как (8,19)=1, то уравнение имеет решение в целых числах. Представим 
в виде конечной цепной дроби: 
. Для нахождения
составим таблицу:
s | 0 | 1 | 2 | 3 | 4 |
qs | 0 | 2 | 2 | 1 | 2 |
Ps | 0 | 1 | 2 | 3 | 8 |
Qs | 1 | 2 | 5 | 7 | 19 |
Из таблицы следует, что 
. 
общее решение уравнения.
Задание 6
Вычислить значение функции Эйлера от числа 1028.
Решение. Если , , - каноническое разложение числа на произведение простых множителей, то
.
Так как 1028 = 23131, то 
.
Задание 7
Найти остаток от деления числа а = 
на 15.
Решение. Пусть r остаток от деления числа а на 15, а=15g+r, 
. Тогда 
. 
Пусть r=3r1, 
Тогда из сравнения 
следует, что 
. Так как (18,5)=1, то по теореме Эйлера 
.
. Из условий 
, , 
следует, что r1=3. Так как r = 3r1, то r = 9.
Задание 8
Решить сравнение 
.
Решение. Так как (82,14) = 2, 
, то сравнение имеет два решения. Поделив обе части сравнения на 2, получим равносильное сравнение 
, которое имеет одно решение, так как (41,101)=1. Решим это сравнение с помощью цепных дробей. Разложим 
в конечную цепную дробь: 
. Для нахождения числителя предпоследней подходящей дроби составим таблицу:
s | 0 | 1 | 2 | 3 |
qs | 2 | 2 | 6 | 3 |
РS | 2 | 5 | 32 | 101 |
Из таблицы следует, что Р2=32. Класс целых чисел 
или 
решение сравнения 
. Решением сравнения 
являются классы вычетов: 
, 
.
Основные порталы (построено редакторами)