(11C) Think of a Number

[Gamo]

Think of a number less than 316
Write down the remainders when that number is divided by 5, 7 and 9.
Using only those remainders this program should be able to reconstruct the original number.

Hints:
This program used the good old Chinese Remainder Theorem.

126 ≡ 1 mod 5
225 ≡ 1 mod 7
280 ≡ 1 mod 9
-------------------------------------------
Example: FIX 0 and USER mode

You gave me three remainders from your chosen number.

Those remainders are 3, 4 and 7

3 [A] display 3
4 [B] display 4
7 [C] display 7
[D] display 88

Your chosen number is 88
------------------------------------------
Program:

Quote:LBL A
STO 1
RTN
LBL B
STO 2
RTN
LBL C
STO 3
RTN
-----------
LBL D
126
RCL 1
x
225
RCL 2
x
280
RCL 3
x
+
+
315
GTO E
--------------
LBL E
STO 4
X<>Y
STO 5
X<>Y
÷
INT
RCL 4
x
RCL 5
X<>Y
-
RTN

Remark:
Label E can be use as a MOD functions to look for the remainder.

Gamo

[Albert Chan]

Amazingly, solution for { x≡a (mod 5), x≡b (mod 7), x≡c (mod 9) }, there is *NO* inverse to calculate

Let x' = a + 5m, a solution to 2 congruences.

mod 7: x' = a + 5m ≡ a - 2m ≡ b → m = (1/2)(a-b)

Note: fraction 1/2 really meant inverse of 2 (mod 7), not yet calculated
Note: since x' is a solution, we use "m = ...", not "m ≡ ..."

Let x'' = x' + 35n, a solution to 3 congruences.

mod 9: x'' = x' + 35n ≡ x' - n ≡ c → n = x' - c

x'' = x' + 35(x' - c) = 36(a + (5/2)(a-b)) - 35c = 126a - 90b - 35c

x'' (mod 315) ≡ 126a + 225b + 280c