(a) Find an inverse for 73 modulo 66o. 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 a, and r, so that 660 = 73 •91 +r. where osr, < 73. Then , - 660 - 73.9, -3 Step 2 1 Find g, and r, so that 73 = ,'2 +r2 where osr2 <, Then , = 73 - (3 Step 3: Find o3 and r3 so that =293 +r3. where 0srz
(a) Find an inverse for 73 modulo 66o. 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 a, and r, so that 660 = 73 •91 +r. where osr, < 73. Then , - 660 - 73.9, -3 Step 2 1 Find g, and r, so that 73 = ,'2 +r2 where osr2 <, Then , = 73 - (3 Step 3: Find o3 and r3 so that =293 +r3. where 0srz
Advanced Engineering Mathematics
10th Edition
ISBN:9780470458365
Author:Erwin Kreyszig
Publisher:Erwin Kreyszig
Chapter2: Second-order Linear Odes
Section: Chapter Questions
Problem 1RQ
Related questions
Question
![(a) Find an inverse 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 9₁ and ₁ so that
660 = 73 9₁ +₁, where 0 s₁ < 73.
Then ₁ = 660 - 73
.
9₁ = 3
91
Step 2: Find 92 and
2 so that
73 = 192 +2, where
03₂ <₁
Then ₂ = 73 (3
2
-
]✔
).92²
Step 3: Find 93 and 3 so that
/1 = 12 *93 +13, where 0 ≤ 3</21
<72"
'3'
Then 3 = 3
1
).93²
Step 4: Select the correct statement from the options below.
Because 3 = 1, gcd (660, 73) = 1/2*93 = 0.
Because 3 = 0, gcd (660, 73) = 731 92 = 1.
Because 3 = 1, gcd (660, 73) = 73 - 192 = 0.
Because 3 = 1, gcd (660, 73) = x2 - 73 92 = 0.
O Because 3 = 0, gcd (660, 73) = 1/2 93=1.
and t=217
Next, substitute numerical values backward through the preceding steps, simplifying the results for each step, to find gcd (660, 73) = 1 = 660s + 73t, where s = -24
It follows that 73. 217
= 1 (mod 660), and so 217
is an inverse for 73 modulo 660.
(b) Find the least positive solution for the congruence: 73x = 125 (mod 660).
Step 1: By part (a), 73
217
217
125 1125 (mod 660) = 125 (mod 660).
Let x 125 217
(217
). Then
73x = 125 (mod 660).
Note that x is a solution to the given congruence, but it may not be the least positive solution.
Step 2: Let v be the remainder obtained when x is divided by 660. Then v =
X and, by Theorem 8.4.1 and Theorem 8.4.3, 73x = 73v (mod 660). Hence, is also a solution to the congruence. In other words,
73v125 (mod 660).
x (mod 660).
Suppose u is any positive solution to the congruence that is less than or equal to v. Then 73 = 73.
X
Since 73 is prime, gdc(73, 660) = 1. Thus, the cancellation theorem for modular equivalence
, can be applied to conclude that u =
X. Therefore,
J
= 1
• ₂ = 0
= 1 (mod 660). Multiply both sides by 125 to obtain 73.
X is the least positive solution to the congruence.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fc4419780-2961-4b4a-afec-a4a329abb0c5%2F670fa2ad-681c-4e16-aa42-c458e7c93dee%2Fl9mwyrp_processed.png&w=3840&q=75)
Transcribed Image Text:(a) Find an inverse 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 9₁ and ₁ so that
660 = 73 9₁ +₁, where 0 s₁ < 73.
Then ₁ = 660 - 73
.
9₁ = 3
91
Step 2: Find 92 and
2 so that
73 = 192 +2, where
03₂ <₁
Then ₂ = 73 (3
2
-
]✔
).92²
Step 3: Find 93 and 3 so that
/1 = 12 *93 +13, where 0 ≤ 3</21
<72"
'3'
Then 3 = 3
1
).93²
Step 4: Select the correct statement from the options below.
Because 3 = 1, gcd (660, 73) = 1/2*93 = 0.
Because 3 = 0, gcd (660, 73) = 731 92 = 1.
Because 3 = 1, gcd (660, 73) = 73 - 192 = 0.
Because 3 = 1, gcd (660, 73) = x2 - 73 92 = 0.
O Because 3 = 0, gcd (660, 73) = 1/2 93=1.
and t=217
Next, substitute numerical values backward through the preceding steps, simplifying the results for each step, to find gcd (660, 73) = 1 = 660s + 73t, where s = -24
It follows that 73. 217
= 1 (mod 660), and so 217
is an inverse for 73 modulo 660.
(b) Find the least positive solution for the congruence: 73x = 125 (mod 660).
Step 1: By part (a), 73
217
217
125 1125 (mod 660) = 125 (mod 660).
Let x 125 217
(217
). Then
73x = 125 (mod 660).
Note that x is a solution to the given congruence, but it may not be the least positive solution.
Step 2: Let v be the remainder obtained when x is divided by 660. Then v =
X and, by Theorem 8.4.1 and Theorem 8.4.3, 73x = 73v (mod 660). Hence, is also a solution to the congruence. In other words,
73v125 (mod 660).
x (mod 660).
Suppose u is any positive solution to the congruence that is less than or equal to v. Then 73 = 73.
X
Since 73 is prime, gdc(73, 660) = 1. Thus, the cancellation theorem for modular equivalence
, can be applied to conclude that u =
X. Therefore,
J
= 1
• ₂ = 0
= 1 (mod 660). Multiply both sides by 125 to obtain 73.
X is the least positive solution to the congruence.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps with 1 images
Recommended textbooks for you
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Advanced Engineering Mathematics
Advanced Math
ISBN:
9780470458365
Author:
Erwin Kreyszig
Publisher:
Wiley, John & Sons, Incorporated
Numerical Methods for Engineers
Advanced Math
ISBN:
9780073397924
Author:
Steven C. Chapra Dr., Raymond P. Canale
Publisher:
McGraw-Hill Education
Introductory Mathematics for Engineering Applicat…
Advanced Math
ISBN:
9781118141809
Author:
Nathan Klingbeil
Publisher:
WILEY
Mathematics For Machine Technology
Advanced Math
ISBN:
9781337798310
Author:
Peterson, John.
Publisher:
Cengage Learning,
