Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share

1 Answer 1

up vote 3 down vote accepted

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$.

E.g., your first equivalence reads:

$$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:

share
    
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

This site is currently not accepting new answers.

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