0
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ If so, then what should I substitute as the inverse variable in the Chinese reminder theorem final formula, as in my example? Anything from $17k - 7$? $\endgroup$ – khernik Aug 15 '13 at 23:10
  • 1
    $\begingroup$ Yep, anything from there will work, and will give you the same answer modulo $n_1n_2$. I personally would use $10$ to make the multiplication easier. $\endgroup$ – Omnomnomnom Aug 15 '13 at 23:14
2
$\begingroup$

For example:

$$63=12\pmod{17 }\;,\;\;12\cdot7=84=-1\pmod{17}\implies -7=10=12^{-1}\pmod{17}$$

and from here

$$63x=1\pmod{17}\implies 12x=1\pmod{17}\implies x=12^{-1}=10\pmod{17}$$

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.