From my Math GRE book.
If $x$, $y$, and $z$ are integers satisfying $13 | 4x - 5y + 2z$, which one of the following sums 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
Is there a procedure, given integers $x$, $y$, $z$ and a linear combination $P(x, y, z)$ to write out all of the linear combinations that satisfy $n | P(x, y, z)$?
On
If $x$, $y$, and $z$ are integers satisfying $13 \mid 4x - 5y + 2z$, which one of the following sums must also be divisible by $13$?
$(A)\ x\! +\! 13y\! -\! z,\ (B)\ 6x\! -\! 10y\! -\! z,\ (C)\ x\! -\! y\! -\! 2z,\ (D)\ \bbox[5px,border:1px solid green]{{\color{#c00}{-7}}x\! +\! 12y\! +\! \color{#c00}3z},\ (E)\ {-}5x\! +\! 3y\!-\! 4z$
Easy way: Let $f = 4x-5y+2z.\,$ If $13\nmid n$ then $13\mid nf\iff 13\mid f,\,$ so it suffices to see if one has the form $nf$. If so the $x$ coef will remain twice the $z$ coef $\!\bmod 13.\,$ Checking only $(D)$ works
$(A)\ \ 1\not\equiv 2(-1),\ \ (B)\ \ 6\not\equiv 2(-1),\ \ (C)\ \ 1\not\equiv 2(-2),\ \ (D)\ \ \bbox[5px,border:1px solid green]{\color{#c00}{{-}7}\equiv 2(\color{#c00}3)}, \ \ (E)\ {-5}\not\equiv 2(-4)$
$(D)$ is $\,g\equiv 6x\!-\!y\!+\!3z.\,$ $f\,$ has $-5y\,$ vs $-y$ in $g\,$ so $\,5g \equiv 30x -5y +15z\equiv f\pmod{\!13}$
Suppose $x,y,z$ are integers such that $13{\,\mid\,}(4x - 5y + 2z)$. \begin{align*} \text{Then}\;\;&13{\,\mid\,}(4x - 5y + 2z)\\[4pt] \iff\;&4x - 5y + 2z\equiv 0\;(\text{mod}\;13)\\[4pt] \iff\;&2z\equiv -4x+5y\;(\text{mod}\;13)\\[4pt] \iff\;&7(2z)\equiv 7(-4x+5y)\;(\text{mod}\;13)\\[4pt] \iff\;&14z\equiv -28x+35y)\;(\text{mod}\;13)\\[4pt] \iff\;&z\equiv\;11x+9y\;(\text{mod}\;13)\\[4pt] \end{align*}
Thus, to satisfy the hypothesis, we can let $x,y$ be arbitrary integers, and then let $z$ be any integer such that $$z\equiv\;11x+9y\;(\text{mod}\;13)$$
Analyzing the choices one at a time, we get \begin{align*} a&=x + 13y - z\\[4pt] &\equiv x+13y -(11x+9y)\;(\text{mod}\;13)\\[4pt] &\equiv -10x+4y\;(\text{mod}\;13)\\[4pt] &\equiv 3x+4y\;(\text{mod}\;13)\\[12pt] b&=6x - 10y - z\\[4pt] &\equiv 6x-10y -(11x+9y)\;(\text{mod}\;13)\\[4pt] &\equiv -5x-19y\;(\text{mod}\;13)\\[4pt] &\equiv 8x+7y\;(\text{mod}\;13)\\[12pt] c&=x - y - 2z\\[4pt] &\equiv x-y -2(11x+9y)\;(\text{mod}\;13)\\[4pt] &\equiv -21x-19y\;(\text{mod}\;13)\\[4pt] &\equiv 5x+7y\;(\text{mod}\;13)\\[12pt] d&=-7x +12 y +3z\\[4pt] &\equiv -7x+12y+3(11x+9y)\;(\text{mod}\;13)\\[4pt] &\equiv 26x+39y\;(\text{mod}\;13)\\[4pt] &\equiv 0\;(\text{mod}\;13)\\[12pt] e&=-5x +3y - 4z\\[4pt] &\equiv-5x+3y -4(11x+9y)\;(\text{mod}\;13)\\[4pt] &\equiv -49x-33y\;(\text{mod}\;13)\\[4pt] &\equiv 3x+6y\;(\text{mod}\;13)\\[12pt] \end{align*} Thus, since the integers $x,y$ can be chosen arbitrarily, choice $(\text{D})$ is the only one which must be a multiple of $13$.
More generally, assume the hypothesis $$13{\,\mid\,}(4x - 5y + 2z)\qquad (*)$$ where $x,y,z$ are unknown integers, and let $p$ be given by $$p=Rx+Sy+Tz$$ where $R,S,T$ are given integers.
Then we get \begin{align*} p&=Rx+Sy+Tz\\[4pt] &\equiv Rx+Sy+T(11x+9y)\;(\text{mod}\;13)\\[4pt] &\equiv (R+11T)x+(S+9T)y\;(\text{mod}\;13)\\[4pt] &\equiv (R-2T)x+(S-4T)y\;(\text{mod}\;13)\\[4pt] \end{align*} hence, assuming $(*)$, we get that $p$ is necessarily a multiple of $13$ if and only if the conditions $$ \begin{cases} 13{\,\mid\,}(R-2T)\\[6pt] 13{\,\mid\,}(S-4T)\\ \end{cases} $$ are satisfied, or equivalently, $R,S,T$ are given by $$ \begin{cases} R=2t+13u\\[4pt] S=4t+13v\\[4pt] T=t\\ \end{cases} $$ where $t,u,v$ are arbitrary integers.