Find $y$ satisfying $17y = 1 \mod (130)$ 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 $?
 A: 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)$.
A: 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.
A: 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)$
