The question is from the following two problems:

Let $x$ and $y$ be positive integers such that $3x+7y$ is divisible by $11$. Which of the following must also be divisible by $11$?
A. $4x+6y$ B. $x+y+5$ C. $9x+4y$ D. $4x-9y$ E. $x+y-1$

If $x,y$ and $z$ are positive integers such that $4x-5y+2z$ is divisible by $13$, then which one of the following must also be divisible by $13$?
A. $x+13y-z$ B. $6x-10y-z$ C.$x-y-2z$ D.$-7x+12y+3z$ E. $-5x+3y-4z$

One way I know is that one can substitute some specific number to rule out the wrong answers. Or alternatively, one can try the properties of congruence(addition and subtraction), which I think is not easy to figure out the steps. Just as for the second problem, how on earth can one figure out one needs to add $$-39x\equiv 0\pmod{13}$$ $$65y\equiv 0\pmod{13}$$ $$13z\equiv 0\pmod{13}$$ to $$4x-5y+2z\equiv 0\pmod{13}$$ and then divides by $5$ in order to get the answer $$-7x+12y+3z\equiv 0\pmod{13}?$$

So, here is my question:

Is there a general method (which might be also quick) to solve this kind of problems?

-
This looks like an old GRE question! – mixedmath Jun 27 '11 at 4:36
You have a typo in the statement of the second problem (made apparent by your answer); it should be "$4x-5y+2z$ divisible by $13$", not $4x+5y+2z$. In the latter case, no answer is guaranteed. – Arturo Magidin Jun 27 '11 at 4:46
@Arturo: Corrected. Thanks. – Jack Jun 27 '11 at 4:52

There are general methods, and in this case there is even a quick one. But in general the "specific numbers" strategy you mentioned is well-suited for this kind of test, in which you have to solve too many too easy problems in too little time.

Below is my strategy. Real multiple choice test survivors can undoubtedly supply better ones.

For the first problem, I would find some particular numbers $x$ and $y$, not both $0$, such that $3x+7y \equiv 0 \pmod{11}$. My immediate choice is the no thinking $x=7$, $y=-3$. This quickly kills all possibilities except D. (I might kill B and E by using $x=y=0$.)

For the second problem, same thing. Let $x=4$, $y=5$, $z=0$. The $z=0$ is to forget about $z$. Got unlucky, D and E are still alive. So pick $x=0$, $y=2$, $z=5$. That kills E.

