(11C) Think of a Number

09122019, 06:24 AM
Post: #1




(11C) Think of a Number
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 Remark: Label E can be use as a MOD functions to look for the remainder. Gamo 

09122019, 03:41 PM
(This post was last modified: 09132019 12:18 PM by Albert Chan.)
Post: #2




RE: (11C) Think of a Number
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)(ab) 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)(ab))  35c = 126a  90b  35c x'' (mod 315) ≡ 126a + 225b + 280c 

« Next Oldest  Next Newest »

User(s) browsing this thread: 1 Guest(s)