CHINESE REMAINDER THEOREM Author Roland Engdahl mr.engdahl@telia.com

Literature Kumanduri and Romero, Number theory with computer application Knuth, Seminumerical Algorthms, The Art of Computer Programming Cohn, Advanced Number Theory Let r[i] (remainders) and m[i] (moduli) be integers Study a system of n simultaneous congruences x \342\211\241 r[i] mod m[i] i = 1...n Given are the values of r[i] and m[i] Chinese Remainder Theorem Let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzZmcC1JJW1zdWJHRiQ2JS1JI21pR0YkNiVRIm1GJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictRiM2Jy1JI21uR0YkNiRRIjFGJy9GNlEnbm9ybWFsRidGMi8lK2ZvcmVncm91bmRHUSxbMjAwLDAsMjAwXUYnLyUscGxhY2Vob2xkZXJHRjRGNS8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnLUkjbW9HRiQ2LVEiLEYnRj4vJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRjQvJSlzdHJldGNoeUdGTi8lKnN5bW1ldHJpY0dGTi8lKGxhcmdlb3BHRk4vJS5tb3ZhYmxlbGltaXRzR0ZOLyUnYWNjZW50R0ZOLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdRLDAuMzMzMzMzM2VtRictRkk2LVEifkYnRj5GTC9GUEZORlFGU0ZVRldGWUZlbi9GaW5GZ24tRiw2JUYuLUYjNiUtRjs2JFEiMkYnRj5GMkY1RkVGSEZbby1GSTYtUSMuLkYnRj5GTEZeb0ZRRlNGVUZXRlkvRmZuUSwwLjIyMjIyMjJlbUYnRl9vLUZJNi1RIi5GJ0Y+RkxGXm9GUUZTRlVGV0ZZRmVuRl9vRkgtRiw2JUYuLUYjNiUtRi82JVEibkYnRjJGNUYyRjVGRUZbby1GLzYlUSNiZUYnRjJGNUZbby1GLzYlUSlwYWlyd2lzZUYnRjJGNUZbby1GLzYlUStyZWxhdGl2ZWx5RidGMkY1RltvLUYvNiVRJnByaW1lRidGMkY1RltvLUYvNiVRKWludGVnZXJzRidGMkY1RlxwLUknbXNwYWNlR0YkNiYvJSdoZWlnaHRHUSYwLjBleEYnLyUmd2lkdGhHRmduLyUmZGVwdGhHRmpxLyUqbGluZWJyZWFrR1EobmV3bGluZUYnRltvLUYvNiVRJVRoZW5GJ0YyRjVGW28tRi82JVEkdGhlRidGMkY1RltvLUYvNiVRLXNpbXVsdGFuZW91c0YnRjJGNUZbby1GLzYlUStjb25ncnVlbmNlRidGMkY1RmVxRltvLUYvNiVRInhGJ0YyRjVGW28tRkk2LVEoJmVxdWl2O0YnRj5GTEZeb0ZRRlNGVUZXRlkvRmZuUSwwLjI3Nzc3NzhlbUYnL0ZpbkZlc0Zbby1GLDYlLUYvNiVRInJGJ0YyRjUtRiM2JUY6RjJGNUZFRltvRltvLUZJNi9RJG1vZEYnLyUlYm9sZEdGNC9GNlElYm9sZEYnLyUrZm9udHdlaWdodEdGZHRGTEZeb0ZRRlNGVUZXRllGZW5GX29GW28tRiw2JUYuRlx0RkUtRi82I1EhRidGZXFGW29GZ29GZ29GZXFGW29GXnNGW29GYXNGW28tRiw2JUZpc0ZhcEZFRltvRltvRltvRl50RltvRl9wRml0RmVxRltvLUYvNiVRJGhhc0YnRjJGNUZbby1GLzYlUSJhRidGMkY1RltvLUYvNiVRJ3VuaXF1ZUYnRjJGNUZbby1GLzYlUSlzb2x1dGlvbkYnRjJGNUZbby1GLzYlUSdtb2R1bG9GJ0YyRjVGW29GZXJGW28tRi82JVEocHJvZHVjdEYnRjJGNUZbb0YrRltvRmBvRltvRmdvRlxwRltvRl9wRml0RmVxLUZmcTYmRmhxRltyRl1yL0ZgclElYXV0b0YnRml0Rj4= A constructive PROOF at the the MAIN PROGRAM below Generalizaton of the theorem above (without pairwise relatively prime) ...The system of congruences x \342\211\241 LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY1LUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEickYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYlLUYvNiVRImlGJ0YyRjVGMkY1LyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYtUSJ+RicvRjZRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZILyUpc3RyZXRjaHlHRkgvJSpzeW1tZXRyaWNHRkgvJShsYXJnZW9wR0ZILyUubW92YWJsZWxpbWl0c0dGSC8lJ2FjY2VudEdGSC8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlctRkE2L1EkbW9kRicvJSVib2xkR0Y0L0Y2USVib2xkRicvJStmb250d2VpZ2h0R0ZqbkZGRklGS0ZNRk9GUUZTRlVGWEZALUYsNiUtRi82JVEibUYnRjJGNUY4Rj1GQEZARkBGQEZARjpGQC1GQTYtUSI9RidGREZGRklGS0ZNRk9GUUZTL0ZWUSwwLjI3Nzc3NzhlbUYnL0ZZRmZvRkAtSSNtbkdGJDYkUSIxRidGRC1GQTYtUSMuLkYnRkRGRkZJRktGTUZPRlFGUy9GVlEsMC4yMjIyMjIyZW1GJ0ZYLUZBNi1RIi5GJ0ZERkZGSUZLRk1GT0ZRRlNGVUZYLUYvNiVRIm5GJ0YyRjVGRA== has a solution if and only if for all i \342\211\240 j GCD(LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY6LUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYlLUYvNiVRImlGJ0YyRjVGMkY1LyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYtUSJ+RicvRjZRJ25vcm1hbEYnLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZILyUpc3RyZXRjaHlHRkgvJSpzeW1tZXRyaWNHRkgvJShsYXJnZW9wR0ZILyUubW92YWJsZWxpbWl0c0dGSC8lJ2FjY2VudEdGSC8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlctRkE2LVEiLEYnRkRGRi9GSkY0RktGTUZPRlFGU0ZVL0ZZUSwwLjMzMzMzMzNlbUYnRkAtRiw2JUYuLUYjNiUtRi82JVEiakYnRjJGNUYyRjVGPS1GQTYtUSIpRidGRC9GR0Y0RkkvRkxGNEZNRk9GUUZTL0ZWUSwwLjE2NjY2NjdlbUYnL0ZZRmdvRkAtRi82JVEjaXNGJ0YyRjVGQC1GLzYlUSJhRidGMkY1RkAtRi82JVEoZGl2aXNvckYnRjJGNUZARkAtRi82JVEjb2ZGJ0YyRjVGQC1GLzYlUSRhYnNGJy9GM0ZIRkQtSShtZmVuY2VkR0YkNiQtRiM2KC1GLDYlLUYvNiVRInJGJ0YyRjVGOEY9RkAtRkE2LVEqJnVtaW51czA7RidGREZGRklGS0ZNRk9GUUZTL0ZWUSwwLjIyMjIyMjJlbUYnL0ZZRmdxRkAtRiw2JUZgcUZcb0Y9RkRGRC1GLzYjUSFGJy1JJ21zcGFjZUdGJDYmLyUnaGVpZ2h0R1EmMC4wZXhGJy8lJndpZHRoR0ZXLyUmZGVwdGhHRmNyLyUqbGluZWJyZWFrR1EobmV3bGluZUYnRkAtRl9yNiZGYXJGZHJGZnIvRmlyUSVhdXRvRidGQEZE For given r[i] and m[i] i= 1 ... n we wish to determine x (if it exists) DESIGN 1. Is there is a solution to the system? Y there is go to 2 ... N otherwise break 2. There is a solution are the moduli pairwise relative prime? Y go to 3 Main Program N otherwise factorize the moduli and make a new list of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYlLUYvNiVRImlGJ0YyRjVGMkY1LyUvc3Vic2NyaXB0c2hpZnRHUSIwRicvRjZRJ25vcm1hbEYn then go to 3 3. Solve with Main Program

The system has a solution if and only if for all i \342\211\240 k GCD(m[i],m[k]) is a divisor to abs(r[i]-r[k]) restart:n:=6:so:=true: m[1]:=473:r[1]:=322: m[2]:=517:r[2]:=476: m[3]:=611:r[3]:=241: m[4]:=637:r[4]:=163: m[5]:=651:r[5]:=100: m[6]:=657:r[6]:=565: for i from 1 to n-1 do for k from (i+1) to n do if (abs(r[i]-r[k]) mod gcd(m[i],m[k]))<>0 then so:=false end if; end end; if so then "there is a solution" else "there is NO solution" end if; for i from 1 to n do mc[i]:=m[i] end do:nc:=n: This line pc[i] to keep m[i] for control after calculatiom

UTR0aGVyZX5pc35hfnNvbHV0aW9uNiI=

LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYjLUkjbWlHRiQ2I1EhRic= If there is no solution BREAK else CONTINUE

relpr:=true: for i from 1 to n-1 do for k from (i+1) to n do if gcd(m[i],m[k]) <>1 then relpr:=false end if end end: if relpr then "CONTINUE WITH MAIN PROGRAM" else "CONTINUE WITH Factorize" end if;

UThDT05USU5VRX5XSVRIfkZhY3Rvcml6ZTYi

Factorize the moduli for i from 1 to n do ifactor (m[i]) end do;

KiYtSSFHNiI2IyIjNiIiIi1GJDYjIiNWRig=

KiYtSSFHNiI2IyIjNiIiIi1GJDYjIiNaRig=

KiYtSSFHNiI2IyIjOCIiIi1GJDYjIiNaRig=

KiYtSSFHNiI2IyIiKCIiIy1GJDYjIiM4IiIi

KigtSSFHNiI2IyIiJCIiIi1GJDYjIiIoRigtRiQ2IyIjSkYo

KiYtSSFHNiI2IyIiJCIiIy1GJDYjIiN0IiIi

METHOD for transforming the moduli to RELATIVLY PRIME INTEGERS If a solution exists and the moduli are not relatively prime we can construct a new system where the moduli are relatively prime by using the follwing simple observation: Assume u>0, v>0 m = u*v Every congruence class modulo m corresponds to a unique pair of classes, that is, x \342\211\241 y (mod m) \342\207\222x \342\211\241 y (mod u) and x \342\211\241 y (mod v) GCD(u,v) = 1 \342\207\222 every pair of congruence classes mod u and mod v corresponds to a single congruence class mod m = u*v Here we have the factors as primes or a power of primes The table of results for factorize we designate above L1, L2 ... L6 Acccording to the lemma We split up L1 in two parts 11 and 43 and keep the remainder 322. We split up L2 in two parts 11 and 47 and keep the remainder 476 We split up L3 in two parts 13 and 47 and keep the remainder 241 In L1 and L2 we have the same prime (11) and they are in the same congruence class so we can exclude one of them, say 11 in L2 In L2 and L3 we have the same prime (47) 47 in L2 Thus L2 is empty Preserved in the example Ex A below are lines m[1],...,m[4] For prime powers take only the highest power In L4 we have (7^2) so exlcude (7) in L5 In L6 we have (3^2) so exclude (3) in L5 New table for m[i] in example Ex A in MAIN PROGRAM below. LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzZlXGwtSSNtaUdGJDYlUSVLZWVwRicvJSdpdGFsaWNHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JI21vR0YkNi1RIn5GJ0YyLyUmZmVuY2VHRjEvJSpzZXBhcmF0b3JHRjEvJSlzdHJldGNoeUdGMS8lKnN5bW1ldHJpY0dGMS8lKGxhcmdlb3BHRjEvJS5tb3ZhYmxlbGltaXRzR0YxLyUnYWNjZW50R0YxLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGSS1GLDYlUSRhbGxGJ0YvRjJGNS1GLDYlUSR0aGVGJ0YvRjJGNS1GLDYlUStyZW1haW5kZXJzRidGL0YyRjUtRiw2JVEld2l0aEYnRi9GMkY1LUYsNiVRKGNvcnJlY3RGJ0YvRjJGNS1GLDYlUSpudW1iZXJpbmdGJ0YvRjItRjY2LVEiIUYnRjJGOUY7Rj1GP0ZBRkNGRS9GSFEsMC4xMTExMTExZW1GJy9GS0Zcby1JJ21zcGFjZUdGJDYmLyUnaGVpZ2h0R1EmMC4wZXhGJy8lJndpZHRoR0ZJLyUmZGVwdGhHRmNvLyUqbGluZWJyZWFrR1EobmV3bGluZUYnRjUtRjY2L0Y4LyUlYm9sZEdRJXRydWVGJy9GM1ElYm9sZEYnLyUrZm9udHdlaWdodEdGYXBGOUY7Rj1GP0ZBRkNGRUZHRkotRiw2J1EmVGhlcmVGJ0ZdcC9GMEZfcC9GM1EsYm9sZC1pdGFsaWNGJ0ZicEZbcC1GLDYnUSNpc0YnRl1wRmdwRmhwRmJwRltwLUYsNidRJW1vcmVGJ0ZdcEZncEZocEZicEZbcC1GLDYnUSV0aGFuRidGXXBGZ3BGaHBGYnBGW3AtRiw2J1Ekb25lRidGXXBGZ3BGaHBGYnBGW3AtRiw2J1Ekd2F5RidGXXBGZ3BGaHBGYnBGW3AtRjY2L1EjdG9GJ0ZdcEZgcEZicEY5RjtGPUY/RkFGQ0ZFRkdGSkZbcC1GLDYnUSVtYWtlRidGXXBGZ3BGaHBGYnBGW3BGW3AtRiw2J0ZRRl1wRmdwRmhwRmJwRltwLUYsNidRJ2Nob2ljZUYnRl1wRmdwRmhwRmJwRmhuRl5vRjUtRiw2J1EjSW5GJ0ZdcEYvRmBwRmJwRltwLUYsNidRJEV4QUYnRl1wRi9GYHBGYnBGW3AtRiw2J1Ejd2VGJ0ZdcEYvRmBwRmJwRltwLUYsNidRJHB1dEYnRl1wRi9GYHBGYnBGW3AtRiw2J1EpdG9nZXRoZXJGJ0ZdcEYvRmBwRmJwRltwLUYsNidRIm1GJ0ZdcEYvRmBwRmJwLUkobWZlbmNlZEdGJDYoLUYjNiYtSSNtbkdGJDYmUSIxRidGXXBGYHBGYnBGXXBGYHBGYnBGXXBGYHBGYnAvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGW3AtRjY2L1EkYW5kRidGXXBGYHBGYnBGOUY7Rj1GP0ZBRkNGRUZHRkpGW3BGY3MtRmdzNigtRiM2Ji1GXHQ2JlEiMkYnRl1wRmBwRmJwRl1wRmBwRmJwRl1wRmBwRmJwRl90RmJ0LUYsNiNRIUYnRl5vRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRltwRmNzLUZnczYoLUYjNiYtRlx0NiZRIjNGJ0ZdcEZgcEZicEZdcEZgcEZicEZdcEZgcEZicEZfdEZidEZbcEZldEZbcEZjcy1GZ3M2KC1GIzYmLUZcdDYmUSI0RidGXXBGYHBGYnBGXXBGYHBGYnBGXXBGYHBGYnBGX3RGYnRGX3VGXm9GW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGW3BGY3MtRmdzNiYtRiM2Ji1GXHQ2JlEiN0YnRl1wRmBwRmJwRl1wRmBwRmJwRl1wRmBwRmJwRltwRmV0RltwRmNzLUZnczYlLUYjNiQtRlx0NiZRIjhGJ0ZdcEZgcEZicEYyRjJGX3RGX3VGXm9GNS1GNjYwRmd0Rl1wRmdwRmhwRmJwRjlGO0Y9Rj9GQUZDRkVGR0ZKLUY2NjBGOEZdcEZncEZocEZicEY5RjtGPUY/RkFGQ0ZFRkdGSi1GLDYnUSRnZXRGJ0ZdcEZncEZocEZicEZgdy1GLDYnUSNFeEYnRl1wRmdwRmhwRmJwRmB3LUYsNidRIkJGJ0ZdcEZncEZocEZicEZeb0Y1Rl5vRjUtRiw2J1EjSWZGJ0ZdcEYvRmBwRmJwRltwRmpyRltwLUYsNidRKGV4Y2x1ZGVGJ0ZdcEYvRmBwRmJwRltwLUZcdDYmUSMxMUYnRl1wRmBwRmJwRltwLUYsNidRKGluc3RlYWRGJ0ZdcEYvRmBwRmJwRltwLUY2Ni9RI2luRidGXXBGYHBGYnBGOUY7Rj1GP0ZBRkNGRUZHRkpGW3AtRiw2J1EjTDFGJ0ZdcEYvRmBwRmJwRltwRltwLUYsNidGXHNGXXBGZ3BGaHBGYnBGYHdGYndGYHdGZXdGYHctRiw2J1EiQ0YnRl1wRmdwRmhwRmJwRltwRmV0RltwLUYsNidRI25vRidGXXBGL0ZgcEZicEZbcC1GLDYnUSZlbXB0eUYnRl1wRi9GYHBGYnBGW3AtRiw2J1ElbGluZUYnRl1wRi9GYHBGYnBGXm9GW3BGXm9GW3AtRiw2J1EkWW91RidGXXBGZ3BGaHBGYnBGW3AtRiw2J1Eld2lsbEYnRl1wRmdwRmhwRmJwRltwLUYsNidRJWZpbmRGJ0ZdcEZncEZocEZicEZbcC1GLDYnUSV0aGF0RidGXXBGZ3BGaHBGYnBGW3BGZ3hGW3AtRiw2J0ZORl1wRmdwRmhwRmJwRltwRl9yRltwLUYsNidRKWV4YW1wbGVzRidGXXBGZ3BGaHBGYnBGW3AtRiw2J1EkeW91RidGXXBGZ3BGaHBGYnBGW3BGYndGW3AtRmdzNiYtRiM2KC1GLDYnUSNvZkYnRl1wRmdwRmhwRmJwRltwLUYsNidRJ2NvdXJzZUYnRl1wRmdwRmhwRmJwRl1wRmBwRmJwRl1wRmBwRmJwRltwRl9yRltwLUYsNidRJXNhbWVGJ0ZdcEZncEZocEZicEZbcC1GLDYnUSdyZXN1bHRGJ0ZdcEZncEZocEZicEZbcEZeb0ZbcEZbcC1GLDYnUSVURVNURidGXXBGZ3BGaHBGYnBGW3BGW3AtRiw2J1ElV0lUSEYnRl1wRmdwRmhwRmJwRltwLUYsNidRKENPTlRST0xGJ0ZdcEZncEZocEZicEZbcC1GLDYnUSNPRkYnRl1wRmdwRmhwRmJwRltwLUYsNidRJ1JFU1VMVEYnRl1wRmdwRmhwRmJwRltwRltwRltwRltwRltwRl5vRjVGXm9GNS1GLDYlUSZCZWxvd0YnRi9GMkY1LUYsNiVRJnRocmVlRidGL0YyRjUtRiw2JUZbW2xGL0YyRjUtRiw2JVElSnVtcEYnRi9GMkY1LUY2Ni5RJGZvckYnL0ZecEYxRjJGOUY7Rj1GP0ZBRkNGRUZHRkpGNS1GLDYlUSJhRidGL0YyRjUtRiw2JUZjckYvRjJGNS1GNjYuRmd0RlxebEYyRjlGO0Y9Rj9GQUZDRkVGR0ZKRjUtRjY2LlEldGhlbkYnRlxebEYyRjlGO0Y9Rj9GQUZDRkVGR0ZKRjUtRiw2JVEnZGlyZWN0RidGL0YyRjUtRjY2LkZbckZcXmxGMkY5RjtGPUY/RkFGQ0ZFRkdGSkY1LUYsNiVRKnByb2NlZHVyZUYnRi9GMkY1RmhuRmhuRmhuRjI=

Ex A r[1]:=322:m[1]:=11: r[2]:=322:m[2]:=43: r[3]:=241:m[3]:=13: r[4]:=241:m[4]:=47: r[5]:=163:m[5]:=49: r[6]:=100:m[6]:=31: r[7]:=565:m[7]:=9: r[8]:=565:m[8]:=73: n:=8: LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EjRXhGJy8lJWJvbGRHUSV0cnVlRicvJSdpdGFsaWNHRjEvJSxtYXRodmFyaWFudEdRLGJvbGQtaXRhbGljRicvJStmb250d2VpZ2h0R1ElYm9sZEYnLUkjbW9HRiQ2L1EifkYnRi8vRjVGOUY3LyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZBLyUpc3RyZXRjaHlHRkEvJSpzeW1tZXRyaWNHRkEvJShsYXJnZW9wR0ZBLyUubW92YWJsZWxpbWl0c0dGQS8lJ2FjY2VudEdGQS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlAtRiw2J1EiQkYnRi9GMkY0Rjc=

KiZJI0V4RzYiIiIiSSJCR0YkRiU=

r[1]:=322:m[1]:=11*43: r[2]:=241:m[2]:=47*13: r[3]:=163:m[3]:=49: r[4]:=100:m[4]:=31: r[5]:=565:m[5]:=9*73: n:=5: LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2J1EjRXhGJy8lJWJvbGRHUSV0cnVlRicvJSdpdGFsaWNHRjEvJSxtYXRodmFyaWFudEdRLGJvbGQtaXRhbGljRicvJStmb250d2VpZ2h0R1ElYm9sZEYnLUkjbW9HRiQ2L1EifkYnRi8vRjVGOUY3LyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZBLyUpc3RyZXRjaHlHRkEvJSpzeW1tZXRyaWNHRkEvJShsYXJnZW9wR0ZBLyUubW92YWJsZWxpbWl0c0dGQS8lJ2FjY2VudEdGQS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlAtRiw2J1EiQ0YnRi9GMkY0Rjc=

KiZJI0V4RzYiIiIiSSJDR0YkRiU=

r[1]:=322:m[1]:=43: r[2]:=476:m[2]:=11: r[3]:=241:m[3]:=47*13: r[4]:=163:m[4]:=49: r[5]:=100:m[5]:=31: r[6]:=565:m[6]:=9*73: n:=6: inver:=proc(x::integer,y::integer)::integer; local te,t,s,d,q,r; global u,a,b; te:=y: s:=1:t:=0:a:=x;b:=y;r:=1: while r>0 do q:=iquo(a,b):r:=a mod b: a:=b:b:=r:d:=s-t*q: s:=t:t:=d: end do; if s<0 then s:=s+te: end if; u:=s; u; end proc: Mp:=1:for i from 1 to n do Mp:=Mp*m[i] end do: for i from 1 to n do Mq[i]:=iquo(Mp,m[i]) end do: for i from 1 to n do x[i]:=inver(Mq[i],m[i]) end do: xp:=0: for i from 1 to n do xp:=xp+ r[i]*Mq[i]*x[i] end do:xp:=xp mod Mp;

IixJIj4pPihc

PROOF of Chinese Remainder Theorem Quotation from Kumanduri and Romero (notation changed a little to fit a Maple program) A Let Mp = LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYsLUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYkLUkjbW5HRiQ2JFEiMUYnL0YzUSdub3JtYWxGJ0Y+Rj4vJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRictSSNtb0dGJDYtUSJ+RidGPi8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGTC8lKXN0cmV0Y2h5R0ZMLyUqc3ltbWV0cmljR0ZMLyUobGFyZ2VvcEdGTC8lLm1vdmFibGVsaW1pdHNHRkwvJSdhY2NlbnRHRkwvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZlbkYrLUY2NiYtRiM2JC1GOzYkUSIyRidGPkY+Rj5GQEZDLUZHNi1RIy4uRidGPkZKRk1GT0ZRRlNGVUZXL0ZaUSwwLjIyMjIyMjJlbUYnRmZuLUZHNi1RIi5GJ0Y+RkpGTUZPRlFGU0ZVRldGWUZmbkYrLUY2NiYtRiM2JC1GLDYlUSJuRidGL0YyRj5GPkZARkNGPg== B Let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEjTXFGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRictSShtZmVuY2VkR0YkNiYtRiM2JC1GLDYlUSJpRidGL0YyL0YzUSdub3JtYWxGJ0Y9LyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnRj0== Mp / LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYkLUYsNiVRImlGJ0YvRjIvRjNRJ25vcm1hbEYnRj0vJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGPQ== Since the LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYkLUYsNiVRImlGJ0YvRjIvRjNRJ25vcm1hbEYnRj0vJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRictSSNtb0dGJDYtUSJ+RidGPS8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGSy8lKXN0cmV0Y2h5R0ZLLyUqc3ltbWV0cmljR0ZLLyUobGFyZ2VvcEdGSy8lLm1vdmFibGVsaW1pdHNHRksvJSdhY2NlbnRHRksvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZaRkUtRiw2JVEkYXJlRidGL0YyRkVGPQ==pairwise relatively prime, Mq[i]LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbW9HRiQ2LVEifkYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZDRi8=is relatively prime to m[i] C so it has an inverse LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbW9HRiQ2LVEifkYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZDRitGK0Yvx[i] modulo m[i] that LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY6LUkjbW9HRiQ2LVEifkYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZDLUkjbWlHRiQ2JVEjaXNGJy8lJ2l0YWxpY0dRJXRydWVGJy9GMFEnaXRhbGljRidGK0YrLUZHNiVRInhGJ0ZKRk0tSShtZmVuY2VkR0YkNiYtRiM2JC1GRzYlUSJpRidGSkZNRi9GLy8lJW9wZW5HUSJbRicvJSZjbG9zZUdRIl1GJ0YrLUYsNi1RIi5GJ0YvRjJGNUY3RjlGO0Y9Rj9GQUZERistRkc2JVEjTXFGJ0ZKRk1GUkYrLUYsNi1RIj1GJ0YvRjJGNUY3RjlGO0Y9Rj8vRkJRLDAuMjc3Nzc3OGVtRicvRkVGZG9GKy1JI21uR0YkNiRRIjFGJ0YvRitGKy1GLDYvUSRtb2RGJy8lJWJvbGRHRkwvRjBRJWJvbGRGJy8lK2ZvbnR3ZWlnaHRHRmBwRjJGNUY3RjlGO0Y9Rj9GQUZERistRkc2JVEibUYnRkpGTUZSRitGK0Yv If i \342\211\240 k then LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzY7LUkjbWlHRiQ2JVEibUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2Ji1GIzYkLUYsNiVRImlGJ0YvRjIvRjNRJ25vcm1hbEYnRj0vJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRictSSNtb0dGJDYtUSJ+RidGPS8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGSy8lKXN0cmV0Y2h5R0ZLLyUqc3ltbWV0cmljR0ZLLyUobGFyZ2VvcEdGSy8lLm1vdmFibGVsaW1pdHNHRksvJSdhY2NlbnRHRksvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZaRkUtRiw2JVEoZGl2aXNvckYnRi9GMkZFLUZGNi9RI3RvRicvJSVib2xkR0YxL0YzUSVib2xkRicvJStmb250d2VpZ2h0R0Zgb0ZJRkxGTkZQRlJGVEZWRlhGZW5GRUZFLUYsNiVRI01xRidGL0YyLUY2NiYtRiM2JC1GLDYlUSJrRidGL0YyRj1GPUY/RkJGRUZFRkVGRS1GLDYlUSV0aGF0RidGL0YyRkUtRiw2JVEjaXNGJ0YvRjJGRUZFRkVGRUZjb0Zmb0Y9LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYwLUkjbW9HRiQ2LVEifkYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGNC8lKXN0cmV0Y2h5R0Y0LyUqc3ltbWV0cmljR0Y0LyUobGFyZ2VvcEdGNC8lLm1vdmFibGVsaW1pdHNHRjQvJSdhY2NlbnRHRjQvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZDLUYsNi1RKCZlcXVpdjtGJ0YvRjJGNUY3RjlGO0Y9Rj8vRkJRLDAuMjc3Nzc3OGVtRicvRkVGSkYrLUkjbW5HRiQ2JFEiMEYnRi9GK0YrLUYsNi9RJG1vZEYnLyUlYm9sZEdRJXRydWVGJy9GMFElYm9sZEYnLyUrZm9udHdlaWdodEdGV0YyRjVGN0Y5RjtGPUY/RkFGREYrRistSSNtaUdGJDYlUSJtRicvJSdpdGFsaWNHRlUvRjBRJ2l0YWxpY0YnLUkobWZlbmNlZEdGJDYmLUYjNiQtRmVuNiVRImlGJ0ZobkZqbkYvRi8vJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGK0YrRi8= D Then xp = r[1] Mq[1] x[1] + r[2] Mq[2] x[2] + ... + r[n] Mq[n] x[n] mod Mp The solution is unique mod Mp (The proof is easy)

for i from 1 to nc do rc[i]:=xp mod mc[i] end do;

IiRBJA==

IiR3JQ==

IiRUIw==

IiRqIg==

IiQrIg==

IiRsJg==

m[1]:= 23916497: m[2]:= 31663333: m[3]:= 43817891: m[4]:= 43716739: r[1]:= 16967183: r[2]:= 11431757: r[3]:= 42314739: r[4]:= 36345245: In the result the first seven digits is the N latitude and the last eight digits the E longitude The format is N XLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzZKLUklbXN1cEdGJDYlLUkjbWlHRiQ2JVEiWEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYlLUkjbW9HRiQ2LVEpJmNvbXBmbjtGJy9GNlEnbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRkIvJSlzdHJldGNoeUdGQi8lKnN5bW1ldHJpY0dGQi8lKGxhcmdlb3BHRkIvJS5tb3ZhYmxlbGltaXRzR0ZCLyUnYWNjZW50R0ZCLyUnbHNwYWNlR1EsMC4xNjY2NjY3ZW1GJy8lJ3JzcGFjZUdGUUYyRjUvJTFzdXBlcnNjcmlwdHNoaWZ0R1EiMEYnRi4tRiw2JUYuLUYjNiUtRjs2LVEoJnByaW1lO0YnRj5GQEZDRkVGR0ZJRktGTS9GUFEsMC4xMTExMTExZW1GJy9GU1EmMC4wZW1GJ0YyRjVGVC1GOzYtUSIuRidGPkZARkNGRUZHRklGS0ZNL0ZQRltvRmpuLUYvNiVRJHh4eEYnRjJGNS1JJ21zcGFjZUdGJDYmLyUnaGVpZ2h0R1EmMC4wZXhGJy8lJndpZHRoR0Zbby8lJmRlcHRoR0Zoby8lKmxpbmVicmVha0dRKG5ld2xpbmVGJy1GOzYtUSJ+RidGPkZARkNGRUZHRklGS0ZNRl9vRmpuRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwRmBwLUYvNiVRIkVGJ0YyRjVGYHBGYHBGYHAtRi82JVEjWVlGJ0YyRjUtRiw2JS1GLzYlUSJZRidGMkY1LUYjNidGOkYyLyUrZm9yZWdyb3VuZEdRLFsyMDAsMCwyMDBdRicvJSxwbGFjZWhvbGRlckdGNEY1RlRGW3EtRiw2JUZbcS1GLzYjUSFGJ0ZURj4=\342\200\262.yyy With luck you will find my coordinates (mr.engdahl@telia.com choose subject as Chinese cache) JSFH Legal Notice: The copyright for this application is owned by the author(s). Neither Maplesoft nor the author are responsible for any errors contained within and are not liable for any damages resulting from the use of this material. This application is intended for non-commercial, non-profit use only. Contact the author for permission if you wish to use this application in for-profit activities.