Divisibility by 3

Question

Maybe this is a duplicate question (if so, can the moderators be kind enough to merge this appropriately?), but what is the condition on $a$ and $b$ for an expression $am+b$ to be divisible by $3$ ($a$ and $b$ are integers)? For example, I can say $16m+3$ is divisible by $3$ since $b=3$ is divisible by $3$ and for $m$ a multiple of $3$, $3|16m$. In the case of $176m+23$, I don't think it is divisible by $3$. Is this the case?

Answer 1

$am+b\equiv 0\mod 3\iff \bigl((a\mod 3)\cdot(m\mod 3)+(b\mod 3)\bigr)\equiv 0 \mod 3$.

So if you are given values for any two of $a,m,b$ you can deduce the requirement on the third unspecified variable by reducing the givens $\mod 3$.

Answer 2

Note that $3|(176m+23)$ $\iff$ $176m \equiv 2 (mod 3)$ $\iff$ $gcd(176,3)|2$ And so there exists a solution m. You can verify that m=5 is a solution. Clearly not every integer is a solution. Take m=1 for example. Similarly, 16m+3 is not always divisible by 3. But 18m+3 is divisible by 3 for every integer m, can you see why?

Answer 3

If $\gcd(a,3)=1$, then there will always exist some $m$ so that $3\mid am+b$. This is because as $m$ ranges from $0$ to $n-1$, the value of $am$ will occupy all the congruence classes mod $3$. Conversely, if $\gcd(a,3)=3$ (which is the only other possibility since $3$ is prime), then if $3\mid b$ then $3\mid am+b$ for all integers $m$, whereas $3\nmid am+b$ for all integers $m$ if $3\nmid b$.

Answer 4

A basic principle is that if $3|v$, then $3|w \iff 3|v+w$. Furthermore, if $3|v$ then $3|nv$.

So $3|ma+b\iff3|ra+s,$ where $r$ is the remainder when $m$ is divided by $3,$

and $s$ is the remainder when $b$ is divided by $3$.

Now we have only $9$ possibilities to consider: $r=0, 1, $ or $2, $ and $s=0, 1, $ or $2$.

When $r=0$ and $s=0$, $ra+s=0$ is divisible by $3$.

When $r=0$ and $s=1$ or $2$, $ra+s=1$ or $2$ is not divisible by $3$.

When $s=0$ and $r=1$ or $2$, then $ra+s=ra$ is divisible by $3$ when $a$ is and not when $a$ is not.

When $r=1$ and $s=1,$ then $ra+s=a+1,$ so $ra+s$ is divisible by $3$ when $a$ leaves remainder $2$ when divided by $3$.

When $r=1$ and $s=2,$ then $ra+s=a+2,$ so $ra+s$ is divisible by $3$ when $a$ leaves remainder $1$ when divided by $3$.

When $r=2$ and $s=1,$ then $ra+s=2a+1,$ so $ra+s$ is divisible by $3$ when $a$ leaves remainder $1$ when divided by $3$.

When $r=2$ and $s=2,$ then $ra+s=2a+2,$ so $ra+s$ is divisible by $3$ when $a$ leaves remainder $2$ when divided by $3.$