2

I'm having some trouble with the following:

Find integers x and y in the set $\{0, 1, 2, 3, 4\}$ such that

$$ 2x - 4y \equiv 1 \pmod 5 $$ $$ 3x + y \equiv 2 \pmod 5 $$

Well I'm a little confused on how to solve for a system of linear congruence. I know that $a\equiv b \pmod m$ is the same as $a=km+b$. However, this doesn't tell me much when the variable $y$ comes into play... Is there a specific way to set this up?

Dimitri
  • 1,287

2 Answers2

0

Yes, the standard way to do this would be to "play" with the two equations so you can cancel one term with the other one. For two equations is easy. For example, multiply the first equation by $-3$ and the second one by $2$ you get: $$ -6x+12y \equiv -3 \pmod 5 $$ $$ 6x+2y \equiv 4 \pmod 5 $$ sum the two equations to get: $$ 14y \equiv 1 \mod 5 $$ but $10y\equiv 0$ so you obtain $$ 4y \equiv 1 \mod 5 $$ from where the value of the variable $y$ can be obtained. You can do the same for $x$. To solve this last one you can find the inverse of $4$ modulo $5$, which happens to be $4$ itself since $4\cdot 4=16\equiv 1$ mod $5$ (when it is not evident use euclid's algorithm). Then multiplying the last equation by $4$ you get $$ y \equiv 4 \pmod 5 $$ you can obtain $x$ from there simply by substitution in the original equations. For example in the first one you get: $$ 2x \equiv 1+4y \equiv 1 + 1 \equiv 2 \pmod 5$$ Since $2$ and $5$ are relative primes you can cancel the number $2$ to get $x\equiv 1 \pmod 5$.

Mauricio Tec
  • 2,624
  • Your solution used the incorrect second equation prior to correction. As it stands, you have $0\equiv 1 \pmod 5$, which is a contradiction. – Glen O Sep 18 '13 at 04:09
  • going to change it I have realized thanks – Mauricio Tec Sep 18 '13 at 04:10
  • @MauricioGTec great! So I can basically "manipulate" equations to cancel each other out, correct? – Dimitri Sep 18 '13 at 04:27
  • 1
    Yes but there are some cavaets. For example: $2x \equiv 3 \pmod 4$ has no solution. That is beceause the gcd of $2$ and $4$ is $2$ which does not divide $3$. But you will win practice soon though. – Mauricio Tec Sep 18 '13 at 04:31
0

Hint: Try subtracting the first equation from the second. Note that $5\equiv 0\pmod5$.

Glen O
  • 12,425