In asymmetric cryptography (such as RSA key derivation), one requires finding the unique modular multiplicative inverse x in the finite field $\mathbb{Z}_{17}$ such that (7 * x) mod 17 = 1.
Principles it rests on
Modular Arithmetic: Congruences are computed over the ring $\mathbb{Z}_p$ under addition and multiplication modulo $p$.
Bรฉzout's Identity: For $\gcd(a, p) = 1$ there exist integers $x, y$ with $a x + p y = 1$.
Existence and Uniqueness: An inverse in $\mathbb{Z}_p^\times$ exists only when $a$ is coprime to the modulus, and is then unique.
Question
What is the unique modular multiplicative inverse of 7 modulo 17?
Solution
1. Define the Congruence Equation for the Multiplicative Inverse:
We seek the unique integer $x \in \{1, 2, \dots, 16\}$ satisfying the linear congruence:
$7 \cdot x \equiv 1 \pmod{17}$
Equivalently, this means $7 x - k \cdot 17 = 1$ for some integer $k$.
2. Apply Bรฉzout's Identity and Fermat's Little Theorem:
Because $17$ is prime and $\gcd(7, 17) = 1$, Bรฉzout's identity guarantees that a unique solution exists modulo $17$.
By Fermat's Little Theorem, for any integer $a$ coprime to prime $p$:
$a^{p-1} \equiv 1 \pmod p \implies a \cdot a^{p-2} \equiv 1 \pmod p$
Therefore, the modular inverse is given by $x \equiv 7^{17-2} \pmod{17}$.
3. Compute and Verify Step-by-Step Arithmetic:
Evaluating the product with target inverse $x = 5$:
$7 \times 5 = 35$
Dividing by modulus $17$:
$35 = 2 \times 17 + 1$
Thus, $7 \times 5 \equiv 1 \pmod{17}$.
4. Conclusion:
The unique modular inverse of $7$ modulo $17$ is 5.
python
import sympy as sp
p = 17
a = 7
inv = sp.mod_inverse(a, p)
print(f"Inverse: {inv}")
assert (a * inv) % p == 1
print(inv)
How others did
Nobody has tried this yet.Be the first. Your answer starts the stats.
Only each person's first answer, given before viewing the solution, is counted.
Discussion 0 comments
Log in to join the discussion.