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

I have this equation :

132 * y = 17 (modulo 35 )

How do I find y?I suspect that there is no solution ,but how do i prove this ?

• What have you tried to solve the problem yourself? Where did you get stuck? What did you try to do to unstuck yourself? – AmagicalFishy Jun 17 '17 at 10:26
• what have you done and use latex. In the title does that mean something? – MAN-MADE Jun 17 '17 at 10:26
• Use proper formatting for your posts here. And show your work, whatever you have done. – StubbornAtom Jun 17 '17 at 10:29
• @Oana, I believe that your assumption about the non-existence of the decision you made at random – Minz Jun 17 '17 at 10:41

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$.

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$.

By employing $$\rm\color{#c00}{even\ reps}$$ to divide by 2 (or 4) the modular fraction is easily mentally computable:

$${\rm mod}\ 35\!:\ \dfrac{17}{132}\equiv\dfrac{\color{#c00}{-18}}{-\color{}8}\equiv \dfrac{9}4\equiv \dfrac{\color{#c00}{44}}4\equiv 11$$

The key idea is: if the modulus $$m$$ is odd then $$\,2\mid a\,$$ or $$\,2\mid \color{#c00}{a\!\pm\!m},\,$$ so we can quickly divide $$\,a\,$$ by $$\,2\,$$ by choosing a rep that is even. Iterating that we can easily divide by all powers of $$\,2\,$$ (e.g $$\,8\,$$ above).

Alternatively it's very simply computed by the fractional extended Euclidean algorithm

$${\rm mod}\,\ 35\!:\,\ \dfrac{0}{35} \overset{\large\frown}\equiv \dfrac{17}{-8} \overset{\large\frown}\equiv \dfrac{-2}3\overset{\large\frown}\equiv\dfrac{11}1$$

Beware $$\$$ Modular fraction arithmetic is well-defined only for fractions with denominator coprime to the modulus. See here for further discussion.

Just like you solve ordinary linear equations. You multiply both sides by the inverse of $132$. We need to find some number $d$ such that $d\cdot 132 = 1\mod 35$. For this you can use Euclid's algorithm since that equation is the same as $$132d-35k=1$$

Alternatively, since 35 is not very large you can try $d=1,2,3,...,34$ to see which one works.