# Solve for $px + q \equiv 0\pmod r$

How would I solve for the following in general:

$(px + q)\equiv 0 \pmod r$

For example,

$(2x + 1)=0 \pmod 7$

$x = 3, 10, 17, 24, \ldots$

$(9y + 5)= 0 \pmod 3$

$y$ has no solution.

I came up with the answers through intuition, but is there an actual proof or formula that can solve for the above?

-

Your title is misleading: the % symbol is the modulus: it $(px + q) \mathbin{\%} r$ means the remainder after dividing $(px + q)$ by $r$. This can be expressed as equivalence modulo $r$.

$$2x + 1 \equiv 0 \pmod 7 \iff 2x \equiv -1 \pmod 7$$ $$\iff 2x \equiv 6 \pmod 7 \iff x \equiv 3 \pmod 7$$

So indeed, $x \in \{..., -4, 3, 10, 17, 24, ...\}$

For your second question: $(9y + 5) \mathbin{\%} 3 = 0$, we are interested in the remainder of $9y + 5$ when divided by $3$, and testing whether this remainder can be equal to $0$: Note that $3$ divides $9y$ for all values of $y$, but $3$ does not divide $5$: so $3$ cannot divide $9y + 5$ evenly, so it cannot hold. That is,

$$9y + 5 \equiv 0 \pmod 3 \iff 9y \equiv -5 \pmod 3$$ $$\iff 9y \equiv 1 \pmod 3$$ which, as you note, cannot hold because $9y\equiv 0 \pmod 3$, that is, $9y$ is divisible by 3, whatever the value of $y$, and so there cannot be a remainder of $1$.

Resources:

-
Thanks! Seems so obvious once you see the answer.. –  oliver Jan 25 '13 at 14:04
Edited the title to more accurately reflect the nature of the question. –  oliver Jan 25 '13 at 14:08
Your welcome! Thanks for the edit. –  amWhy Jan 25 '13 at 14:09
Thanks @Willie, for the edit: I totally missed the % problem! –  amWhy Jan 25 '13 at 14:11
+1 Nice and I agree with oliver at the first comment. –  B. S. Jan 25 '13 at 14:28