2
$\begingroup$

I'm trying to wrap my head around this:

$a \equiv b^{-1}\pmod{y}$

$x \equiv c^{-1} \pmod{y}$

I know all values but $x$ and $y$. Is it possible to solve this problem for $x$? Can anyone point out a good resource on this kind of problems?

1 Answers 1

3

If $b,c$ have an inverse in $\pmod y$ then is valid :$$ ab\equiv 1 \pmod y $$ and $$ xc\equiv 1 \pmod y $$ From this you get: $$ ab-1 = k_{1}y $$ $$ xc-1 = k_{2}y $$

(For some $k_{1}$ and $k_{2}$ integers )

So you can find $x$ and $y$ from this ecuations system.

$Edit:$

For example,

If $y=5$, the elements with inverse are: $2,3$, also $b=2$ and $b^{-1}=3$.

Know that (with $a=8$ ):

$ 8 \equiv 3 \pmod 5 $, is say , $ a \equiv b^{-1} \pmod y $,

Note that also:

$ 16 =8 \cdot 2\equiv 1 \pmod 5 $, is say , $ ab \equiv 1 \pmod y $

  • 0
    what are $k_1$ and $k_2$?2010-11-28
  • 0
    @Chris Remember that: $$a\equiv b \mod y \Leftrightarrow y\setminus(a-b) $$2010-11-28