In base 10, you can determine the divisibility by 3 or 9 simply by adding up all the digits in the number; if the results are divisible by 3 or 9, then the numbers are divisible by 3 or 9, respectively.
What is the smallest base n such that we can do the same trick for all the numbers from 2 to 6?
In other words, what is the smallest integer n > 1 such that for any number x written in base n we can determine the divisibility by all integers m ( 2 ≤ m ≤ 6 ) , by adding up all the digits of x and, if the result divides by m , concluding that x is divisible by m ?
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
Could you explain/prove why this is? Thank you!
Log in to reply
Consider the number A = a t a t − 1 a t − 2 … a 2 a 1 a 0 n . We gonna to prove that if m is a factor of n − 1 and m ∣ ( a 0 + a 1 + … + a t − 1 + a t ) , then m divides A .
A = = = i = 0 ∑ t a i × n i a 0 + a 1 × n + … + a t − 1 × n t − 1 + a t × n t a 0 + a 1 + … a t − 1 + a t + a 1 × ( n − 1 ) + … + a t − 1 × ( n t − 1 − 1 ) + a t × ( n t − 1 ) A is the sum of a 0 + a 1 + … a t − 1 + a t and a 1 × ( n − 1 ) + … + a t − 1 × ( n t − 1 − 1 ) + a t × ( n t − 1 ) . By the condition, m ∣ ( a 0 + a 1 + … a t − 1 + a t ) . For all n i − 1 ( i = 1 , 2 , … , t ) , it has the factor n − 1 , because you can factorize n i − 1 = ( n − 1 ) ( n i − 1 + … + 1 ) . m is the factor of n − 1 . Hence, we can conclude that A is the multiple of m .
take 10 for example, if s=a1 1+a2 10...+an 10^n and n=a1+a2+...an, then s-n=a2 (10-1)+a3 (10^2-1)...an (10^n-1) which is guaranteed to be divisible by 9.So if 9 divides n, and then 9 divides s which is that statement. It means we need to make sure 10^n-1 is divided by 9 for every n,to be simple, 10-1 is divisible by 9. Therefore, n-1 should be divisible by gcd(2,3,4,5,6).
Problem Loading...
Note Loading...
Set Loading...
The trick works for base 10 since 3 and 9 both divide by 1 less than the base, or 9.
In general, for a base n number, this trick will work for any n for which n − 1 is divisible by all the numbers from 2-6. The smallest such number is 60, so the answer is n = 6 0 + 1 = 6 1 .