BZP says "Chinese Remainder Theorem"

[NotLKH]

FYI:

Given the numbers 0 thru n, if you use the First R Prime numbers, and mod them, Just so long as N < the Multple of the first R prime numbers, then you will end up with a unique numerical sequence that represents each such number.

ie..: Referencing the primes 2,3,and 5, the numbers 0 thru 7 could be seen as:


0=0,0,0
1=1,1,1
2=0,2,2
3=1,0,3
4=0,1,4
5=1,2,0
6=0,0,1
7=1,1,2

and so on...

Obviuosly Cols 1, 2, and 3 are the results of taking the Target number and Modding it by the prime whose index is identical to that of the columns.


But, heres the delema: How do you go in revers?


Well, if you only use the primes 2 and 3, the equation is:

Num = {3*Pos(Prime2) + 4*Pos(Prime3)} Mod 2*3

If you use 2,3, and 5:

Num = {15*Pos(Prime2) + 10*Pos(Prime3) + 6*Pos(Prime5)} Mod 2*3*5

and actually, its really simple to figure, once youve done your homework.

Check the attached table:

to be continued...





errr? Wheres the image???

[NotLKH]

Well, lets ignore the [IMG] tag problem for now.

If we refer to the table in the following manner, as seen in the next attached image: to be continued

[NotLKH]

So, ultimately, now that I've lost my train of thought, boils down to this series of examples:


Given 23 = 1 {mod 2}, 2 {mod 3}, 3 {mod 5}

Useing {1,2,3}

We see that

(15*1 + 10*2 + 6*3) Mod (2*3*5) = 23

and that:

91 = 1 {mod 2}, 1 {mod 3}, 1 {mod 5}, 0 {mod 7}

which shows us that:

(1*105 + 1*70 + 1*126 + 0*120} mod (2*3*5*7) = 91

So,

Given the set of the first k Prime numbers, if some number n < the multiple of those k prime numbers taken together,

if n = a set B of integers, which are the result of taking n and moding it individually by each of thos k prime numbers,

how do you, given that set B, calculate the original number n?

ie... How do you figure out the equation, or actually the multiples used in that equation?

its an interesting problem, dont'cha think?



-lou

[bugzpodder]

i am gonna do an example, you can generalize. let the primes be p,q,r

n=p*q*a1+p*r*a2+q*r*a3 (mod p*q*r)

and n=r1 (mod p), r2 (mod q) r3 (mod r)

hence we want to solve for r1,r2,r3

we have n=r1 (mod p)
so q*r*a3=r1 (mod p)
hence, introduce a variable x

q*r*a3=r1+p*x
which is linear diophantine equation in (x,a3) which can be solved easily by extended euclidean algorithm.
similarly you can find a2,a1

finally you have n