1
$\begingroup$

(I am aware there are similar questions on the forum)

What is the Question?

A positive integer (in decimal notation) is divisible by $11$ if and only if the difference of the sum of the digits in even-numbered positions and the sum of digits in odd-numbered positions is divisible by $11$.

For example consider the integer 7096276.

The sum of the even positioned digits is $0+7+6=13.$ The sum of the odd positioned digits is $7+9+2+6=24.$ The difference is $24-13=11$, which is divisible by 11.

Hence 7096276 is divisible by 11.

(a)

Check that the numbers 77, 121, 10857 are divisible using this fact, and that 24 and 256 are not divisible by 11.

(b)

Show that divisibility statement is true for three-digit integers $abc$. Hint: $100 = 99+1$.

What I've Done?

I've done some research and have found some good explanations of divisibility proofs. Whether that be 3,9 or even 11. But...the question lets me take it as fact so I don't need to prove the odd/even divisible by 11 thing.

I need some help on the modular arithmetic on these.

For example... Is 77 divisible by 11? $$7+7 = 14 \equiv ...$$

I don't know what to do next.

Thanks very much, and I need help on both (a) and (b).

$\endgroup$
1
$\begingroup$

In order to apply the divisibility rule, you have to distinguish between odd and even positioned digits. (It doesn't matter how you count.)

Example: In 77 the first position is odd, the second even, so you would have to calculate $7-7=0$, which is divisible by 11.

Now it should be easy for you to understand what you try to prove in (b): If a,b,c are three digits abc is the number $100a+10b+c$. You know what it means to say that this number is divisible by 11. You have to prove that $$11\vert (a+c)-b \Leftrightarrow 11\vert 100a+10b+c$$ or with modular arithmetic $$ (a+c)-b \equiv 0 \pmod{11}\Leftrightarrow 100a+10b+c\equiv 0 \pmod {11}\; .$$ I don't want to spoil the fun so I leave it there.

P.S. Sorry, I hadn't noticed the answer posted in the meantime.

$\endgroup$
1
$\begingroup$

When you are checking $77$ for divisiblility, the first $7$ is in an even place and the second is in an odd place, so you check $7-7=0$, which is divisible by $11$, so $77$ is. For $10857$ you do $1+8+7-0-5=11$, which is divisible by $11$. For part b, note that the three digit number $abc$ can be written as $100a+10b+c$ and use the hint to represent the $100$

$\endgroup$
1
$\begingroup$

How to quickly determine whether an integer is divisible by 3,9,11


NOTE

Generally speaking, it is not a simple question to determine whether an integer is divisible by another one or not . We don't have a universal method. However, given a specific integer, when the dividend take some special value, such as 3, 9, 11,.... we can easily test that by hand.


Proposition :

Suppose n is any positive integer,and the decimal representation of $n$ is:

$$n=a_{k}a_{k-1}a_{k-2}\cdots a_{0}$$

We have the following results:

  1. $$\textrm{n is divisible by 3 if and only if} \quad \sum_{i=0}^{k}a_{i} \,\,\text{is divisible by 3} $$
  2. $$\textrm{n is divisible by 9 if and only if} \quad \sum_{i=0}^{k}a_{i} \,\,\text{is divisible by 9} $$
  3. $$\qquad\textrm{n is divisible by 11 if and only if} \sum_{i=0}^{k}(-1)^{i}a_{i} \,\,\text{is divisible by 11} $$

proof of 3:

Since $$n=\sum_{i=0}^{k}a_{i}\cdot10^{k}$$ and $$10\equiv -1\pmod {11}$$ we have $$n=\sum_{i=0}^{k}a_{i}\cdot10^{k}\equiv \sum_{i=0}^{k}a_{i}\cdot(-1)^{i}\pmod{11}$$ Thus,

$$n\equiv0 \pmod{11 }\,\text{if and only if}\sum_{i=0}^{k}a_{i}\cdot(-1)^{i}\equiv0\pmod{11}$$ Notice that $$10\equiv 1\pmod9\quad and\quad 10\equiv 1\pmod3$$ the first two propositions can be proofed in the same way,we safely omit the proof here.

Coment:

When the dividend take other values, we can also construct similar test method, but the result will not be as beautiful as the above ones.

$\endgroup$
1
$\begingroup$

There are other tests for divisibility by $11$. I submit the following.

This Lemma has been proved many many times

Lemma. Let $n = \sum_{i=0}^D d_i 10^{D-i}$ where the $d_i$ are integers from $0$ to $9$. Then $n \pmod 9 \equiv \sum_{i=1}^D d_i \pmod 9$.

The process is often referred to as casting out nines.

It isn't hard to show that there is a similar lemma for casting out ninety-nines.

Lemma. Let $n = \sum_{i=0}^D d_i 100^{D-i}$ where the $d_i$ are integers from $0$ to $99$. Then $n \pmod{99} \equiv \sum_{i=1}^D d_i \pmod{99}$.

For example Let $n = 363957 = (36 \times 100^2) + (39 \times 100) + (57)$.

Then \begin{align} n \pmod{99} &\equiv 36 + 39 + 57 \pmod{99} \\ &\equiv 132 \pmod{99} \\ &\equiv 1 + 32 \pmod{99} \\ &\equiv 33 \pmod{99} \end{align}

It follows that $n \pmod{11} = 33 \pmod{11} = 0$. Hence $11 \mid 363957$.

$\endgroup$
0
$\begingroup$

Here is a not-quite-right hand-waving answer that might be worth thinking aboiut.

If a number is divisible by $11$, this long division problem ends up with no remainder (all zeros at the bottom). Look at the red numbers that were subtracted from a red digit $\color{red}\#$ in the original dividend: $\color{red}{a+b+c+d+e+f+g}$, and look at the blue numbers that were subtracted from a blue digit $\color{blue}\#$ in the original dividend: $\color{blue}{a+b+c+d+e+f+g}$

Now the hand-waving. Of course, this isn’t quite right, because there might have been some borrowing involved, but everywhere there was borrowing, it was to allow $10$ more to be subtracted from some digit position and $1$ less to be subtracted from the position to its left, which we’ll pretend explains why divisibility by $11$ means the difference in sums is either zero or (if there was borrowing) a multiple of $11=10+1$.

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.