QUANTUM COMPUTING - EXAMPLE 32.4 : A system of linear congruences consists of 3 equations : X ≡ 1 (mod 2), X ≡ 3 (mod 3), X ≡ 4 (mod 5). X has positive values. (a)(i) List the values of these equations from 1 to approximately 40. (ii) Find the first smallest value and second smallest value of X. (iii) Guess the third smallest value of X. (b) Let X ≡ Aa (mod Ma), X ≡ Ab (mod Mb), X ≡ Ac (mod Mc). According to Chinese remainder theorem, X ≡ (Aa x Ya x Md + Ab x Yb x Me + Ac x Yc x Mf) [ mod (Ma x Mb x Mc) ]. (i) Show that Ma, Mb and Mc have the greatest common divisor of Ma x Mb x Mc. (ii) Find the values of Md, Me and Mf if Md = Mb x Mc, Me = Ma x Mc and Mf = Ma x Mb. (iii) Find the values of Ya, Yb and Yc if Ya = Remainder of (Md / Ma), Yb = Remainder of (Me / Mb) and Yc = Remainder of (Mf / Mc). (iv) Use Chinese remainder theorem to find X.
- 1 Answers
- 1907 Views
- I also Faced
- E-Mail Answers
Answer Posted / kangchuentat
QUANTUM COMPUTING - ANSWER 32.4 : (a)(i) 1 (mod 2) = 1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39. 3 (mod 3) = 3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39. 4 (mod 5) = 4, 9, 14, 19, 24, 29, 34, 39. (ii) By observation on X, 3 equations have common values of 9 and 39. First smallest value = 9, second smallest value = 39. (iii) Third smallest value = second smallest value + (second smallest value - first smallest value) = 39 + (39 - 9) = 69. (b)(i) Let Ma = 2, Mb = 3, Mc = 5 where they are prime numbers. Their greatest common divisor is 2 x 3 x 5 = Ma x Mb x Mc (shown). (ii) Md = Mb x Mc = 3 x 5 = 15, Me = Ma x Mc = 2 x 5 = 10, Mf = Ma x Mb = 2 x 3 = 6. (iii) Ma = 2, Mb = 3, Mc = 5, Md = 15, Me = 10, Mf = 6. Md / Ma = 15 / 2 = 7 remain 1, Ya = 1. Me / Mb = 10 / 3 = 3 remain 1, Yb = 1. Mf / Mc = 6 / 5 = 1 remain 1, Yc = 1. (iv) Let Aa = 1, Ab = 3, Ac = 4, Ya = 1, Yb = 1, Yc = 1, Ma = 2, Mb = 3, Mc = 5, Md = 15, Me = 10, Mf = 6. X ≡ (Aa x Ya x Md + Ab x Yb x Me + Ac x Yc x Mf) [ mod (Ma x Mb x Mc) ] = (1 x 1 x 15 + 3 x 1 x 10 + 4 x 1 x 6) [ mod (2 x 3 x 5) ] = 69 mod 30 = 39 mod 30 = 9 mod 30. The answer is given by Kang Chuen Tat; PO Box 6263, Dandenong, Victoria VIC 3175, Australia; SMS +61405421706; chuentat@hotmail.com; http://kangchuentat.wordpress.com.
| Is This Answer Correct ? | 0 Yes | 0 No |
Post New Answer View All Answers
Explain global warming from a common man's and an engineer's perspective?
Explain what are the affinity laws associated with dynamics pumps?
What is the method of determining maximum differential pressure during hydro testing of shell and tube heat exchangers?
What is a good source of information for the design of pressure vessels?
What is the angle of repose?
What effect does choking a vertical thermosiphon have on the heat transfer rate?
Explain how can you estimate a gas flow based on two pressure measurements?
Explain what types of metals are typically removed via chemical precipitation?
what is the hearth and arch pressure in furnace?
Explain the different ways in which solids can be blended?
What are the reasons of removal of particles from effluent gas?
Can condensate control in a reboiler cause water hammer problems?
what is mass flow rate of steam of 7 kg/cm2 pressure in 1 inch id. pipe.
List the advantages and disadvantages of a pfr?
What are angle of repose applications in the chemical industry?
