Теория чисел и арифметика Здравствуйте! Нужна ваша помощь с решением.
Пусть N= [√30202020 + 20190 ⋅ 8] + 24*8=
K= [√20192019 − 20200 ⋅ 8] – 38*8 =
1. Вычислите НОД(;) по алгоритму Евклида и найдите целые и такие, что
xN + yK = НОД( (N;K).
Вычислите 2 ( в 8 степени ) mod (2*8 + 143).
3. Пусть наименьшие из целых чисел взаимнопростых с 2027 и не меньших N и K соотвественно. Решите
2027x ≡K' mod N'

Предыдущий
вопрос Следующий
вопрос

Для начала вычислим значения N и K:

N = [√30202020 + 20190 ⋅ 8] + 24*8
N = [√30202020 + 161520] + 192
N = [√30363540] + 192
N = 5514 + 192
N = 5706

K = [√20192019 − 20200 ⋅ 8] – 38*8
K = [√20192019 - 161600] - 304
K = [√20030419] - 304
K = 4473 - 304
K = 4177

Теперь найдем НОД(N,K) с помощью алгоритма Евклида:

5706 = 1 4177 + 1529
4177 = 2 1529 + 719
1529 = 2 719 + 91
719 = 7 91 + 62
91 = 1 62 + 29
62 = 2 29 + 4
29 = 7 * 4 + 1

Таким образом, НОД(N,K) = 1.

Далее находим целые x и y, удовлетворяющие уравнению xN + yK = НОД(N,K):

1 = 29 - 74
1 = 29 - 7(62-229)
1 = 29 - 762 + 1429
1 = 1529 - 762
1 = 1529 - 7(91-62)
1 = 1529 - 791 + 762
1 = 1529 - 791 + 7(1529-2719)
1 = 1529 - 791 + 71529 - 14719
1 = 1529 - 791 + 71529 - 14(20030419-4473304)
1 = 1529 - 791 + 71529 - 14(20030419-4473(20192019-388))
1 = 1529 - 791 + 71529 - 14(20030419-447320192019+4473304)
1 = 1529 - 791 + 71529 - 1420030419 + 14447320192019 - 144473*304
1 = -57292 - 31657 + 10603 + 2804256663 - 2825465859 + 28385057
1 = 12

Следовательно, x = -57292, y = -31657.

Далее вычислим 2^8 mod (16 + 143):

2^8 mod 159
256 mod 159
97

И, наконец, решим уравнение 2027x ≡ K' mod N':

Для начала найдем число K', которое является наименьшим целым числом, взаимнопростым с 2027 и большим или равным K:

K' = 4179

Теперь вычислим N':

N' = N - НОД(N,K)
N' = 5706 - 1
N' = 5705

Теперь нужно найти такое целое число x, для которого 2027x ≡ 4179 mod 5705.
Для этого можно воспользоваться расширенным алгоритмом Евклида.

Надеюсь, это поможет вам в решении задачи! Если у вас возникнут еще вопросы, не стесняйтесь обращаться.