1. Find all solutions of each of the following linear congr a) 2x = 5 (mod 7) c) 19x = 30 (mod 40) e) 103x = 444 (mod 999) b) 3x = 6 (mod 9) d) 9x = 5 (mod 25) f) 980x = 1500 (mod 1600)
1. Find all solutions of each of the following linear congr a) 2x = 5 (mod 7) c) 19x = 30 (mod 40) e) 103x = 444 (mod 999) b) 3x = 6 (mod 9) d) 9x = 5 (mod 25) f) 980x = 1500 (mod 1600)
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
4.2 question 1 letters d,e and f
![160
Congruences
Hence, 1=5-2.2=5- (7-5- 1) 2=6-3-2-7=(12 – 7 - 1) · 3 - 2-7= 12 .
3-5-7. Therefore, a particular solution to the linear diophantine equation is xo =-20
and yo-12. Hence, all solutions of the linear congruences are given by x =-20 =
4 (mod 12).
%3D
Later e wili want to know which integers are their own inverses modulo
pis prime. The following theorem tells us which integers have this property.
P,
where
Theorem 4.12. Let p be prime. The positive integer a is its own inverse modulo p if
and only if a = i (mod p) or a =- (mod p).
Proof. lf a =1 (mod p) or a = -1 (mod p), then a =1 (mod p), so that a is its own
inverse modulo p.
Conversely, if a is its own inverse modulo p, then a² = a · a = 1(mod p). Hence,
P| (a² – 1). Because a - 1= (a – 1)(a + 1), this implies that p| (a – 1) or p | (a + 1).
Therefore, a = 1 (mod p) or a =-1 (mod p).
%3D
4.2 EXERCISES
1. Find all solutions of each of the following linear congruences.
c) 19x = 30 (mod 40)
a) 2x = 5 (mod 7)
e) 103x = 444 (mod 999)
b) 3x = 6 (mod 9)
d) 9x = 5 (mod 25)
f) 980x = 1500 (mod 1600)
2. Find all solutions of each of the following linear congruences.
a) 3x = 2 (mod 7)
c) 17x = 14 (mod 21)
e) 128x = 833 (mod 1001)
b) 6x = 3 (mod 9)
d) 15x =9 (mod 25) f) 987.x 610 (mod 1597)
3. Find all solutions to the congruence 6,789,783x = 2,474,010 (mod 28,927,591).
4. Suppose that p is prime and that a and b are positive integers with (p, a) = 1. The following
method can be used to solve the linear congruence ax = b (mod p).
a) Show that if the integer x is a solution of axr b (mod p), then x is also a solution of the
linear congruence
ax = -b(m/a] (mod p),
where a, is the least positive residue of p modulo a. Note that this congruence is of
the same type as the original congruence, with a positive integer smaller than a as the
coefficient of x.
b) When the procedure of part (a) is iterated, one obtains a sequence of linear congruences
with coefficients of x equal to ao =a>a,>az > .Show that there is a positive integer
n with an
I, so that at the nth stage, one obtains a linear congruence x = B (mod pl-
%3D
c) Use the method described in part (b) to solve the linear congruence 6.x =7(mod 25.
5. An astronomer knows that a satellite orbits the Earth in a period that is an exact multipie
I hour that is less than I day. If the astronomer notes that the satellite completes 11 orbits in
an interval that starts when a 24-hour clock reads 0 hours and ends when the clock reads 17
bours, how long is the orbital period of the satellite?](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fcfba8c1b-379a-495a-9284-26414a9f3892%2F04eaec9b-ffe8-4e58-b2e0-5589f5432269%2F4erjz1q_processed.jpeg&w=3840&q=75)
Transcribed Image Text:160
Congruences
Hence, 1=5-2.2=5- (7-5- 1) 2=6-3-2-7=(12 – 7 - 1) · 3 - 2-7= 12 .
3-5-7. Therefore, a particular solution to the linear diophantine equation is xo =-20
and yo-12. Hence, all solutions of the linear congruences are given by x =-20 =
4 (mod 12).
%3D
Later e wili want to know which integers are their own inverses modulo
pis prime. The following theorem tells us which integers have this property.
P,
where
Theorem 4.12. Let p be prime. The positive integer a is its own inverse modulo p if
and only if a = i (mod p) or a =- (mod p).
Proof. lf a =1 (mod p) or a = -1 (mod p), then a =1 (mod p), so that a is its own
inverse modulo p.
Conversely, if a is its own inverse modulo p, then a² = a · a = 1(mod p). Hence,
P| (a² – 1). Because a - 1= (a – 1)(a + 1), this implies that p| (a – 1) or p | (a + 1).
Therefore, a = 1 (mod p) or a =-1 (mod p).
%3D
4.2 EXERCISES
1. Find all solutions of each of the following linear congruences.
c) 19x = 30 (mod 40)
a) 2x = 5 (mod 7)
e) 103x = 444 (mod 999)
b) 3x = 6 (mod 9)
d) 9x = 5 (mod 25)
f) 980x = 1500 (mod 1600)
2. Find all solutions of each of the following linear congruences.
a) 3x = 2 (mod 7)
c) 17x = 14 (mod 21)
e) 128x = 833 (mod 1001)
b) 6x = 3 (mod 9)
d) 15x =9 (mod 25) f) 987.x 610 (mod 1597)
3. Find all solutions to the congruence 6,789,783x = 2,474,010 (mod 28,927,591).
4. Suppose that p is prime and that a and b are positive integers with (p, a) = 1. The following
method can be used to solve the linear congruence ax = b (mod p).
a) Show that if the integer x is a solution of axr b (mod p), then x is also a solution of the
linear congruence
ax = -b(m/a] (mod p),
where a, is the least positive residue of p modulo a. Note that this congruence is of
the same type as the original congruence, with a positive integer smaller than a as the
coefficient of x.
b) When the procedure of part (a) is iterated, one obtains a sequence of linear congruences
with coefficients of x equal to ao =a>a,>az > .Show that there is a positive integer
n with an
I, so that at the nth stage, one obtains a linear congruence x = B (mod pl-
%3D
c) Use the method described in part (b) to solve the linear congruence 6.x =7(mod 25.
5. An astronomer knows that a satellite orbits the Earth in a period that is an exact multipie
I hour that is less than I day. If the astronomer notes that the satellite completes 11 orbits in
an interval that starts when a 24-hour clock reads 0 hours and ends when the clock reads 17
bours, how long is the orbital period of the satellite?
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 4 steps
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,
