divisibility

**adhyeta** · May 5th 2009, 07:01 PM

For a positive integer n, Let S(n) denote the sum of its decimal digits.

Then S(n)-n is always divisible by?

A)9
B)10
C)11
D)None of these is always true.

The only problem is i did not get what is meant by decimal digits of the integer?

**pickslides** · May 5th 2009, 08:10 PM

If n is an integer then decimal digits must imply we are talking about numbers in the decimal system, I.e normal counting numbers as you know them.

Now pick any number n = 205 so S(n) = 2+0+5 = 9

Now S(n)-n = 205 - 9 = 196

196 is not divisble by 9, 10 or 11. Therefore we have found 1 example that contracdicts each of these sases therefore I think D is the answer.

**Gamma** · May 5th 2009, 09:10 PM

unfortunately $2 + 0 + 5 = 7\not = 9$ so this will not work. But I have an answer for you, the answer is A and I will explain below. I hope you know modular arithmetic if you were asked this question. I just wanted to catch you before you thought the answer was D.

**Gamma** · May 5th 2009, 09:17 PM

let n be a positive integer.

then $n=a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0$
So then $S(n)=a_n + a_{n-1} + ... + a_1 + a_0$

but consider the fact that
$10\equiv 1$ (mod 9)

induction if you want to be formal shows this means

$10^k \equiv 1$ (mod 9) for all $k\in \mathbb{N}$

So if we consider
$S(n)-n = (a_n + a_{n-1} + ... + a_1 + a_0) - a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0$

But reduce this mod 9
$S(n)-n \equiv (a_n + a_{n-1} + ... + a_1 + a_0) - a_n1^n + a_{n-1}1^{n-1} + ... + a_11^1+a_0 \equiv 0$ (mod 9)

But if two things are congruent to 0 mod 9, this means 9 divides this number.

So 9 divides S(n)-n

**adhyeta** · May 5th 2009, 10:50 PM

Originally Posted by Gamma

let n be a positive integer.

then $n=a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0$
So then $S(n)=a_n + a_{n-1} + ... + a_1 + a_0$

but consider the fact that
$10\equiv 1$ (mod 9)

induction if you want to be formal shows this means

$10^k \equiv 1$ (mod 9) for all $k\in \mathbb{N}$

So if we consider
$S(n)-n = (a_n + a_{n-1} + ... + a_1 + a_0) - a_n10^n + a_{n-1}10^{n-1} + ... + a_110^1+a_010^0$

But reduce this mod 9
$S(n)-n \equiv (a_n + a_{n-1} + ... + a_1 + a_0) - a_n1^n + a_{n-1}1^{n-1} + ... + a_11^1+a_0 \equiv 0$ (mod 9)

But if two things are congruent to 0 mod 9, this means 9 divides this number.

So 9 divides S(n)-n

thanks! but i believe they expect me to do it without modular arithmetic(as that is not in my course-i wish i knew that, sorry.) ill try to study that online.

**Gamma** · May 5th 2009, 11:21 PM

Definitely worth learning, however, there is in fact an alternative method that I think you can do with out modular arithmetic. Let's hope you at least know induction.

Lemma:
$9|10^k-1$ for all $k\in \mathbb{N}$
k=1
$9|10-1=9$ This is clearly true.

(Induction Hypothesis) Suppose up to n,
$9|10^n-1$

Now we must show $9|10^{n+1}-1$
$10^{n+1}-1=10^{n+1}-1-9+9=10^{n+1}-10+9=10(10^n-1)+9$
But by induction hypothesis 9 divides the first term and clearly 9|9, so 9 divides the sum and the induction is complete.

Okay, so now pick up my old proof up at the point where I wrote out
$S(n) - n = a_n + a_{n-1} + ... + a_1 + a_0 - a_n10^n + a_{n-1}10^n + ... + a_110^1 + a_010^0$
Now instead of the modular argument, we will group nicely by coefficient.
$S(n) - n = a_n(1-10^n) + a_{n-1}(1-10^n) + ... + a_1(1-10^1) + a_0(1-10^0)$

So by our lemma $9|10^k-1 \Rightarrow 9|-(10^k-1)=1-10^k$ but this means 9 divides every term so 9 must divide the whole thing which is S(n)-n as desired. QED (again)

**adhyeta** · May 5th 2009, 11:23 PM

Originally Posted by Gamma

Definitely worth learning, however, there is in fact an alternative method that I think you can do with out modular arithmetic. Let's hope you at least know induction.

Lemma:
$9|10^k-1$ for all $k\in \mathbb{N}$
k=1
$9|10-1=9$ This is clearly true.

(Induction Hypothesis) Suppose up to n,
$9|10^n-1$

Now we must show $9|10^{n+1}-1$
$10^{n+1}-1=10^{n+1}-1-9+9=10^{n+1}-10+9=10(10^n-1)+9$
But by induction hypothesis 9 divides the first term and clearly 9|9, so 9 divides the sum and the induction is complete.

Okay, so now pick up my old proof up at the point where I wrote out
$S(n) - n = a_n + a_{n-1} + ... + a_1 + a_0 - a_n10^n + a_{n-1}10^n + ... + a_110^1 + a_010^0$
Now instead of the modular argument, we will group nicely by coefficient.
$S(n) - n = a_n(1-10^n) + a_{n-1}(1-10^n) + ... + a_1(1-10^1) + a_0(1-10^0)$

So by our lemma $9|10^k-1 \Rightarrow 9|-(10^k-1)=1-10^k$ but this means 9 divides every term so 9 must divide the whole thing which is S(n)-n as desired. QED (again)

yes. i do know some stuff :P

**Gamma** · May 5th 2009, 11:42 PM

Oh man, I didn't mean it to be a slight at all. I can see how that could have sounded pretty disrespectful, I just meant it more in the sense of I have no idea how to prove it without induction! It is always a difficult thing to judge what type of proof to present on here since I have no idea what kind of mathematical background any of the askers have. It is a struggle to find a common ground of risking using a fact or something the reader may be unfamiliar with and being able to present a concise elegant proof.

Well, if you find this problem interesting and are curious about doing another really fun problem like this you should consider the following. Also it would be a great practice for you if you decide to learn modular arithmetic (which you will have to if you continue in number theory, algebra, or discrete mathematics). Consider the test for divisibility by 11.

A number is divisible by 11 if and only if the alternating sum of its digits is divisible by 11.

Here is what I mean.
Is 72237 divisible by 11?
7 -3 +2 -2 +7 = 11 which is divisible by 11 clearly, so 72237 number is divisible by 11.

**pickslides** · May 6th 2009, 01:57 PM

Originally Posted by Gamma

unfortunately $2 + 0 + 5 = 7\not = 9$

Opps!

Gamma,

I can recall a similar pattern that if the digits of an integer add to a multiple of 9 then it will be divisible by 9.

For example 2412, 2+4+1+2 = 9 and 2412/9 = 268

and 98172, 9+8+1+7+2 = 27 and 98172/9 = 10908

Apart from this one and the sum of alternating digits for divisibilty by 11, do you know any others?

**Gamma** · May 6th 2009, 02:17 PM

The other ones are really unsatisfying that I know compared to these two, lol.

For 2, if it ends in 0,2,4,6,8 it is divisible by two... duh it is even

For 3, if you sum the digits and it is divisible by 3 the number is divisible by 3.

For 4, if you look at the last two digits if they are divisible by 4 then the whole thing is 4|100 is why.

For 5, again, look at whether the last digit is 5 or 0, then it is divisible by 5, otherwise it is not.

For 6, check divisibility by 2 and 3 if it is divisible by both then it is divisible by 6.

For 7 I am honestly not sure of a good test for this divisibility

For 8 you just gotta check the last 3 digits because 8|1000

For 9, yeah we got that one on lock down

For 10 if it ends in 0 yeah, otherwise not.

For 11 the one i mentioned is the only test i know.

Of course you can generalize the one for 6. If it is a product of distinct primes you can just check it for divisibility by each of the distinct primes that make up the number.

**pickslides** · May 6th 2009, 02:40 PM

Thanks mate!

Thread: divisibility

LinkBack

Thread Tools

Display

divisibility

Alternate Proof without modular arithmetic :(

Similar Math Help Forum Discussions

Divisibility 11

Divisibility (gcd) 10

Divisibility (gcd) 9

Divisibility (gcd) 8

Divisibility

Search Tags