Divisibility (Modular Arithmetics)

204 Views Asked by At

Consider you are given that

$$4a2b$$

and this number can be divided by $36$. How would I evaluate the values for $a$ and $b$ that satifsy with our condition?

Let us try to write it mathematically, whereupon we will have that

$$4000+100a+20+b \equiv 0 \pmod{36}$$

$$24+28a+b \equiv 0\pmod{36}$$

With my best wishes!

4

There are 4 best solutions below

0
On BEST ANSWER

Notation Confusion?

See, if you are uncomfortable with the notation $a \equiv b \mod c$, then you may always revert to the definition : this is equivalent to the statement that $a-b$ is a multiple of $c$, or that $a-b = kc$ for some integer $k$.

Thus, saying that the number $4a2b$ is a multiple of $36$, is the same thing as saying that $4000 + 100a + 20 + b = 36 k$ for some integer $k$.


You've written the right things, but we can simplify

Let us look at each term of $4000 + 100a + 20 + b = 36k$.

  • We know that $4000 - 4 = 3996 = 36 \times 111$ (You can verify this). Thus, $4000 -4$ is a multiple of $36$, and hence $4000 \equiv 4 \mod 36$.

  • We know that $100a - 28 a = 72 a = 36 \times 2a$ is a multiple of $36$. So $100a \equiv 28 a \mod 36$.

Leaving the other terms as they are, gives $4a2b \equiv 4 + 28a + 20 + b \mod 36 = 0 \mod 36$. Adding the $20$ and $4$ gives your equation $28a + 24 + b \equiv 0 \mod 36$.


I'm stuck

$36$ is too large a number, so we need to work with smaller numbers, whose multiples are more easily understood than those of $36$. Therefore, for this, we need an observation from the comments : $36$ is the least common multiple of $9$ and $4$, therefore any number is a multiple of $36$, if and only if it is a multiple of both $4$ and $9$.

Therefore, what we are saying is that if $28a + 24 + b \equiv 0 \mod 36$, then these two equations are both true : $$ 28a + 24 + b \equiv 0 \mod 9 \\ 28a + 24 + b \equiv 0 \mod 4 $$


Further simplifications

On the first equation above, we note that:

  • $28a - a = 27 a = 9 \times 3a$ is a multiple of $9$. So $28a \equiv a \mod 9$.

  • $24 - 6 = 18 = 9 \times 2$ is a multiple of $9$, so $24 \equiv 6 \mod 18$.

Leaving the third term as it is gives the result $28a + 24 + b \equiv a + 6 + b \equiv 0 \mod 9$.

The second equation above has drastic simplifications :

  • Note that $24 - 0 = 24$ is a multiple of $4$, so $24 \equiv 0 \mod 4$.

  • Note that $28a-0 = 28a$ is a multiple of $4$, so $28a \equiv 0 \mod 4$.

Leaving thee third term as it is, gives $28a + 24 + b \equiv b \equiv 0 \mod 4$. In other words, $b - 0 = b$ is a multiple of $4$.


Collecting results, and inference

Therefore, $a+b+6$ is a multiple of $9$, and $b$ is a multiple of $4$.

Also, $a$ and $b$ are single digit numbers. This implies that $b$ can only be $0$, $4$ or $8$.

Therefore, $a+0+6$ is a multiple of $9$ implies $a = 3$.

$a+4+6$ is a multiple of $9$ implies $a = 8$.

$a + 8 + 6$ is a multiple of $9$ implies $a = 4$.

This gives three numbers : $4320,4428,4824$.

Check that $120 \times 36 = 4320,123 \times 36 = 4428$ and $134 \times 36 = 4824$.


Why knowing your divisibility rules makes things easy

Well, the divisibility rule for $9$ is : sum of digits is a multiple of $9$. The sum of digits here, is $a+b+6$, so we want $a+b+6$ to be a multiple of $9$. Same condition as above.

The divisibility rule for $4$ is : last two digits should form a multiple of $4$. So $2b$ should be a multiple of $4$, this forces $b = 0,4,$ or $8$ as the only multiples are $20,24,28$.

Therefore, with the divisibility rules in hand, this problem would have been damp squib. Having said that, the divisibility rules are proved using modular arithmetic, so it is more like we develop the machinery and do the kard work first, and then everything looks easy after that.

0
On

We have that

$$24+28a+b \equiv 0\pmod{36} \iff 28a+b \equiv12 \pmod{36}$$

which is equivalent to

  • $28a+b \equiv12 \pmod{4} \implies b\equiv 0 \pmod{4}$

  • $28a+b \equiv12 \pmod{9} \implies a+b\equiv 3 \pmod{9}$

then we have

  • $b=0 \implies a=3$

  • $b=4 \implies a=8$

  • $b=8 \implies a=4$

0
On

$4a2b$ has to be divisible separately by $4$ and by $9$.

  • $4a2b$ is divisible by $4$ if and only if $2b$ is, i.e. if and only if $b\in\{0, 4,8\}$.
  • It is divisible by $9$ if and only if $4+a+2+b=a+b+6\equiv 0\mod 9$, i.e. if and only if $a+b\equiv 3\mod 9$.

Can you proceed? (remember that $0\le a\le 9$).

0
On

You like to have $4a2b$ be a multiple of $36$

Since $36=4\times 9$, your number should be a multiple of $4$ and a multiple of $9$.

To be divisible by $4$ we need $b=0,4,8$ and to be divisible by $9$ we need $4+a+2+b$ divisible by $9$ That is $a+b+6$ divisible by $9$ so we have $(a,b) = (3,0)$ or (a,b)=(8,4)$ or $(a,b)=(4,8)$

Thus the number could be $4320$ or $4824$ or $4428$