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.

#NumberTheory #Divisibility #Sharky

Easy Math Editor

This discussion board is a place to discuss our Daily Challenges and the math and science related to those challenges. Explanations are more than just a solution — they should explain the steps and thinking strategies that you used to obtain the solution. Comments should further the discussion of math and science.

When posting on Brilliant:

Use the emojis to react to an explanation, whether you're congratulating a job well done , or just really confused .
Ask specific questions about the challenge or the steps in somebody's explanation. Well-posed questions can add a lot to the discussion, but posting "I don't understand!" doesn't help anyone.
Try to contribute something new to the discussion, whether it is an extension, generalization or other idea related to the challenge.
Stay on topic — we're all here to learn more about math and science, not to hear about your favorite get-rich-quick scheme or current world events.

Markdown	Appears as
`italics` or `_italics_`	italics
`bold` or `__bold__`	bold
- bulleted - list	bulleted list
1. numbered 2. list	numbered list
Note: you must add a full line of space before and after lists for them to show up correctly
paragraph 1 paragraph 2	paragraph 1 paragraph 2
`[example link](https://brilliant.org)`	example link
`> This is a quote`	This is a quote
# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"	# I indented these lines # 4 spaces, and now they show # up as a code block. print "hello world"

Math	Appears as
Remember to wrap math in `$` ... `$` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$

Comments

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 - 6 years, 12 months ago

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 - 6 years, 11 months ago

What if the number is a four digit number, say, 4593? Your proof currently only holds for three digit numbers.

Victor Loh - 6 years, 11 months ago

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 - 6 years, 11 months ago

@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 - 6 years, 8 months ago

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.

Anonymous Anonymous - 6 years, 11 months ago

Please show some examples

Sunil Pradhan - 6 years, 11 months ago

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 - 6 years, 11 months ago

Math	Appears as
Remember to wrap math in `\(` ... `\)` or `\[` ... `\]` to ensure proper formatting.
`2 \times 3`	$2 \times 3$
`2^{34}`	$2^{34}$
`a_{i-1}`	$a_{i-1}$
`\frac{2}{3}`	$\frac{2}{3}$
`\sqrt{2}`	$\sqrt{2}$
`\sum_{i=1}^3`	$\sum_{i=1}^3$
`\sin \theta`	$\sin \theta$
`\boxed{123}`	$\boxed{123}$