Divisibility of Integers ## 176521221 ## & ## 149235678 ## by 9 & 11

[Math100]

Homework Statement

Without performing the divisions, determine whether the integers $176521221$ and $149235678$ are divisible by $9$ or $11$.

Relevant Equations

None.

First, consider the integer $176521221$.
Observe that $1+7+6+5+2+1+2+2+1=27$.
Since $9\mid (1+7+6+5+2+1+2+2+1)$, it follows that $9\mid 176521221$.
Note that $1-2+2-1+2-5+6-7+1=-3$.
This means $11\nmid (1-2+2-1+2-5+6-7+1)$.
Thus $11\nmid 176521221$.
Therefore, the integer $176521221$ is divisible by $9$ but not divisible by $11$.
Next, consider the integer $149235678$.
Observe that $1+4+9+2+3+5+6+7+8=45$.
Since $9\mid (1+4+9+2+3+5+6+7+8)$, it follows that $9\mid 149235678$.
Note that $8-7+6-5+3-2+9-4+1=9$.
This means $11\nmid (8-7+6-5+3-2+9-4+1)$.
Thus $11\nmid 149235678$.
Therefore, the integer $149235678$ is divisible by $9$ but not divisible by $11$.

 

[fresh_42]

Homework Statement:: Without performing the divisions, determine whether the integers $176521221$ and $149235678$ are divisible by $9$ or $11$.
Relevant Equations:: None.

First, consider the integer $176521221$.
Observe that $1+7+6+5+2+1+2+2+1=27$.
Since $9\mid (1+7+6+5+2+1+2+2+1)$, it follows that $9\mid 176521221$.
Note that $1-2+2-1+2-5+6-7+1=-3$.
This means $11\nmid (1-2+2-1+2-5+6-7+1)$.
Thus $11\nmid 176521221$.
Therefore, the integer $176521221$ is divisible by $9$ but not divisible by $11$.
Next, consider the integer $149235678$.
Observe that $1+4+9+2+3+5+6+7+8=45$.
Since $9\mid (1+4+9+2+3+5+6+7+8)$, it follows that $9\mid 149235678$.
Note that $8-7+6-5+3-2+9-4+1=9$.
This means $11\nmid (8-7+6-5+3-2+9-4+1)$.
Thus $11\nmid 149235678$.
Therefore, the integer $149235678$ is divisible by $9$ but not divisible by $11$.

Correct, although the actual division wouldn't be any longer.

How about divisibility by $7$? Do you know the rule for it?

 

[Math100]

$7\nmid 27$, so $7\nmid 176521221$.
$7\nmid 45$, so $7\nmid 149235678$.

 

[Math100]

Correct, although the actual division wouldn't be any longer.

How about divisibility by $7$? Do you know the rule for it?

What's the rule for it?

 

[fresh_42]

$7\nmid 27$, so $7\nmid 176521221$.
$7\nmid 45$, so $7\nmid 149235678$.

Yes, they are not dividable by $7$ but the rule is a different one.

You take twice the number without the last two digits plus once the number of the last to digits and check whether this is dividable by $7$. So ...
\begin{align*}
176521221 &\longrightarrow 21 + 2\cdot 1765212 = 3530445\\
3530445 &\longrightarrow 45 +2 \cdot 35304 = 70653\\
70653 &\longrightarrow 53+ 2\cdot 706 =1465\\
1465&\longrightarrow 65+2\cdot 14 = 93
\end{align*}
... and $7\nmid 93$.

It looks a bit complicated which is due to the fact that there is no easy rule for seven, but it can be iterated so we get a recursion. From the computational point of view, it is still an improvement since doubling a number and addition are fast computations. (Not that this still plays a role nowadays, but it is the origin of complexity theory and algorithms.)

 

[Math100]

This is something good to know.

 

[SammyS]

A additional feature of the above divisibility tests for dividing by 9, or 11, or 7, as demonstrated above by OP and @fresh_42 , is that:
the resulting small number is congruent to the original number modulo 9, or 11, or 7 respectively.

