Let a and b be integers and n a positive integer. Assume also that a and n have a common divisor d > 1, but that the only positive integer dividing all three of a, b, and n is 1. Show that the congruence ax ≡ b mod n has no solutions.
Let a and b be integers and n a positive integer. Assume also that a and n have a common divisor d > 1, but that the only positive integer dividing all three of a, b, and n is 1. Show that the congruence ax ≡ b mod n has no solutions.
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
Topic Video
Question
Let a and b be integers and n a positive integer. Assume also that a and n have a common divisor d > 1, but that the only positive integer dividing all three of a, b, and n is 1. Show that the congruence ax ≡ b mod n has no solutions.
Expert Solution

Step 1
Use the following concepts, to prove the required result.
- If a divides b then b is a multiple of a.
That is, implies that , for any integer n.
- If d is the common divisor of a and b, then d divides both a and b.
Step by step
Solved in 3 steps

Knowledge Booster
Learn more about
Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, advanced-math and related others by exploring similar questions and additional content below.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,

