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

UptoLike

ВУЗ: 

ВГУ | Воронеж

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

Рубрика: 

6
Докажите, что если a | n, b | n и (a, с) = 1, то ab | n. [Это может быть
сделано прямо из разложения на простые сомножители или записью в виде
ra = sb = n с использованием свойства (a, b) = 1, чтобы показать, что a | s ].
Покажите, что если a | b и (b, с) = 1, тогда (a, с) = 1.
2. Докажите,
что если a | b , то (a, b) = | a | .
3. Покажите, что если (a, b) = 2 и a | k , b | k, то ab | 2k. Приведите
пример, показывающий, что произведение ab может не делить k .
4. Докажите, что если 1 ≤ r ≤ p–1, где p – простое число, то (r!, p) = 1.
Покажите при этом, что биномиальный коэффициент
! ( 1)...( 1)
!( )! !
p
ppppr
r
rpr r
⎛⎞
−
−+
==
⎜⎟
−
⎝⎠
кратен p .
Предположим, что n не является простым числом, скажем, n = k p
s
,
где p – простое число, p не делит k, а также k > 1 или s > 1, тогда
n
p
⎛⎞
⎜⎟
⎝⎠
не де-
лится на n, т. е. представляет собой некоторый, отличный от нуля, биноми-
альный коэффициент, не кратный n.
5. Предположим, что a, b, x, y – ненулевые целые числа и x/a = y/b (эти
дроби необязательно должны быть целыми числами!). Пусть h = (a, b) и
пусть a = a
1
h, b = b
1
h для целых чисел a
1
, b
1
. Докажите, что x = ka
1
, y = kb
1
для некоторого целого k. Используйте известное свойство (или докажите
сами), что если a | bс и (a, b) = 1, тогда a | с. [Условие, что (a, b) = 1 нельзя
ослабить до «а не является делителем b». Убедитесь в этом при а = 4, b = 2,
с = 6].
6. Пусть a, b, c, d – положительные числа, (a, b) = 1 и
(c, d) = 1, так что
дроби
a
b
и
c
d
несократимы. Предположим, что
a
b
+
c
d
является целым чис-
лом. Покажите, что b = d.
7. В качестве варианта задания 4 рассмотрите прямоугольник разме-
ром a × b (a, b – натуральные числа), разделенный на ab квадратов сеткой
линий, параллельных его сторонам, в котором проведена диагональ. Пока-
жите, что диагональ точно проходит через узлы сетки с координатами x =
= ka
1,
y = kb
1
для k = 0,h . Докажите, что диагональ пересекает точно a +
+
b – (a, b) ячеек сетки.
8. Заданы три натуральных числа
a, b и с. Покажите, исходя из разло-
жения на простые сомножители в соответствующих степенях, что ((
a, b),
c) = ((c, a), b). Общее значение этих трех чисел, записываемое как (a, b, c),
называется НОД
a, b и c. Докажите, что ((a, b), (a, c)) = (a, b, c).
9.* Пусть
a, b, c, x, y, z являются натуральными числами. Предполо-
жим, что
x/a = y/b = z/c. Пусть h = (a, b, c), а a = a
1
h, b = b
1
h, c = c
1
h. По-
кажите, что (
a
1
, b
1
, c
1
) = 1. Используя тот факт, что ((a
1
, b
1
), (a
1
, c
1
)) = 1 и,
учитывая задание 1, доказать, что
x = ka
1
, y = kb
1
, z = kc
1
для целого числа k.

Страницы