For example, $149235678\equiv 9\pmod {11}$ .

 

[WWGD]

If you were worried about computing time, try subtracting by a known large number close to it that you know is a multiple of 9,11 .
For 149.235.678, you can use 144.000.000
If both are divisible by 9, so is their difference : 149235678-144000000=5235678.
Then the sum is easier to handle : 5+2+3+5+6+7+8 =36

For 11, use 143000000
For 176.521.221, use 171000000, 176000000 respectfully.

You'll never be farther than 11000000 or 9000000 away from a multiple. Or 5500000 and 4500000 , if you accept using negative numbers.

 

[haruspex]

An easy reduction is modulo 1001. Since that =7x11x13, it is relatively easy then to check for those three divisors.

 

[snorkack]

Generally, the idea of "divisibility rules" is to subtract large but easy numbers. This way you get not only the fact of divisibility (that is, residue equals 0) but the residue itself while the result of division is discarded in a number of components inconvenient to add up. Like your initial example:
176521221=(1*100 000 000)+(7*10 000 000)+(6*1 000 000)+(5*100 000)+(2*10 000)+(1*1000)+(2*100)+(2*10)+1=1*(99 999 999+1)+7*(9 999 999+1)+6*(999 999+1)+5*(99 999+1)+2*(9 999+1)+1*(999+1)+2*(99+1)+2*(9+1)+1=(1*99 999 999+7*9 999 999+6*999 999+5*99 999+2*9 999+1*999+2*99+2*9)+(1+7+6+5+2+1+2+2+1)
It would be inconvenient to actually divide the first term by 9, because we would have to sum up again (1*11 111 111+7*1 111 111... But if all we need is whether the total is divisible by 9, or even what the residue is, we can rest assured that the first term is divisible by 9 because every term of the first term is sure to be (9, 99,...,99 999 999,... are all certain to be divisible by 9) and divide just the second term.

"The" divisibility rule for 7 was new for me. It is limited usefulness, but gave insight for another divisibility rule.

Now back to rules. The rule for 11 is slightly more complex.
Here the idea is that 99=9*11, and so 100=(9*11+1), but while 10=9+1, also 10=11-1. And for every higher power of 10, for every even power of 10, 10²ⁿ-1 divides by 11, but for every odd power of 10, 10²ⁿ⁺¹+1 does. So 99, 9 999, 999 999... are divisible by 11, and so are 11, 1 001, 100 001...
Then you can usefully depict odd powers of 10 as having negative residue rather than residue +10, which is more correct but less convenient to use. So
176521221=(1*100 000 000)+(7*10 000 000)+(6*1 000 000)+(5*100 000)+(2*10 000)+(1*1000)+(2*100)+(2*10)+1=1*(99 999 999+1)+7*(10 000 001-1)+6*(999 999+1)+5*(100 001-1)+2*(9 999+1)+1*(1001-1)+2*(99+1)+2*(11-1)+1
Now, 11 has different but simple rule for both 10 and 100. To the harder numbers. 7.

I was aware of the rule of 1001. Which has the advantage of simultaneously giving divisibility for 7, 11 and 13.
The rule offered for 7 above essentially uses the fact that 98 divides by 7. I should say that it is more complicated to use 98 than 1001.
Even if you have to, you can choose an easier end:
176521221=(1765212*100)+21=(1765212*98)+(1765212*2)+21
still means multiplying (1765212*2).
Instead, you might group
176521221=(17*10 000 000)+6521221=(17*9 800 000)+(17*200 000)+6521221
and iterate from there.

Once you call 98 an acceptable rule of divisibility, it gives insight for another:
102=6*17.
In that case, there is no better alternative: for higher powers of 10, the nearby multiples of 17 go 1 003, 9 996...
Nor does 19 seem to have a good divisibility rule: multiples near powers of 10 go 95, 1 007, 9 994...