0
$\begingroup$

I am having trouble finding mod arithmetic questions.

Can you show how to solve these?

$x + 30 \equiv 1 \pmod {12}$

$30x \equiv 1 \pmod {12}$

$x + 3y \equiv 1 \pmod {12}$ and $2x + y \equiv 7 \pmod {12}$

$\endgroup$
  • 2
    $\begingroup$ Where are you stuck? Can you solve $x+30=1$ in general? Can you find a number $k$ such that $30k=99j+1$ for some integer $j$? Use the Euclidean algorithm. Can you invert a matrix in $\Bbb Z_{11}$? If not, can find say an inverse of $2$, modulo $11$, to change your second equation into $x+ay=b\mod 11$ and subtract fro the first? Don't expect people to just do your homework here. $\endgroup$ – Pedro Tamaroff Sep 23 '13 at 23:02
  • $\begingroup$ We need to know what you’ve tried, and how much you know. $\endgroup$ – Lubin Sep 23 '13 at 23:08
  • $\begingroup$ ($\mod 99$ changed to $\mod 12$) $\endgroup$ – Pedro Tamaroff Sep 23 '13 at 23:34
  • $\begingroup$ If the modulo is 12, then the second equation doesn't have a solution, because for any $x$ the LHS is even, while the RHS is odd. And when the modulo is even that implies that there aren't solution $\endgroup$ – Stefan4024 Sep 24 '13 at 0:19
2
$\begingroup$

$\begin{align} x + 30 & \equiv 1 \pmod {12} \\ \\ x + 30 - 30 &\equiv 1 - 30 \pmod{12} \\ \\ x \equiv -29 \pmod{12} \end{align}$.

Now, we can add any multiple of 12 to $-29$ if we want to find $x \in \{0, 1, 2, \ldots, 10, 11\}$. Specifically, we find that $-29 + 3\cdot 12 = -29 + 36 = 7$. So $x \equiv -29 \equiv 7 \pmod {12}$.


For the next question, we need to find the multiplicative inverse of 30 (modulo $12$) to clear the coefficient of $x$.

$$30x \equiv 1 \pmod {12}$$

Indeed, in this situation, no solution exists.

So, for practice, let's solve $$30x \equiv 1 \pmod {11}$$

$$\dfrac 1{30} \equiv \dfrac {1 + 9\cdot 11}{30} = \frac{100}{30} \equiv \dfrac{100 + 10\cdot 11}{30} = \dfrac {210}{30} = 7$$

This means that $7$ is the multiplicative inverse of $30 \pmod{11}$: $7\cdot 30 \equiv 1 \pmod 11$:

$$7 \cdot 30 x\equiv 7\cdot 1 \pmod{11} \iff x \equiv 1 \pmod {11}$$

$\endgroup$
  • $\begingroup$ Why does this have no TU's? Not now +1 $\endgroup$ – Amzoti Sep 27 '13 at 2:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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