how to solve an equation (132 * y = 17 (modulo 35 )) modulo i [closed]

Solution 1:

Euclid's algorithm

$$132=35\cdot 3 + 27$$ $$35 = 27\cdot 1 + 8$$ $$27 = 8\cdot 3 + 3$$ $$8 = 3\cdot 2 + 2$$ $$3 = 2\cdot 1 + 1$$

Now we substitute the previous equations into the last one.

$$3 = (8-3\cdot2)\cdot1 + 1$$ $$(27-8\cdot 3) = (8-3\cdot2)\cdot1 + 1$$ and so on until

$$13\cdot132 - 35\cdot 49 = 1$$ that tells you that $13$ is the inverse of $132$ mod $35$. Therefore the solution is $y=13\cdot17$.

Solution 2:

We want to solve the equation $$ 132y+35x=17 $$ so first we solve the equation $$ 132y+35x=1 $$ and multiply the particular solution by $17$. Using the extended Euclidean algorithm detailed in this answer, we get $$ \begin{array}{r} &&3&1&3&2&1&2\\\hline 1&0&1&-1&4&-9&\color{#C00}{13}&\color{#C00}{-35}\\ 0&1&-3&4&-15&34&-49&132\\ \color{#090}{132}&\color{#090}{35}&27&8&3&2&1&0\\ \end{array} $$ which says that $y=13-35k$ for $k\in\mathbb{Z}$. Multiplying the particular solution by $17$, we get the final solution to be $$ y=221-35k $$ Setting $k=6$, gives the smallest positive solution to be $y=11$.