Re: n-ary representation and divisibility
- From: "Ed Hook" <hook@xxxxxxxxxxxx>
- Date: 30 May 2005 16:23:51 -0700
krill 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)For p=7:split the digits two by two from the leftmost digit; then 2
> times the leftmost group and add on the second leftmost group, and so
> on, till see if the sum divides by 7.
>
> (3)For p=11: split the digits two by two from the leftmost digit;
> them add the leftmost group on the second leftmost group, so on, till
> see if the final sum divides by 11.
>
> 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.
>
Let a = a_k m^k + a_{k-1} m^{k-1} + ... + a_1 m + a_0 and suppose
that a* = a_k 10^k + a_{k-1} 10^{k-1} + ... + a_1 10 + a_0.
By assumption, a = a* (mod p) - so a is divisible by p if and
only if a* is. That proves your claim -- note also that there's
no particular need to assume that p is prime ...
> Could anyone help me?
.
- References:
- n-ary representation and divisibility
- From: krill
- n-ary representation and divisibility
- Prev by Date: Re: derivative of a complex argument
- Next by Date: Re: analytic continuation of prime number function
- Previous by thread: Re: n-ary representation and divisibility
- Next by thread: lie algebra isomorphism
- Index(es):
Relevant Pages
|
