Divisibility Rules! Base 2015

Number Theory Level 4

In base 10, the divisiblity rule for 11 works as follows:

Suppose we have a number $a_6a_5a_4a_3a_2a_1$ . Then we know whether this number is divisible by 11 if and only if the numbers in odd places ( $a_1, a_3, a_5$ ) and the numbers in even places( $a_2, a_4, a_6$ ) have a difference divisible by 11, i.e. $(a_1+ a_3+ a_5)-(a_2+ a_4+ a_6)$ is divisible by 11.

In base 2015, for how many numbers can this divisibility rule be applied (excluding 1)?

Submit your answer as the sum of all numbers for which this divisibility rule can be applied.

The answer is 6551.

1 solution

Manuel Kahayon
Jun 9, 2016

Relevant wiki: Application of Divisibility Rules

Why does the divisibility rule in base $10$ work for $11$ ? This is precisely because $10 \equiv -1 \pmod {11}$ . This means that any number in the form $a_6a_5a_4a_3a_2a_1$ can be expressed as $a_6a_5a_4a_3a_2a_1 = a_6(10^5)+a_5(10^4)+a_4(10^3)+a_3(10^2)+a_2(10)+a_1$

But, $a_6(10^5)+a_5(10^4)+a_4(10^3)+a_3(10^2)+a_2(10)+a_1 \equiv a_6(-1)^5+a_5(-1)^4+a_4(-1)^3+a_3(-1)^2+a_2(-1)^1+a_1(-1)^0 \pmod{11}$ (Since $10 \equiv -1 \pmod {11}$ )

Therefore the whole expression is equivalent to $-a_6+a_5-a_4+a_3-a_2+a_1 \pmod{11}$ .

In the same manner, for the question, we need numbers $n$ such that $2015 \equiv -1 \pmod n$ , or $2016 \equiv 0 \pmod{n}$ .

Now, the sum of the numbers which satisfy is equal to the sum of all the positive divisors of $2016$ reduced by 1.

Since $2016 = 2^5 \cdot3^2 \cdot 7$ , the sum of all its divisors is $(1+2+4+8+16+32)(1+3+9)(1+7) = 6552$ .

Therefore, we just subtract $1$ from the sum to obtain the answer $\boxed{6551}$ .

What about rule for divisibility by $2014$ and $5$ ?

Since. $5$ is a factor of $2015$ , the last digit of a number being divisible by 5 would be sufficient to determine divisibility by 5. Similarly, sum of digits of a numebr being divisible by $2014$ would assure divisibility of the number by $2014$ .

Janardhanan Sivaramakrishnan - 5 years ago

I only asked for the numbers which have the same divisibility rule as $11$ in base $10$ . $2014$ also has a divisibility rule, but not the same as that of $2016$ .

Manuel Kahayon - 5 years ago

But, then there is another issue. The divisibility rule can test the divisibility by 2016 only. If a number fails the test, you can only reliably say that the number is not divisible by 2016. You cannot comment on its divisibility by any of the factors of 2016. It only gives out a sufficient condition for divisibility, not 'necessary and sufficient' condition.

Eg : $15_{2015} = 2020_{10}$ . This is divisible by $4$ . However, it fails the divisibility test.

If you are talking about numbers for which the 'divisiblity by 11' type of test can be applied, in base 2015, the only case is 2016. For the factors, it is not a divisibility test, but a sufficiency for divisibility.

Janardhanan Sivaramakrishnan - 5 years ago

@Janardhanan Sivaramakrishnan – No, $15_{2015}$ also passes the divisibility test by $4$ , since $15_{2015}$ gives $1-5 = -4$ when subjected to the divisibility test, and $4|-4$ . Note that any number which divides 2016, i.e. $2016 \equiv 0 \pmod {n}$ has the same divisibility test above base 2015, since $2015 \equiv -1 \pmod{n}$ , which implies that any number in the form $...ABCDE_{2015} = ... + A(2015)^4+B(2015)^3+C(2015)^2+D(2015)+E \equiv ...+A(-1)^4+B(-1)^3+C(-1)^2+D(-1)+E \pmod {n}$ , since $2015 \equiv -1 \pmod{n}$ . This implies that if $...+A-B+C-D+E \equiv 0 \pmod {n}$ , then $...ABCDE \equiv 0 \pmod{n}$ .

Manuel Kahayon - 5 years ago

@Manuel Kahayon – That is an interesting property. Good problem. Thank you.

Janardhanan Sivaramakrishnan - 5 years ago

Would we want to consider that the case of 2 having a decimal pattern of 1? For example $(n-1) base n$ follows a similar rule as all factors of $n-1$ will have a period 1. So $gcd(2014,2016)=2$ thus you would want to remove that case.

Jaleb Jay - 4 years, 12 months ago

Divisibility Rules! Base 2015

The answer is 6551.

1 solution

0 pending reports