# Checking divisibility of an expression - Need Pointers

I would like it if someone could give me pointers on solving problems like these. And why was 4 the answer here ?

If $a=4b+26$ and $b$ is positive , then a could be divisible by all of following except

a)2 b)4 c)5 d)6 e)7

Edit:. I know by taking b=4 its divisible by 7 . However is there any other way by which we could tell its divisible by 7 other than randomly plugging in a no and testing ? Also I am using the current method to check if the expression is divisible by other options , is this method correct

Check by 2: 4b mode 2 and 26 mod 2 = 0 hence divisible by 2

For numbers greater than 4 the expression is doubled to $a=8b + 52$

Check by 5: 8b mode 5 = 3 while 52+3 mod 5 = 0 hence divisible by 5

Check by 6: 8b mode 6 = 2 while 52+2 mod 6 = 0 hence divisible by 6

Check by 4: 4b mode 2 =0 while 26 mod 2 $\not=$ 0 hence not divisible by 4

I need to know if this checking mechanism is correct ? is so why doesn't it work for 7 ? How could I check for 7 without plugging in and testing values ?

• $0=4b+26=4b+5 \pmod 7 \implies 4b=2 \pmod 7$. Since $\gcd(4,7)=1$, there is a solution.(e.g. b=4) – steven gregory Dec 30 '17 at 9:51

## 3 Answers

Hint $\rm\,\ d\:|\:4b\!+\!26\:\Rightarrow\: n\,d-4\,b = 26\:\Rightarrow\: gcd(d,4)\:|\:26\iff 4\nmid d$

• Hi @Bill I just wanted to make sure If I got your method for checking divisibility right. Did you mean $\frac{4b+26}{d}$ should give remainder $0$ thus giving equation $4b+26=dn$ implying $26=nd-4b$ Thus if 26 is divisible by the GCD of (d,4) then d is divisible by the expression- Will this be valid if the RHS of the equation was different like $nd+4b$? – Rajeshwar Jul 23 '12 at 4:07
• @Rajeshwar Yes, $\rm\:x\:|\:y\:$ means $\rm\,x\,$ divides $\rm\,y.\,$ Note that $\rm\,gcd(d,4)\:|\:nd+4b\,$ too, since $\rm\,gcd(d,4)\:|\:d,4\:$ so it divides every integer linear combination of $\rm\,d\,$ and $\rm\,4,\,$ i.e. every $\rm\:j\,d + 4\,k,\,$ for $\rm\,j,k\in\Bbb Z.\ \$ – Bill Dubuque Jul 23 '12 at 4:21
• Thanks for clearing that up. – Rajeshwar Jul 23 '12 at 4:24

It could never be divisible by 4, since $4b \mod 4 = 0$ for any integer $b$, and $26 \mod 4 = 2$.

Suppose $a$ is divisible by $4$, so $a=4c$ for some integer $c$. Then $26=a-4b=4(c-b)$ is divisible by $4$, which is clearly not the case. Thus we have a contradiction.

In general, you should approach these problems using modular arithmetic. In this case we have \begin{align} a &\equiv 4b+26 \mod 4\\ &\equiv 0b+2\mod 4\\ &\equiv 2\mod 4 \end{align} and so clearly $a$ is not divisible by $4$, as then we'd have $0\equiv 2\bmod 4$.