Re: Prime Factorization and Digit Congruence

From: Daniel W. Johnson (panoptes_at_iquest.net)
Date: 07/18/04 

Date: Sun, 18 Jul 2004 00:35:03 -0500

Ross A. Finlayson <raf@tiki-lounge.com> wrote:

> That might be so, but why then does seven need multiples of three
> grouped in decimal?

Because 7 is a factor of 1001, but not of 11 or 101.

Consider a number written as a3*1000^3 + a2*1000^2 + a1*1000^1 +
a0*1000^0, where a0, a1, a2, and a3 can take values from 0 up to 999.

This number is equal to (a0-a1+a2-a3) + 1001*(a1 + 999*a2 + 999001*a3)

The difference between the original number and (a0-a1+a2-a3) is clearly
a multiple of 1001 and therefore of 7. Thus, the two numbers are either
both divisible by 7 or neither divisible by 7.

If you are interested in a divisor which happens to be a factor of 999
rather than 1001, the relevant expression would be (a0+a1+a2+a3) +
999*(a1 + 1001*a2 + 1001001*a3).

> I haven't really done much work on this yet, I would like to implement
> the algorithm in a well-specified way for high-performance extended
> precision integer arithmetic.
>
> I noticed that x | b^3+1, x evenly divides into the value of the base
> cubed, plus one, but that might be a red herring and not a true
> indicator of the ability to consider the digits as a set besides as
> representing the large composite (or perhaps prime).

x being a factor of b^3+1 is equivalent to b^3 being congruent to -1
modulo x. The congruence of b^3 and -1 modulo x is equivalent to the
ability to replace (a1*b^3 + a0) with (a0 - a1) in a test for
divisibility by x.

Or to look at this another way: If you can alternate adding and
subtracting groups of 3 digits when checking for divisibility by x, what
happens when you check b^3+1 for divisibility by x that way?

> So, then I'm trying to figure out some more general forms for base b
> and values x. Also, there are probably various consideration where
> there are different sized groupings instead of one or three, in terms
> of alternately adding and subtracting the digits in a higher base that
> is a power of the lower base. As well, there are linear relations
> that allow simple functions upon the coefficients to scale the
> coefficients in the various moduli's contribution to the even
> multiple.

If x is a factor of b^k-1, you can add successive groups of k digits in
base b when checking for divisibility by x. If x is a factor of b^k+1,
you can alternating adding and subtracting groups of k digits when
checking for divibility by x. And vice versa on both (consider b^k+x-1
and b^k+1, respectively). 

-- 
Daniel W. Johnson
panoptes@iquest.net
http://members.iquest.net/~panoptes/
039 53 36 N / 086 11 55 W

Relevant Pages