close

Вход

Забыли?

вход по аккаунту

?

Fedorenko3

код для вставкиСкачать
???????????? ??????????? ? ????? ?????????? ?????????
??????????????? ??????????????? ??????????
??????? ????????????????? ???????????
?????-????????????? ??????????????? ???????????
???????????????? ???????????????
C. ?. ?????????
?????????? ??????????
?????? ? ??????????? ??????
?? ?????? ?????
???????????? ????????
?????-?????????
2011
??????????? ????????? ?. ?. ?????????
????????? ?????? ??????? ?????????????? ?????????? ?
???????????? ????? ?????-?????????????? ???????????????? ???????????????? ????????????, ????????
??????????? ???? ?. ?. ????????
????????? ?????? ? ??????????? ?????? ??? ?????????, ??????????? ?? ???????????? «?????????????? ????????????», «?????????????? ???????», «??????????? ? ?????????????? ???????».
????????????? ??? ????????? ????????????? 090104.
???????????? ???????? ??????????? ?????? ?????????? ? ????????????? ? ??????? ???????????-???????????? ??????? ??????????????????? ???????????????? ???????????? ????????????????
???????????????.
???????? ?. ?. ?????????
????????? ? ?????? 05.05.11. ?????? 60Ч84 1/16.
?????? ????????. ???. ???. ?. 1,13. ????? 100 ???. ????? ? 185.
???????????-???????????? ????? ????
190000, ?????-?????????, ?. ??????? ??., 67
© ?????-????????????? ???????????????
??????????? ????????????????
??????????????? (????), 2011
1.
Теоремы Ферма и Эйлера
Теорема 1.1 (Эйлера).
справедливо сравнение
Для любых a и m при (a, m) = 1
a?(m) ? 1 (mod m).
Доказательство
Если x пробегает приведенную систему вычетов по модулю m,
то и ax пробегает приведенную систему вычетов. То есть, если
x ? {r1 , r2 , r3 , . . . , r?(m) },
то
ax ? {?1 , ?2 , ?3 , . . . , ??(m) }.
Эти два множества совпадают с точностью до порядка элементов.
Кроме того, имеет место система сравнений
?
a · r 1 ? ?1
?
?
?
?
(mod m)
a · r2 ? ?2 (mod m)
.
...
?
?
?
?a · r
?(m) ? ??(m) (mod m)
3
Перемножим почленно эти сравнения
a?(m) · r1 · r2 · r3 · . . . · r?(m) ? ?1 · ?2 · ?3 · . . . · ??(m)
(mod m).
Из последнего сравнения и из тождества
?1 · ?2 · ?3 · . . . · ??(m) ? r1 · r2 · r3 · . . . · r?(m)
(mod m)
следует теорема Эйлера
a?(m) ? 1 (mod m).
Теорема 1.2 (Ферма).
сравнение
При простом p и a ? ... p справедливо
ap?1 ? 1 (mod p).
Доказательство
Так как a ? ... p, то (a, p) = 1. Из теоремы Эйлера имеем
a?(p) ? 1 (mod p)
и
ap?1 ? 1 (mod p).
Теорема 1.3 (Ферма).
При простом p справедливо сравнение
ap ? a (mod p).
Доказательство
Рассмотрим два случая.
1. Пусть a ? ... p, тогда, умножая сравнение ap?1 ? 1 (mod p)
на a, имеем ap ? a (mod p).
2. Пусть a ... p. Так как (ap ? a) ... p, то ap ? a ? 0 (mod p) и,
следовательно, ap ? a (mod p).
4
2.
Сравнения первой степени с одним
неизвестным
Сравнением первой степени с одним неизвестным называется выражение вида
Определение.
ax ? b (mod m),
где коэффициенты a, b и неизвестное x целые числа, а модуль
m натуральное число.
Решить сравнение значит найти все значения x, ему удовлетворяющие. Класс чисел по mod m считается за одно решение.
Теорема 2.1. Если (a, m) = 1, то сравнение ax ? b (mod m)
имеет единственное решение.
Доказательство
Пусть x пробегает полную систему вычетов по mod m, тогда
ax тоже будет пробегать полную систему вычетов. Следовательно,
имеется единственное значение x, при котором ax будет сравнимо
с b.
Имеется несколько методов решения сравнений при (a, m) = 1.
1. Путем подбора x из множества {0, 1, . . . , m ? 1}.
2. Применяя расширенный алгоритм Евклида. Так как из
ax + mq = b ? ax ? b (mod m),
то, применяя его для a и m, получим x и q (нам требуется только
x).
3. Используя теорему Эйлера, по формуле
x ? b · a?(m)?1
5
(mod m).
Доказательство
Подставляя x ? b · a?(m)?1 в ax ? b (mod m), получаем тождество a · b · a?(m)?1 = b · a?(m) ? b · 1 ? b (mod m).
Теорема 2.2. Если (a, m) = d, то сравнение ax ? b (mod m)
не имеет решения, если b ? ... d, и имеет d решений, если b ... d.
Доказательство
Так как a ... d и m ... d, то по свойству сравнений 10 b должно
делиться d. Если b ? ... d, то сравнение не выполняется и решений
не имеет.
Пусть a = a?d, m = m?d, b = b?d, причем (a?, m?) = 1. Так
как a ... d, b ... d и m ... d, то по свойству сравнений 8 сравнение
ax ? b (mod m) можно разделить на d:
a? x ? b?
(mod m? ).
(1)
Так как (a?, m?) = 1, то это сравнение имеет единственное решение
по модулю m?.
Пусть x0 решение сравнения (1). Покажем, что x0 будет решением исходного сравнения. Умножая все три части сравнения
a? x0 ? b? (mod m? ) на d, имеем ax0 ? b (mod m). Верно и обратное: если x0 решение исходного сравнения, то x0 (mod m?)
будет решением сравнения (1). Следовательно, любое
решение исm
ходного сравнения должно иметь вид x = x0 + i d , i ? Z , где x0
наименьшее неотрицательное решение сравнения (1).
Докажем это утверждение. Подставляя x = x0 + i md в сравнение ax ? b (mod m), имеем
(
a x0 + i
m)
? b (mod m);
d
a · x0 + a · i
m
? b (mod m);
d
a · x0 + a? · i · m ? b (mod m).
6
Но (a? · i · m) ... m и ax0 ? b (mod
m).
m
Во множестве {x = x0 + i d | i ? Z} имеется ровно d неотрицательных чисел, меньших m. Они и являются решением по
mod m.
Итак, сравнение
ax ? b (mod m)
при b ... d имеет d решений
x ? x0 + i
m
d
(mod m),
где i ? [0, d ? 1], x0 наименьшее неотрицательное решение сравнения
a
b (
m)
d
3.
x?
mod
d
d
.
Системы сравнений первой степени
Теорема 3.1.
Система сравнений
{
x ? c1
x ? c2
(mod m1 )
(mod m2 )
имеет единственное решение, представляющее собой класс чисел
по модулю M , если (c2 ? c1) ... d, и не имеет решения, если (c2 ? c1)
.
? .. d, где M = [m1 , m2 ], d = (m1 , m2 ).
Доказательство
Выразим x из первого сравнения системы
x = c1 + m1 k,
7
(2)
где k ? Z . Подставляя x во второе сравнение, получаем
c1 + m1 k ? c2
(mod m2 ),
m1 k ? c2 ? c1
(mod m2 ).
Так как m1 ... d и m2 ... d, то по свойству сравнений 10 c2 ?c1 должно
делиться на d. Если c2 ? c1 не делится на d, то сравнение не имеет
решения и у системы решения также не будет.
Разделим последнее выражение на d:
m1
c2 ? c1
k?
d
d
(
(
mod
m2 )
.
d
(3)
)
Так как md1 , md2 = 1, то сравнение (3) имеет единственное решение по mod md2 . Обозначим это решение через ?:
k??
(
mod
m2 )
d
и запишем его в виде множества чисел
k =?+
m2
· l,
d
l ? Z.
Подставляем k в (2)
x = c1 + m1 (? +
m1 m2
m2
l) = c1 + m1 ? +
l = c1 + m1 ? + M l.
d
d
Запишем это решение системы как класс чисел по mod M
x ? c1 + m1 ? (mod M ),
где ? решение сравнения (3).
Для решения систем, состоящих из трех и более сравнений,
можно использовать метод последовательного решения. То есть
последовательно заменяем два сравнения их решением.
8
Теорема 3.2.
Система
?
x ? c1
?
?
?x ? c
2
?
.
.
.
?
?
(mod m1 )
(mod m2 )
x ? cs
(mod ms )
x ? c1
x ? c2
(mod m1 )
,
(mod m2 )
?
? x ? c1
(mod m1 )
...
?
x ? cl
(mod ml )
имеет единственное решение, если все модули попарно взаимно
простые.
Доказательство
База математической индукции.
Пусть s = 2, т.е. рассмотрим систему из двух сравнений
{
где (m1, m2) = 1. По теореме 3.1 эта система имеет единственное
решение.
Индукционное предположение.
Пусть s = l, тогда система имеет вид
и единственное решение
x ? ? (mod m1 · m2 · . . . · ml ).
Индукционный переход.
Пусть s = l + 1, тогда
?
x ? c1
?
?
?
(mod m1 )
...
.
?
x ? cl (mod ml )
?
?
x ? cl+1 (mod ml+1 )
По индукционному предположению заменим l сравнений их
решением
{
x ? ? (mod m1 · m2 · . . . · ml )
.
x ? cl+1 (mod ml+1 )
9
Заметим, что (m1 ·m2 ·. . .·ml , ml+1) = 1, и так как модули попарно
взаимно простые, то система будет иметь единственное решение
x??
(mod m1 · m2 · . . . · ml+1 ).
По методу математической индукции теорема доказана.
4.
Китайская теорема об остатках
Пусть m1, . . . , ms попарно взаимно простые
натуральные числа, mi > 1, M = m1 · m2 · . . . · ms, тогда каждому
числу x, x ? [0, M ? 1] взаимно однозначно соответствует вектор
вычетов (c1, . . . , cs) по модулям (m1, . . . , ms).
Доказательство
Система
?
Теорема 4.1.
x ? c1
?
?
?x ? c
2
?...
?
?
(mod m1 )
(mod m2 )
x ? cs
(mod ms )
имеет единственное решение
x ? x0
(mod M ),
M
yi ? 1
где yi решение сравнения m
x0 =
s
?
M
i=1
mi
,
(mod mi )
i
,
i ? [1, s]
yi ci .
Возьмем число x0 по модулю mi. Так как mM ... mi при j ?= i и
учитывая, что
x0 ?
, имеем
j
M
yi ? 1 (mod mi )
mi
? M
j?=i
mj
yj cj +
M
M
yi ci ?
yi ci ? ci
mi
mi
10
(mod mi ).
Это сравнение удовлетворяет i-й строке системы.
Повторяя эти рассуждения для всех i ? [1, s], получаем доказательство теоремы.
Задачи
ќ1. Число a = 42157 при делении на некоторое целое положительное число b дало в частном q = 231. Найти делитель b и
остаток r.
ќ2. Показать, что если mn + pq делится на m ? p, то и mq + np
делится на m ? p, где m, n, p, q целые числа.
ќ3. Показать, что если пятизначное число делится на 41, то и
все числа, полученные круговой перестановкой цифр этого числа,
делятся на 41.
ќ4. Пользуясь алгоритмом Евклида, найти НОД следующих
систем чисел: 1) 546 и 231; 2) 1001 и 6253; 3) 1517 и 2257; 4) 2737,
9163 и 9639; 5) 1411, 4641 и 5253.
ќ5. Разложением на простые множители найти НОК следующих чисел: 1) 360 и 504; 2) 2520 и 6600; 3) 187 и 533; 4) 9163, 2737
и 9639; 5) 374, 1599 и 9061.
ќ6. Найти НОД следующих систем чисел: 1) 299, 391 и 667; 2)
588, 2058 и 2849; 3) 31605, 13524, 12915 и 11067; 4) 279, 372 и 1395;
5) 2988, 3735, 8134 и 14525.
ќ7. По формуле [a, b] = (a,abb) найти НОК следующих чисел:
1) 252 и 468; 2) 279 и 372; 3) 178 и 381; 4) 318 и 477; 5) 758 и 1137.
Указание: НОД находится с помощью алгоритма Евклида.
Проверить ответы путем отыскания НОК разложением чисел на
простые множители.
ќ8. Дано (a, b)=24, [a, b]=2496. Найти a и b.
ќ9. Сумма двух чисел 667, а отношение НОК к их НОД равно
120. Найти эти числа.
11
ќ10. Найти два числа, зная, что сумма частных от деления
каждого из них на их НОД равна 18 и НОК равно 975.
ќ11. Дано: a = 899, b = 493. Найти d = (a, b) и определить x и
y , посредством которых можно осуществить линейное представление НОД в виде
d = ax + by.
ќ12. Решить предыдущую задачу для следующих пар чисел:
1) a=1445, b=629; 2) a=903, b=731; 3) a=1786, b=705; 4)
a=4543; b=885; 5) a=6919, b=1443.
ќ13. Найти сумму и число делителей всех следующих натуральных чисел: 1)375; 2)720; 3)957; 4)988; 5)990; 6)1200; 7)1440;
8)1500; 9)1890; 10)4320.
ќ14. Найти все делители чисел: 1) 360, 2) 375, 3) 957, 4) 988.
ќ15. N = p? · q? , где p и q ?= p простые числа. N 2 имеет 15
различных делителей. Сколько различных делителей имеет N 3?
ќ16. Показать, что произведение всех делителей числа N равно N n/2, где n число всех его делителей.
ќ17. Найти число N , произведение всех делителей которого
равно 5832.
ќ18. Найти число N , произведение всех делителей которого
равно 330 · 540.
ќ19. Найти число N = 2?5? 7? , зная, что 5N имеет на 8 делителей больше, чем N ; 7N на 12 делителей больше, чем N ; 8N
на 18 делителей больше, чем N .
ќ20. Найти функцию Эйлера для чисел: 1)375; 2)720; 3)957;
4)988; 5)990; 6)1200; 7)1440; 8)1500; 9)1890; 10)4320.
ќ21. Найти функцию Эйлера для простых чисел: 1)17; 2)31;
3)43; 4)71; 5)83.
ќ22. Найти функцию Эйлера для степеней простых чисел: 1)
5
3 ; 2) 54 ; 3) 113 ; 4) 172 ; 5) 232 .
ќ23. Найти функцию Эйлера от каждого из следующих произведений, не вычисляя самих произведений:
1) 5·11; 2) 5·7·13; 3) 17·23; 4) 12·17; 5) 14·15;
6) 11 · 14 · 15; 7) 32 · 81 · 49; 8) 24 · 28 · 45; 9) 720 · 957;
10) 990 · 1890;
12
Указание: чтобы сомножители были попарно простыми, следует предварительно представить их, а затем и все произведение
в каноническом разложении. Например, 12·21·28 = 22 ·3·3·7·22 ·7=
24 · 32 · 72 .
ќ24. Сколько чисел в интервале от 1 до 120 не взаимно простых с 30?
ќ25. Дано, что ?(a) = 3600 и a = 3?5? 7? . Найти a.
ќ26. Дано, что ?(a) = 120 и a = pq, где p и q различные
простые числа. Найти a, если p ? q = 2.
ќ27. Дано, что ?(a) = 11424 и a = p2q2, где p и q различные
простые числа. Найти a.
ќ28. Найти количество натуральных чисел, меньших числа
300 и имеющих с ним наибольшим общим делителем число 20.
ќ29. Найти количество натуральных чисел, меньших числа
1665 и имеющих с ним наибольшим общим делителем число 37.
ќ30. Найти количество натуральных чисел, меньших числа
1476 и имеющих с ним наибольшим общим делителем число 41.
ќ31. Показать, что если n нечетное число, то n2 ? 1 ?
0 (mod 8).
ќ32. Показать, что если p простое число, то
(a + b)p ? ap + bp
ќ33. Показать, что если
(mod p).
, то a ? 2b + 4c ? 0 (mod 21).
ќ34. Если
то 3n+4 ? ?1 (mod 10).
ќ35. Написать все три вида как полной, так и приведенной
системы вычетов по следующим модулям: 1) m =9; 2) m =8;
3) p =13; 4) m =12; 5) m =15; 6) p =7; 7) m =10.
ќ36. Показать, что числа 25, ?20, 16, 46, ?21, 18, 37, ?17
составляют полную систему вычетов по модулю m = 8.
ќ37. Показать, что числа 32, ?9, 15, 42, ?18, 30, 6 составляют
полную систему вычетов по модулю p = 7.
ќ38. Показать, что числа 21, 2, ?18, 28, ?19, 40, ?22, ?2, 15
составляют полную систему вычетов по модулю m = 9.
100a + 10b + c ? 0 (mod 21)
3n ? ?1 (mod 10),
13
ќ39. Показать, что числа 24, 18, ?19, 37, 28, ?23, ?32, 5, 41,
, составляют полную систему вычетов по модулю m = 11.
ќ40. Показать, что числа 19, 23, 25, ?19 составляют приведенную систему вычетов по модулю m = 12.
ќ41. Показать, что числа 11, ?1, 17, ?19 составляют приведенную систему вычетов по модулю m = 8.
ќ42. Показать, что числа 13, ?13, 29, ?9 составляют приведенную систему вычетов по модулю m = 10.
ќ43. Найти наименьшие неотрицательные, наименьшие по абсолютной величине неположительные и абсолютно наименьшие
вычеты чисел 24, 14, 25, 37, ?8, ?19, ?40 по модулю m = 6. Ко
скольким различным классам принадлежат данные числа по данному модулю? Какие числа из данных принадлежат к одному и
тому же классу по данному модулю?
ќ44. Найти наименьшие неотрицательные, наименьшие по абсолютной величине неположительные и абсолютно наименьшие
вычеты чисел 17, ?14, 19, ?49, ?22, ?21, ?29 по модулю m = 8.
Ко скольким различным классам принадлежат данные числа по
данному модулю? Какие числа из данных принадлежат к одному
и тому же классу по данному модулю?
ќ45. Найти наименьшие неотрицательные, наименьшие по абсолютной величине неположительные и абсолютно наименьшие
вычеты числа 100 по модулям 5, 7, 11, 25, 120, 200.
ќ46. Найти наименьшие неотрицательные, наименьшие по абсолютной величине неположительные и абсолютно наименьшие
вычеты числа 50 по модулям 3, 8, 12, 25, 70, 100.
ќ47. Заменить вычеты ?9, ?8, ?7, ?6, ?5, ?4, ?3,
?2, ?1, 0 по модулю 10 наименьшими неотрицательными вычетами по этому модулю.
ќ48. Проверить теорему Эйлера:
1) при a = 5, m = 24; 2) при a = 2, m = 33; 3)
при a = 3, m = 16; 4) при a = 3, m = 18; 5) при
a = 3, m = 24.
?35 ?33
14
ќ49. Пользуясь теоремами Эйлера и Ферма, составить сравнения по модулям:
1) 6;
2) 5;
3) 8;
a
4) 7;
5) 10;
6) 12.
Выписать значения и классы чисел, удовлетворяющих каждому сравнению.
ќ50. Найти остатки от деления:
1) 383175 на 45; 2) 109345 на 14; 3) 439291 на 60;
4) 293275 на 48; 5 6617 на 7; 6) 11753 на 11.
ќ51. Найти остатки от деления:
1) 380 + 780 на 11; 2) 3100 + 5100 на 7; 3) 2100 + 3100 на 5; 4)
570 + 750 на 12; 5) 580 + 7100 на 13; 6) 550 + 13100 на 18.
ќ52. Решить способом Эйлера следующие сравнения:
1) 3x ? 1 (mod 5);
2) 5x ? 6 (mod 7);
3) 5x ? 7 (mod 10);
4) 3x ? 8 (mod 13);
5) 25x ? 15 (mod 17);
6) 29x ? 3 (mod 12);
7) 5x ? 26 (mod 12);
8) 4x ? 7 (mod 8).
ќ53. Решить следующие сравнения:
1) 7x ? 4 (mod 19);
2) 13x ? 1 (mod 27);
3) 37x ? 25 (mod 117);
4) 113x ? 89 (mod 311);
5) 221x ? 111 (mod 360);
6) 23x ? 667 (mod 693);
7) 143x ? 41 (mod 221);
8) 91x ? 143 (mod 222);
9) 271x ? 25 (mod 119);
10) 13x ? 178 (mod 153).
Указания:
1) в примерах 8, 9 и 10 сравнения предварительно упростить;
2) Правильность ответов проверить подстановкой.
15
ќ54. Решить одним из способов следующие сравнения, в которых (a, m) = d > 1 и d | b:
1) 12x ? 9 (mod 15);
2) 12x ? 9 (mod 18);
3) 20x ? 10 (mod 25);
4) 10x ? 25 (mod 35);
5) 39x ? 84 (mod 93);
6) 90x + 18 ? 0 (mod 138);
7) 375x ? 195 (mod 501);
8) 14x ? 22 (mod 36);
9) 78x ? 42 (mod 51);
10) 114x ? 42 (mod 87).
ќ55. Решить системы сравнений:
?
?x ? 4
,
?
? x ? 13
(mod 5)
1) x ? 1 (mod 12)
?
x ? 7 (mod 14)
?
x?1
?
?
?x ? 2
3)
?
x?3
?
?
x?4
,
;
(mod 25),
(mod 4),
(mod 7),
(mod 9);
2)
?
? 4x ? 3
(mod 13)
5x ? 8 (mod 17)
5)
?
3x ? 7 (mod 31)
?
?
14x ? 35 (mod 19)
?
? 3x ? 7
?
4x ? 7
?
?
?
;
,
,
;
(mod 12),
(mod 8),
(mod 11);
9)
5x ? 2
?
7x ? 3
,
(mod 13)
x ? 2 (mod 17)
6)
?
5x ? 3 (mod 9)
?
?
8x ? 4 (mod 14)
?
? 4x ? 1
(mod 10)
7) 2x ? 5 (mod 15)
?
7x ? 5 (mod 12)
?
? 5x ? 1
,
;
,
(mod 7)
4) 5x ? 4 (mod 11)
?
11x ? 8 (mod 13)
,
,
,
?
2x ? 7
?
?
?
(mod 16)
x ? 3 (mod 10)
?
x ? 9 (mod 14)
8)
,
,
(mod 9)
5x ? 3 (mod 7)
?
4x ? 5 (mod 12)
?
? 3x ? 1
10)
16
,
,
,
;
,
;
;
(mod 10)
4x ? 3 (mod 5)
?
2x ? 7 (mod 9)
,
.
,
ќ56. Найти наименьшее натуральное число, которое при делении на 7, 5, 3, 11 дает соответственно остатки 3, 2, 1, 9.
ќ57. Решить в целых числах уравнения:
1) 3x + 4y = 13;
2) 8x ? 13y = 63;
3) 7x ? 19y = 23;
4) 39x ? 22y = 10;
5) 17x ? 25y = 117;
6) 43x + 37y = 21;
7) 53x + 47y = 11;
8)
9)
10)
11)
12)
45x ? 37y = 25;
81x ? 48y = 33;
26x + 34y = 13;
122x + 129y = 2;
258x ? 172y = 56.
ќ58. Для перевозки зерна имеются мешки по 60 кг и по 80 кг.
Сколько нужно тех и других мешков для перевозки 440 кг зерна?
ќ59. Ставится водопровод протяженностью 105 м; имеются
трубы длиной 3 и 4,5 м. Сколько нужно поставить тех и других
труб?
ќ60. Сколько билетов по 30 коп. и по 50 коп. можно купить
на 14 руб. 90 коп.?
ќ61. Сколько почтовых марок по 3 коп. и по 4 коп. можно
купить на 50 коп.?
ќ62. Решить следующие уравнения:
1) 38x+117y = 209; 2) 122x+129y = 2; 3) 119x?68y =
34; 4) 258x ? 175y = 113; 5) 41x + 114y = 5.
17
Контрольные работы
1. Найти НОД и НОК двух чисел применением алгоритма Евклида.
2. Найти НОД и коэффициенты x и y применением расширенного алгоритма Евклида к двум числам.
3. Решить линейное диофантово уравнение от двух переменных ax + by = c (в ответе выделить x0 минимальное неотрицательное решение).
4. Найти функцию Эйлера ?(m) от заданного числа.
5. Решить сравнение первой степени ax ? b (mod m).
6. Решить систему из двух сравнений первой степени
{
x ? a (mod m1 )
.
x ? b (mod m2 )
7. Решить систему из трех сравнений первой степени применением китайской теоремы об остатках
?
?x ? a
(mod m1 )
x ? b (mod m2 ) .
?
x ? c (mod m3 )
Примеры заданий
ќ
1
2
3
4
5
6
7
Задание
846 406
661 249
608x + 202y = 8
5304
372x
? 126 (mod 414)
{
x ? 3 (mod 14)
? x ? 9 (mod 26)
? x ? 3 (mod 11)
x ? 21 (mod 26)
?
x ? 8 (mod 31)
Ответ
(846,406)=2 [846,406]=171738
{661 · 55 + 249 · (?146) = 1
x = 4 ? 101n
, n?Z
y = ?12 + 304n
?(5304) = 1536
x ? 66 + 69i (mod 414), i ? [0, 5]
x ? 87 (mod 182)
x ? 6053 (mod 8866)
18
Литература
1. Виноградов И. М. Основы теории чисел. М.: Наука, 1965.
2. Бухштаб А. А. Теория чисел. М.: Просвещение, 1966.
3. Акритас А. Основы компьютерной алгебры с приложениями.
М.: Мир, 1994.
4. Грибанов В. У., Титов П. И. Сборник упражнений по теории
чисел. М.: Просвещение, 1964.
19
Документ
Категория
Без категории
Просмотров
0
Размер файла
154 Кб
Теги
fedorenko3
1/--страниц
Пожаловаться на содержимое документа