solve system of linear congruences mod 13 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?
 A: 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$.
A: $$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$$
A: $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$
A: 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$.
A: 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.
