+- HP Forums (https://www.hpmuseum.org/forum)
+-- Forum: HP Software Libraries (/forum-10.html)
+--- Forum: General Software Library (/forum-13.html)
+--- Thread: (11C) Think of a Number (/thread-13631.html)
(11C) Think of a Number - Gamo - 09-12-2019 06:24 AM
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
RE: (11C) Think of a Number - Albert Chan - 09-12-2019 03:41 PM
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