0

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

modlim
  • 1
  • 2
    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. – Pedro Sep 23 '13 at 23:02
  • We need to know what you’ve tried, and how much you know. – Lubin Sep 23 '13 at 23:08
  • ($\mod 99$ changed to $\mod 12$) – Pedro Sep 23 '13 at 23:34
  • 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 – Stefan4024 Sep 24 '13 at 00:19

1 Answers1

3

$\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}$$

amWhy
  • 209,954