As to general methods, for linear algebra reasons, if we know that $ax+by\equiv 0\pmod{p}$, where $p$ is prime, we cannot have $cx+dy \equiv 0 \pmod{p}$, with the unless $ad-cb \equiv 0\pmod{p}$. With some care, the idea can be extended to non-prime moduli. So a few quick determinant calculations modulo $11$ also give the answer to the first problem. (The constant terms in B and E kill these as choices, so we needn't bother with them.)

In the second problem, since any variable could be set to $0$, there cannot be a solution unless all $2$ variable problems obtained by setting one variable to $0$ have a solution. This brings us back to calculations like those in the preceding paragraph. But to rule out some possibilities, we may have to do more than one determinant calculation.

My preference is substitution rather than determinant calculations. From the point of view of arithmetic, they are of equal difficulty, indeed identical. But substitution is something you have better intuition about, it is "theory-free."

Added: In the $3x+7y$ problem, I immediately jumped to using $x=7$, $y=-3$. We could replace $7$ by $-4$, and use $x=3$, $y=4$. We could in addition replace $3$ by $-8$, obtaining $(-8x)+(-4y)$, which is equivalent to $2x+y$, and we can use $x=1$, $y=-2$. These changes make the subsequent arithmetic simpler. Should we "invest" in such simplifications? It depends on how comfortable we are with mental arithmetic. My gut reaction is not to invest, I could make a minus sign error, and blow everything. Act, don't think, and go on to the next question.

-
Your comment on "linear algebra reasons" only works for $m$ prime. In general, you need $ad-cb$ prime with $m$. – lhf Jun 27 '11 at 19:48
@lhf: Thanks. Answer modified. – André Nicolas Jun 27 '11 at 22:25

If $N|Ax+By$ implies $N|Cx+Dy$ then also $N|CAx+CBy$ and $N|CAx + DAy$, hence $N|(AD-BC)y$ and so $N|AD-BC$. For example, in the first question answer $C$, $7 \cdot 4 + 3 \cdot 9 = 55$ is divisible by $11$.

Another way of looking at that is that $(C,D)$ must be some multiple of $(A,B)$. So $C/A = D/B$, which can be tested via $CB=AD$.

If you have more than two variables, say $N|Ax+By+Cz$ implies $N|Dx+Ey+Fz$ then the same method gives $A/D=B/E=C/F$ and so $AE=BD$ and $BF=CE$. Try it on the second question.

-
+1 Very nice. Essentially $(C,D)$ must be 'orthogonal' to the same set of vectors in $\mathbf{Z}_{11}^2$ as $(3,7)$ is, so these two need to be linearly dependent. – Jyrki Lahtonen Jun 27 '11 at 6:51

HINT $\ \ \mathbb F = \mathbb Z/11\:$ and $\:\mathbb Z/13\:$ are fields, so $\rm\:\mathbb F^{\:n}\:$ is a vector space, hence lines through the origin are uniquely determined by any non-origin point on the line. To find such a point, pick an easily invertible coefficient $c$ of the equation and scale the equation by $c^{-1}$ so the coefficient becomes $1$.

E.g. $\rm\ 4\:x -5\:y + 2\:z = 0\:$ over $\rm\:\mathbb Z/13\:.\:$ We look for an easy invertible coef, i.e. one dividing $13\pm1\:.\:$ We find $4\:$ since $4\cdot 3 = 13- 1 = -1\:.\:$ Scaling the equation by $3$ yields $\rm\: -x -2\:y + 6\:z = 0\:,\:$ so $\rm\:x = -2\:y+6\:z\:.\:$ Picking "simple" values for $\rm\:y,z\:,\:$ say $\rm\:y=0,\:z=2\:$ yields $\rm\:x=-1\:,\:$ which lies only on the line $\rm\:(D)\ -7\:x +12\:y+3\:z = 0\:.\:$

This method is both general and quick - esp. quick when there is an easily invertible coefficient dividing modulus $\pm 1\:$ (which occurs frequently for small moduli by the law of small numbers).

-

This is what I would do:

If $3x+7y$ is divisible by $11$, then $3x + 7y\equiv 0\pmod{11}$, so $3x\equiv -7y = 4y\pmod{11}$. Multiplying through by $4$, we get $12x \equiv 16y\pmod{11}$, which simplifies to $x\equiv 5y\pmod{11}$.

Then one can plug into the congruences: $4x+6y \equiv 26y\equiv 3y\pmod{11}$; $x+y+5\equiv 6y+5\pmod{11}$; $9x+4y\equiv 49y\equiv 5y\pmod{11}$; $4x-9y\equiv 11y\equiv 0\pmod{11}$; and $x+y-1\equiv 6y-1\pmod{11}$. Clearly, the answer is D.

For the second one, from $4x-5y+2z\equiv 0\mod{13}$ we have $4x\equiv 5y-2z\pmod{13}$; multiplying through by $-3$ we get $$-12x \equiv -15y+6z\pmod{13}$$ which is equivalent to $x \equiv -2y+6z\pmod{13}$.

Plugging into the different possibilities, we have: \begin{align*} \text{A. }&& x+13y - z &\equiv -2y+5z\pmod{13}\\ \text{B. }&& 6x-10y-z &\equiv 4y +9z\pmod{13}\\ \text{C. }&& x-y-2z &\equiv -3y+4z\pmod{13}\\ \text{D. }&&-7x+12y+3z &\equiv 26y -39z \equiv 0\pmod{13}\\ \text{E. }&& -5x+3y-4z &\equiv 13y-34z \equiv 5z\pmod{13}, \end{align*} so again, the answer is D.

Alternatively.

Once you have $x-5y\equiv 0\pmod{11}$ in the first problem, multiply by a suitable $k$ to try to match the coefficient of $x$ in the alternatives, until you get a match:

• For $4x+6y$, multiply $x-5y$ by $4$ to get $4x-20y \equiv 4x+9y$, not equal.
• For $x+y+5$, not equal.
• For $9x+4y$, multiply $x-5y$ by $9$ to get $9x-45y \equiv 9x-y$; not equal.
• For $4x-9y$, multiply $x-5y$ by $4$ to get $4x - 20y \equiv 4x -9y$; equal. This is the answer.

For the second one, again, from $x+2y-6z\equiv 0$, we try to match the coefficient of $x$ in each:

• Multiply by $1$ to try to get $x+13y-z$; no luck.
• Multiply by $6$ to try to get $6x-10y-z$; we get $6x+12y-36z\equiv 6x+12y-3z$; no luck.
• Multipy by $1$ to try to get $x-y-2z$; no luck.
• Multiply by $-7$ to try to get $-7x+12y+3z$; we get $-7x-14y+42z \equiv -7x -y+3z \equiv -7x+12y+3z$. Equal, so this is the answer.
-