For example:
$$63x \equiv 1 (mod 17)$$
I wanna find the multiplicative inverse here so that I can use this in the Chinese reminder theorem. Example:
$$x \equiv 2 (mod 3)$$
$$x \equiv 4 (mod 5)$$
$N=3*5=15$
$N_{1}=5$
$N_{2}=3$
x = 5*2*[multiplicative inverse of the first equation] + 3*4*[multiplicative inverse of the second equation]
Multiplicative inversions should be evaluated like this – $N_{1}x \equiv 1 (mod n_{1})$
So, back to the topic, the solution of the first equation in this post is $17k-7$…But what will the multiplicative inverse be? -7? 10? 27?
Best Answer
As you said, any number of the form $x=17k-7$ (where $k$) is an integer will be a valid solution to $$ 63x \equiv 1 \pmod {17} $$ But the real punchline is that when we talk about the numbers modulo $17$, the numbers $x=17k-7$ are all the same number.
To be more precise, the numbers $x=17k-7$ are all part of the equivalence class of $10$, where two numbers are equivalent when they have the same remainder under division by $17$. As it ends up, when you add and multiply numbers in modular arithmetic, the result is the same regardless of which representative you choose.
So, for this example, $10\equiv -7$ are the same valid solution to the equation. In fact, we can check to find that this is the case:
$$ 63\times10 \equiv 630 \equiv 1 + (37\times 17) \equiv 1 + 0 \equiv 1 \pmod{17}\\ 63\times(-7) \equiv -441 \equiv 1 + (26\times 17)\equiv 1 + 0 \equiv 1 \pmod{17} $$ In fact, we didn't even need to use the number $63$. Instead, we could have used the equivalent value $12\equiv63 \pmod{17}$. You'll find, as before, that $$ 12\times10\equiv 12\times(-7)\equiv 1 \pmod{17} $$ I hope that I've cleared things up.