 (11C) Think of a Number - Printable Version +- 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