Find $y$ satisfying $17y = 1 \mod (130)$

Question

Let $x=17$ $n=130$. Find $y; (1\leq y \leq n-1)$ that satisfies :$$xy=1 \pmod n$$ Now I'm not sure if I should use one of Euler's theorem's for prime numbers? Can anyone help? Or try something with $xy=kn+1 $?

Answer 1

Euclidean Algorithm and substitution is enough here:

$17y=130k+1$

$17y_1=130k-(17)(7k)+1$

$17y_1=11k+1$, or $17y_1-1=11k$

$6y_1-1=11k_1$

It is easy to see that the above has $y_1=2$ and $k_1 = 1$ (you could keep bringing the coefficients down up to 1 if the numbers were bigger).

$6\cdot 2-1=11$

$6\cdot2 + 11\cdot2 - 1 = 11+11\cdot2$, or $17\cdot2 -1 = 11\cdot3$ meaning that $k=3$.

$17\cdot2 = 11\cdot3 + 1$

$17\cdot2 + (17)(7\cdot3) = 11\cdot3 + (17)(7\cdot3) + 1$

$17\cdot23 = 130\cdot3 + 1$

So we have $y=23$.

Note that this approach is can be generalized for any $(x,y,n)$.

Answer 2

It follows that $xy = kn + 1$, where k is integer, or equivalently $y = \frac{kn+1}{x}$

Since $1\leq y \leq n-1$, we have: $1 \leq \frac{kn+1}{x} \leq n-1$

Solve for k, we have:

$\frac{x-1}{n} \leq k \leq \frac{x(n-1)-1}{n} $ or $1 \leq k \leq x-1$, for $x+1 \leq n$

Plug $n = 130,x=17 $, we have $1 \leq k \leq 16$

Now just trials and errors (I use Excel), only $k = 3$ gives integer value of $y = 23$

So $y=23$ is the only solution.

Answer 3

I used the python programming language. Code:

x=130
n=11
for y in range(1,n):
  if (x*y)%n==1:
    print y

The result I get is 5. We can check that indeed $x\times y = 130\times 5 = 650 = 59\times 11 + 1 = 1 (\text{mod } 11)$