4
$\begingroup$

Given the system: $$ 2x+5y \equiv 1 \textrm{mod} 13 $$ $$ 5x+y \equiv 2 \textrm{mod} 13 $$

What is the value of $$ 5x+7y \equiv \textrm{mod} 13 $$?

do I have to solve the first two equations, i.e., $x=11+5t, y=1-2t$ for the first equation, do the same for the second, obtain the common values of $x, y $, and do the calculation? or is there other method?

$\endgroup$

5 Answers 5

Reset to default
6
$\begingroup$

You don't have to solve the first two equations. $5x+7y=(5+26)x+(7+13)y=3(2x+5y)+5(5x+y)=3+10=0 \mod 13$.

$\endgroup$
2
  • $\begingroup$ This is way shorter and nicer than my answer. +1 $\endgroup$
    – DonAntonio
    Commented Oct 12, 2012 at 23:58
  • 3
    $\begingroup$ Of course, finding the coefficients 3 and 5 requires solving a linear system of two equations and two unknowns.... $\endgroup$
    – user14972
    Commented Oct 13, 2012 at 0:35
3
$\begingroup$

$$I\;\;\;\;\;2x+5y=1\pmod {13}$$

$$II\;\;\;\;5x+2y=2\pmod {13}$$

Multiply eq. I by -5 and eq.II by 2 and add the results (for simplicity all the following is done modulo 13):

$$(-5)\cdot I\;\;\;\;\;-10x-25y=-5$$

$$2\cdot II\;\;\;\;\;\;\;10x+4y=4$$

$$-21y=-1\Longrightarrow y=\frac1{21}=\frac18=5$$

And substitute now, say in I:

$$2x+5(5)=1\Longrightarrow2x=-24=2\Longrightarrow x=1$$

$\endgroup$
4
  • $\begingroup$ In my textbook, multiplication by a scalar m on $a \equiv b \pmod{c}$ gives $am \equiv bm \pmod{mc}$. Why is it that you don't multiply the modulus number $13 $in the beginning of your solution? $\endgroup$
    – TheRealFakeNews
    Commented Jun 3, 2013 at 0:21
  • 1
    $\begingroup$ Either your textbook means something different or else that's a mistake: one cannot usually change the modulo at will. We're working modulo $\,13\,$ and we stay all the time within modulo $\,13\,$ . $\endgroup$
    – DonAntonio
    Commented Jun 3, 2013 at 0:23
  • $\begingroup$ Ah, okay. Thanks. Btw, when you multiply $-5$ to equation $I$, did you mean to write $-5$ on the RHS? $\endgroup$
    – TheRealFakeNews
    Commented Jun 3, 2013 at 0:26
  • $\begingroup$ Oh, dear: yes, thanks for noting that. I already corrected it. $\endgroup$
    – DonAntonio
    Commented Jun 3, 2013 at 0:36
2
$\begingroup$

$2x+5y\equiv 1\pmod{13}\implies 2x+5y=1-13a$

$5x+y\equiv 2\pmod{13}\implies 5x+y=2-13b$ for some integers $a,b$.

Solving for $x,y,$ we get, $x=\frac{9+13(a-5b)}{23},y=\frac{1+13(2b-5a)}{23}$

$23(5x+7y)=5(9+13(a-5b))+7(1+13(2b-5a))\equiv 5\cdot9+7\pmod{13}\equiv 0$

$\implies 5x+7y\equiv 0\pmod{13} $ as $(13,23)=1$

Had $ 5x+7y$ not been $\equiv 0\pmod{13} $ we needed to multiply the RHS with $(23)^{-1}\pmod{13}\equiv (-3)^{-1}$.

Now, $(-3)^2=9,(-3)^3=-27\equiv -1\pmod{13}\implies (-3)^{-1}\equiv -(-3)^2\equiv 4$

$\endgroup$
1
$\begingroup$

In general for this type problem:

$ax+by=c$

$dx+ey=f$

$gx+hy=z$

To find: the value of $z$ without first finding $x,y$.

Calculate the determinant of the matrix with rows

$[a, b, c]$

$[d, e, f]$

$[g, h, z].$

Multiply it out and get the factor in front of z (this better be nonzero mod n), and move the numerical terms of the determinant to the other side. Now divide by what's in front of $z$ to get $z$ mod $n$.

For the above example the rows are [2,5,1],[5,1,2],[5,7,z] and the determinant is $-23z+52.$ So z = 52/23 = 0 since 13 divides 52 and 23 isn't zero mod 13. In general this method involves finding the inverse mod $n$ of the coefficient of $z$

The reason the method works is that the three equations are equivalent to saying that the three rows of the matrix are all orthogonal to the vector $[x,y,-1]$. Therefore they lie in a two dimensional subspace of $R^3$ and are linearly dependent, making the determinant $0$.

$\endgroup$
0
$\begingroup$

To make the technique explicit (using coffeemath's nomenclature):

You are given knowns $a, b, c, d, e, f, g$ and $h$ and unknowns $x$ and $y$ such that (all equalities are modulo some prime $p$) $a x + b y = c$ and $d x + e y = f$, and you want to evaluate $g x + h y$ without first determining $x$ and $y$.

A way to do this is to find values $u$ and $v$ such that $u$ times the first equation plus $v$ times the second equation gives, for the left-hand side, the left-hand side of the third equation. Then, the resulting right-hand side gives the desired result (again, all computations are modulo $p$).

So, we want (with a little abuse of notation) u(a x+b y = c) + v(d x + e y + f) = g x + h y = ?$.

This produces the two equations $u a + v d = g$ and $u b + v e = h$ to be solved for $u$ and $v$. Once you have done this, the value you want is $u c + v f$, from the right-hand sides.

$\endgroup$
1
  • $\begingroup$ Yes, and the determinant just does the calculation without first finding your values u,v. Essentially the same idea. But perhaps one less thing to determine along the way, but one more thing to do at the end of determinant approach, namely find an inverse of a number mod n. It may for large modulus n be just as difficult to find your u,v as to find the required inverse of the coefficient of z in the determinant method... $\endgroup$
    – coffeemath
    Commented Oct 13, 2012 at 1:27

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .