Waste less time on Facebook — follow Brilliant.
×

Divisibility Tests

Pretty soon, I will start posting notes which ask to find and prove divisibility tests for many different prime numbers. If you don't know the divisibility test for 13 or 29, let this be the time for you to learn them.

Proofs must be given with the actual test. That's the main rule you have to follow. As a start, this note will ask you to prove the divisibility test of 3.

Note by Sharky Kesa
2 years, 7 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

Write \(n=a_{k}\times 10^{k}+\cdots + a_{1}\times 10 + a_{0}\) (where \(0\leq a_{i}\leq 9\), and \(a_{k}\neq 0\)),

Then \(S(n)=a_{0}+a_{1}+\cdots+a_{k}\). We have

\[n-S(n)=a_{k}(10^{k}-1)+\cdots+a_{1}(10-1).\] \((1.1)\)

For \(1\leq i \leq k\), from factorisation we get \(9|(10^{i}-1)\). \(3|9 \implies 3|(10^{i}-1)\). So every term of the \(k\) terms in the right-hand side of \((1.1)\) is a multiple of \(3\), thus their sum is also a multiple of \(3\), that is, \(3|(n-S(n))\). Hence, the result can be obtained easily. Victor Loh · 2 years, 7 months ago

Log in to reply

Comment deleted Jun 19, 2014

Log in to reply

@Victor Loh Nicely done. Next one may be slightly harder. Sharky Kesa · 2 years, 7 months ago

Log in to reply

Let the digits in the number abc so number is represented as 100a + 10b + c = 99a + 9b + a + b + c out of these (99a + 9b) is divisible by 3 so (a + b + c) must be divisible by 3 (a + b + c) which is sum of digits in the number divisible by 3 Sunil Pradhan · 2 years, 7 months ago

Log in to reply

@Sunil Pradhan What if the number is a four digit number, say, 4593? Your proof currently only holds for three digit numbers. Victor Loh · 2 years, 7 months ago

Log in to reply

@Victor Loh No. = 1000a + 100b + 10c + d = (999a + 99b + 9c) + (a + b + c + d)

(999a + 99b + 9c) divisible by 3 so remaining (a + b + c + d) must be divisible by 3 Sunil Pradhan · 2 years, 7 months ago

Log in to reply

@Sharky Kesa Can you add this (and your other divisibility notes) to Diviisbility Rules or Applications?

Select "Write a summary", and then copy-paste your text into it (with minor edits). Thanks! Calvin Lin Staff · 2 years, 3 months ago

Log in to reply

Instead of proving the divisibility rule for just 3, ill do the divisibility rule for any factor of the base, b, minus 1.

If we select a given number, n, that is a factor of b-1, then b is congruent to 1 mod n. Thus, if we select any n such that it is a factor of the base minus 1, we can check wether any other given number is divisible by n by adding its digits in the base b representation of itself and check wether that number is divisible by n.

For example: take the divisibility rule for 5 in base 21. Lets say that i want to test wether 1027109 in base 21. Since 21 is congruent to 1 mod 5, i can add up 1+0+2+7+1+0+9= (20), which is congruent to 0 mod 5, and thus divisible by 5. Robert Melville · 2 years, 7 months ago

Log in to reply

@Robert Melville In case of base 10 the numbers can be expressed as 10^N X A + 10^N-1 X B and so on.. now when we divide this by 3 we have the remainder as A + B + C... as 10^anything will leave a remainder 1 when divided by 3 Rohan Rawal · 2 years, 6 months ago

Log in to reply

@Robert Melville Please show some examples Sunil Pradhan · 2 years, 7 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...