Re: n-ary representation and divisibility

On 30 May 2005 06:44:52 -0700, "krill" <krillqill@xxxxxxxxxxx> wrote:

>
>Recently I have an observation about algorithms on divisibility of
>integers by prime numbers. People have developed many of these, e.g.
>
>(1)For p=3: add up all digits and see if the sum divides by 3.
>
>(2)(...)
>(3)(...)
>
>But we perform all these algorithms mostly under decimal representation
>of the integer. What about for different n-ary representation?
>
>I find that: For integer a and fixed prime p, if we write a into m-ary
>representation, where m and 10 are congruent mod p, then the same
>algorithm that works under decimal representation, could still applies
>for m-ary representation of a. I've checked tens of numbers and the
>first several primes, and the conclusion goes true, but i dont know how
>to prove it or disprove it.
>
>Could anyone help me?
>
As you present it, the proof will have to be made separately for each
rule, but you should be able to imitate from the simplest case (above)

The reason why a number in decimal form is divisible by 3 iff the sum
of its digits is divisible by 3 is that: 10 is congruent to 1 mod 3,
therefore all powers of 10 are congruent to 1 mod 3, therefore
replacing a_i * 10^i in a decimal number "a_n ... a_i ... a_2 a_1 a_0"
i.e. a_0 + a_1 * 10 + a_2 * 10^2 + ... + a_i * 10^i + ... + a_n * 10^n
by a_i (in this sum) will not change (the class of) the number mod. 3

The same rule will be valid for any number base m congruent to 1 mod 3
which is the same as congruent to 10 mod 3.

(The primality of p=3 is not essential. The same is done with p'=9.)

You can get more such results in bases different from 10 if you find
out the reason of such a rule and generalize the reasoning, e.g.

A hexadecimal number (base 16) is divisible by 5 iff the sum of its
digits is divisible by 5 (because 16 is congruent mod 5 to 1)
.

Relevant Pages

  • Re: hi everyone, i had s.ome questions about holographic information
    ... post-offset need to be stored for each base representation, ... i've not come across any algorithms like it, but as i can just see it ... To have a stream type compression with advanced algorithms (even ... since in this analogy the data set size is only limited by the memory ...
    (comp.compression)
  • Re: n-ary representation and divisibility
    ... > times the leftmost group and add on the second leftmost group, ... > But we perform all these algorithms mostly under decimal representation ... What about for different n-ary representation? ... > for m-ary representation of a. ...
    (sci.math)
  • Representation of Triangle Meshes
    ... i'm currently searching for an adequate representation of triangle ... I know that the choice of representation heavily depends on the ... * meshes as indexed face lists stores pointers ... A lot of algorithms I deal with require fast access for neighborhood ...
    (comp.graphics.algorithms)
  • Re: Little Endian -> Big Endian (Ada95 / GNAT), Whats with floating point types?
    ... The OP was converting out of and back into the same representation. ... The algorithms were both published in Proceedings of the ACM SIGPLAN ... How to Print Floating Point Numbers Accurately. ... You can find free implementations of these algorithms in C at ...
    (comp.lang.ada)