a. Bzout's identity states that for positive integers a and b, there always exist integers m...

 

Transcribed Image Text:

a. Bézout's identity states that for positive integers a and b, there always exist integers m and n such that am + bn = gcd(a, b). Also, recall that a = b (mod n) means that there exists an integer such that a-b=ln. As you know, this is called modular equivalence or modular congruence. -1 Recall that (if it exists) the multiplicative inverse of p modulo q, is defined to be the unique number p-¹ such that p ¹p 1 (mod q). E i. Apply the definition of modular equivalence and write down what p ¹p 1 (mod g) means. 1 mark. ii. Rearrange what you get and apply Bézout's identity to conclude that if gcd (p, q) = 1 then p¹ exists (modulo q). 2 marks. b. The Division algorithm tells us that, given positive numbers a and b, with a b, there always exist integers q and r, with 0≤r<b such that a = bq + r. (Think of primary school division before you learned about decimals.) Here, q is called the quotient and r is called the remainder. It can be shown that ged(a, b) = ged(b, r). The Euclidean algorithm makes use of this fact to calculate gcd(a, b) by repeatedly replacing the larger number by a remainder (which is always smaller). The algorithm is: i. Set ao = a, bob, j = 0. ii. Use the division algorithm to find q, and r, with 0 <r; <b; such that aj = bjqj + rj iii. If r;> 0 then set aj+1 = bj, bj+1 = r;, increment j ←j +1 and go back to the previous step. iv. Output r;-1 as gcd(a, b). We can keep track of all values in a table. For example, we can calculate ged(27, 16) by: jaj bj qj Tj 0 27 16 1 11 (27=16(1) +11) 1 16 11 1 5 2 11 5 2 1 35 1 5 0 (16=11(1) + 5) (11= 5(2) + 1) (5= 1(5) + 0) and we find ged(27, 16) - ged(5, 1) - 1 on the last row, which is also always going to be equal to the second last value of r; (here r2- 1) before the termination condition is reached. The final value of j is 3. The final column is included for illustration and is not necessary. Use the Euclidean algorithm to calculate ged(31, 19). Organise your work in a table as in the example above. 2 marks. a. Bézout's identity states that for positive integers a and b, there always exist integers m and n such that am + bn = gcd(a, b). Also, recall that a = b (mod n) means that there exists an integer such that a-b=ln. As you know, this is called modular equivalence or modular congruence. -1 Recall that (if it exists) the multiplicative inverse of p modulo q, is defined to be the unique number p-¹ such that p ¹p 1 (mod q). E i. Apply the definition of modular equivalence and write down what p ¹p 1 (mod g) means. 1 mark. ii. Rearrange what you get and apply Bézout's identity to conclude that if gcd (p, q) = 1 then p¹ exists (modulo q). 2 marks. b. The Division algorithm tells us that, given positive numbers a and b, with a b, there always exist integers q and r, with 0≤r<b such that a = bq + r. (Think of primary school division before you learned about decimals.) Here, q is called the quotient and r is called the remainder. It can be shown that ged(a, b) = ged(b, r). The Euclidean algorithm makes use of this fact to calculate gcd(a, b) by repeatedly replacing the larger number by a remainder (which is always smaller). The algorithm is: i. Set ao = a, bob, j = 0. ii. Use the division algorithm to find q, and r, with 0 <r; <b; such that aj = bjqj + rj iii. If r;> 0 then set aj+1 = bj, bj+1 = r;, increment j ←j +1 and go back to the previous step. iv. Output r;-1 as gcd(a, b). We can keep track of all values in a table. For example, we can calculate ged(27, 16) by: jaj bj qj Tj 0 27 16 1 11 (27=16(1) +11) 1 16 11 1 5 2 11 5 2 1 35 1 5 0 (16=11(1) + 5) (11= 5(2) + 1) (5= 1(5) + 0) and we find ged(27, 16) - ged(5, 1) - 1 on the last row, which is also always going to be equal to the second last value of r; (here r2- 1) before the termination condition is reached. The final value of j is 3. The final column is included for illustration and is not necessary. Use the Euclidean algorithm to calculate ged(31, 19). Organise your work in a table as in the example above. 2 marks.

Answer rating: 100% (QA)

i p p 1 mod q means that there exists an integer k such that p p 1 kq ii Rearranging the equation gi... View the full answer