-2
$\begingroup$

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 ?

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

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.