ผลต่างระหว่างรุ่นของ "01204211/activity7 number theory 2"
Jittat (คุย | มีส่วนร่วม) |
Jittat (คุย | มีส่วนร่วม) |
||
| แถว 5: | แถว 5: | ||
'''A.1''' Implement the Extended-GCD algorithm and use it to find, for each following pair of <math>a</math> and <math>b</math>, the g.c.d. of <math>a</math> and <math>b</math> and a pair of integers <math>(x,y)</math> such that <math>ax + by = gcd(a,b)</math>. | '''A.1''' Implement the Extended-GCD algorithm and use it to find, for each following pair of <math>a</math> and <math>b</math>, the g.c.d. of <math>a</math> and <math>b</math> and a pair of integers <math>(x,y)</math> such that <math>ax + by = gcd(a,b)</math>. | ||
| − | (a) <math>a = 5, b = 7</math> | + | (a) <math>a = 5,</math> <math>b = 7</math> |
| − | (b) <math>a = 500, b = 7123</math> | + | (b) <math>a = 500,</math> <math>b = 7123</math> |
| − | (c) <math>a = 55515, b = 71234</math> | + | (c) <math>a = 55515,</math> <math>b = 71234</math> |
| − | (d) <math>a = 5551532, b = 7123456</math> | + | (d) <math>a = 5551532,</math> <math>b = 7123456</math> |
| − | (e) <math>a = </math>your student id, <math>b = </math> the student id of another student sitting next to you. | + | (e) <math>a = </math>your student id, <math>b = </math> the student id of another student sitting next to you. (Don't forget to write down the values of <math>a</math> and <math>b</math> as well. |
| + | |||
| + | '''A.2''' Use the Extended-GCD algorithm to find the modular multiplicative inverse for the divisor in each of the following question and find the result of the modular division. If the inverse does not exist, you can just state the fact and state that the division cannot be found. | ||
| + | |||
| + | (E.g., if the question is to find 4/3 (mod 11), you have to find <math>3^{-1}</math> and then find <math>0\leq c < 11</math> such that <math>c\cdot 3\equiv 4</math> (mod 11).) | ||
| + | |||
| + | (a) <math>5/6</math> (mod <math>7</math>) | ||
| + | |||
| + | (b) <math>5/6</math> (mod <math>1451</math>) | ||
| + | |||
| + | (c) <math>5/6</math> (mod <math>7829</math>) | ||
| + | |||
| + | (d) <math>6543/3456</math> (mod <math>98899</math>) | ||
| + | |||
| + | (e) <math>1234/4567</math> (mod <math>104537</math>) | ||
== Homework == | == Homework == | ||
รุ่นแก้ไขเมื่อ 16:41, 14 ตุลาคม 2558
- This is part of 01204211-58.
In-class activities
A.1 Implement the Extended-GCD algorithm and use it to find, for each following pair of and , the g.c.d. of and and a pair of integers such that .
(a)
(b)
(c)
(d)
(e) your student id, the student id of another student sitting next to you. (Don't forget to write down the values of and as well.
A.2 Use the Extended-GCD algorithm to find the modular multiplicative inverse for the divisor in each of the following question and find the result of the modular division. If the inverse does not exist, you can just state the fact and state that the division cannot be found.
(E.g., if the question is to find 4/3 (mod 11), you have to find and then find such that (mod 11).)
(a) (mod )
(b) (mod )
(c) (mod )
(d) (mod )
(e) (mod )
