Элементы теории чисел и криптозащита. Воронков Б.Н - 13 стр.

UptoLike

ВУЗ: 

ВГУ | Воронеж

Составители: 

Рубрика: 

13
a
1
(X – x ) = – b
1
(Y – y) и покажите, что X = x + kb, Y = y – kb для некоторого
целого числа
k.
3. Найдите основные решения каждого из следующих уравнений
7
x + 5y = 17; 6x + 9y = 33; 6x + 12y = 36.
4. Пусть
a и b – положительные числа, и a не делит b, b не делит a.
Покажите, что целые числа
x и y могут быть выбраны таким образом, что
ax + by = (a , b), где 1 ≤ x ≤ b – 1 и 1 ≤ y ≤ а – 1.
5. В виде приложения к заданию 4 рассмотрите кусок бумаги шири-
ной 1 м, который поделен на
a одинаковых полосок a – 1 красными линия-
ми с одинаковыми промежутками и параллельными между собой (
а ≥ 2) и
также разделен на (
b ≥ 2) равных линий с помощью b – 1 голубых полосок с
одинаковыми промежутками и параллельными по отношению к красным
линиям. Принимая, что
a не делит b и b не делит a, покажите, что мини-
мальным ненулевым расстоянием между красными и голубыми линиями
будет (
a, b)/ab (м).
6. Теперь рассмотрим уравнение в целых числах
ax + by + cz = d, (3)
где мы предположили, что (
a, b, c) | d, чтобы это уравнение имело какое-
нибудь решение. Вспоминая, что (
a, b, c) = (a, (b, c)) (см. выше задание 8 уп-
ражнения 2.1), мы знаем, что существуют
x
0
и u
0
, удовлетворяющие уравне-
нию
ax
0
+ (b, c)u
0
= d. Известно, что существуют числа y
0
и z
0
, удовлетворяю-
щие уравнению
by
0
+ cz
0
= (b, c). Найдем общее решение уравнения by +
+ cz = k
(b, c) для некоторого фиксированного k и, отсюда, получим общее ре-
шение выражения (3) для произвольных целых чисел
s и t:
x = x
0
+
(,)
(,,)
bc
s
abc
,
y = uy
0
–
(,,)
as
abc
y
0 +
c
t,
(b,c)
z = uz
0
–
(,,)
as
abc
z
0
–
b
t.
(b,c)
7. Найдите решения следующих диофантовых уравнений:
2
x + 6y – 8z = 0; 2x + 6y – 8z = 2; 7x – y + 3z = – 2.
Найдите все неотрицательные решения уравнения 2
x + 5y + 10z = 100;
возможные комбинации 2р, 5р и 10р, где р – копейки, дающие в сумме один
рубль. (Или, разумеется, подобные комбинации центов (пенсов), которые в
сумме дают один доллар (фунт)!).
Перед тем, как написать программу для решения диофантовых урав-
нений, нам необходим надёжный метод нахождения целых чисел
s и t, для
которых
as + bt = (a, b). Это обеспечивается следующим результатом.
3.12. Теорема. Определим целые числа s
i
и t
i
для i = 0, 1, 2, . . . таким
образом: s
0
= 1, s
1
= 0, t
0
= 0, t
1
= 1 и для i ≥ 2,
s
i
= s
i-2
– q
i–1
s
i–1
, t
i
= t
i–2
– q
i–1
t
i–1
.

Страницы