Чтобы найти 1:49mod 100 1:49 \mod 100 1:49mod100, сначала нужно перевести деление в умножение. При этом мы будем искать значение 49−1mod 100 49^{-1} \mod 100 49−1mod100обратныйэлементк49помодулю100обратный элемент к 49 по модулю 100обратныйэлементк49помодулю100, а затем умножим его на 1.
Для нахождения обратного элемента можно использовать расширенный алгоритм Евклида. Сначала найдем gcd(49,100) \text{gcd}(49, 100) gcd(49,100).
Чтобы найти 1:49mod 100 1:49 \mod 100 1:49mod100, сначала нужно перевести деление в умножение. При этом мы будем искать значение 49−1mod 100 49^{-1} \mod 100 49−1mod100 обратныйэлементк49помодулю100обратный элемент к 49 по модулю 100обратныйэлементк49помодулю100, а затем умножим его на 1.
Для нахождения обратного элемента можно использовать расширенный алгоритм Евклида. Сначала найдем gcd(49,100) \text{gcd}(49, 100) gcd(49,100).
100=2⋅49+2 49=24⋅2+1 2=2⋅1+0 100 = 2 \cdot 49 + 2 \
49 = 24 \cdot 2 + 1 \
2 = 2 \cdot 1 + 0
100=2⋅49+2 49=24⋅2+1 2=2⋅1+0
Поскольку gcd(49,100)=1 \text{gcd}(49, 100) = 1 gcd(49,100)=1, обратный элемент существует.
Теперь применим обратный алгоритм Евклида:
1=49−24⋅2 2=100−2⋅49 1 = 49 - 24 \cdot 2 \
2 = 100 - 2 \cdot 49
1=49−24⋅2 2=100−2⋅49
Подставляем 2 2 2 во второе уравнение в первое:
1=49−24(100−2⋅49) 1=49−24⋅100+48⋅49 1=49⋅49−24⋅100 1 = 49 - 24(100 - 2 \cdot 49) \
1 = 49 - 24 \cdot 100 + 48 \cdot 49 \
1 = 49 \cdot 49 - 24 \cdot 100
1=49−24(100−2⋅49) 1=49−24⋅100+48⋅49 1=49⋅49−24⋅100
Таким образом, 49⋅49≡1mod 100 49 \cdot 49 \equiv 1 \mod 100 49⋅49≡1mod100. Значит, обратный элемент к 49 мод 100 равен 49.
Теперь мы можем найти 1:49mod 100 1:49 \mod 100 1:49mod100:
1⋅49≡49mod 100 1 \cdot 49 \equiv 49 \mod 100
1⋅49≡49mod100
Итак, 1:49mod 100 1:49 \mod 100 1:49mod100 равно 49 49 49.