(a) (i) Without using the Euclidean algorithm, write down integers s, t such that 1 = 4s + 9t, and use your answer to find the inverse of 4 mod 9. Hence, replace the congruence 4x = 5 mod 9 with one of the form x = a mod 9. (ii) Without using the Euclidean algorithm, write down integers u, v such that 1 = 3u + 22v, and use your answer to find the inverse of 3 mod 22. Hence, replace the congruence 3x = 19 mod 22 with one of the form x = b mod 22. (b) Use your answers to part (a) to solve the simultaneous congruences 4x = 5 mod 9 3x = 19 mod 22 Give your answer as a single congruence x = c mod n for an appropri- ate positive integer n and an appropriate integer c E {0,... , n – 1}. -

(a) (i) Without using the Euclidean algorithm, write down integers s, t such that 1 = 4s + 9t, and use your answer to find the inverse of 4 mod 9. Hence, replace the congruence 4x = 5 mod 9 with one of the form x = a mod 9. (ii) Without using the Euclidean algorithm, write down integers u, v such that 1 = 3u + 22v, and use your answer to find the inverse of 3 mod 22. Hence, replace the congruence 3x = 19 mod 22 with one of the form x = b mod 22. (b) Use your answers to part (a) to solve the simultaneous congruences 4x = 5 mod 9 3x = 19 mod 22 Give your answer as a single congruence x = c mod n for an appropri- ate positive integer n and an appropriate integer c E {0,... , n – 1}. -

Advanced Engineering Mathematics

10th Edition

ISBN:9780470458365

Author:Erwin Kreyszig

Publisher:Erwin Kreyszig

Chapter2: Second-order Linear Odes

Section: Chapter Questions

Problem 1RQ

See similar textbooks

Similar questions

1 Using prime factorization, find gcd(900, 140) and lcm(900, 140). 2. Use the Euclidean algorithm to determine gcd(900, 140) 3. Solve the linear congruence 31x ≡ 57 ( mod 61). 4. Express gcd(55, 17) as a linear combination of 55 and 17.
Use the inversion algorithm to find the inverse of A = 1 2 3 0 1 2 011
(8) (a) Write 13 as a sum of distinct powers of 2. (b) Use the fast factoring algorithm to compute 2¹3 (mod 29).
Start Fill in the missing numbers of the sequence generated by Euclid's algorithm on inputs 70 and 15. gcd(70, 15) yields sequence: 70 15 Ex: 5 Ex: 5 0 Check cative inverse mod n 1 Next 2
(a) Find an imverse for 73 modulo 660. First use the extended Euclidean algorithm to find the greatest common divisor of 660 and 73 and express it as a linear combination of 660 and 73. Step 1: Find q, and r, so that 660 - 73 - 9, +r where Osr, <73. Then r, - 660 - 73 - 4, - Step 2: Find q, and r, so that 73 -92 + where 0sr, Then r- 73 - Step 3: Find q, and r, so that -2 43+ ra where 0sr Then r,- Step 4: Select the correct statement from the options below. O Because r - 0, god (660, 73) - 73 - -1. O Becauser- a, god (660, 73) -,- - 1. O Because r, - 1, god (660, 73) - 73 -r, 9-0. O Because r- 1, god (660, 73) --73 - 92-0. O Becauser- 1, god (660, 73) -1- -0. Next, substitute numerical values backward throuch the preceding steps, simplifying the results for each step, to find god (660, 73) - 1- 660s + 73t, where s- and t- =1 (mod 660), and so is an inverse for 73 modulo 660. It follows that 73 (b) Find the least positive solution for the congruence: 73x = 125 (mod 660). Step 1: By part…
Find the smallest positive integer x that solves the congruence: 4x = 5 (mod 27) x = (Hint: From running the Euclidean algorithm forwards and backwards we get 1= s(4) + t(27). Find s and use it to solve the congruence.)
(a) Use the Euclidean algorithm to find gcd(131,326). (b) Use the above to find a solution to 131x+326y=gcd(131,326) (c) Does 131 have an inverse modulo 326? If so, find a value in {0,1,2,3,…,325} that is an inverse. If not, explain why not?
(2) Let a = 218 and b =-115. Use the Euclidean Algorithm to find the gcd(a,b) and integers m and n such that gcd(a,b)=ma+nb .
Illustrate the Euclidean algorithm by using it to compute gcd(40, 134) and find a solution to Bezout’s identity 40x + 134y = gcd(40, 134). Show your work.