PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!! Let a, b. and c be integers,

Question

PLEASE SHOW DETAIL WILL RATE LIFESAVER if done so!!

Let a, b. and c be integers, let n be a natural number, and suppose ged(c, n) 1. If ac = bc (mod n), then a = b (mod n). In class, it was claimed that there are infinitely many different pairs of integers (x, y) with the property that 3x + 2y ged(3, 2) 1. For convenience, let's call such a pair of integers (x, y) a solution to the equation 3x + 2y = 1. I low did we find the first such solution? How did we find infinitely many other solutions? Describe the solutions we found. (Notice our 1-2 punch: find one, then construct more.) A key question we would like to know the answer to is this question: Dots our method of finding infinitely many solutions actually find ALL of the solutions (x, y) to the equation 3x + 2y = 1? Or are there others? What do you think? How can you know for sure?

Explanation / Answer

Given, gcd(c,n) = 1

So, c and n has no common multiples.

Given, ac = bc (mod n)

So, ac = nk + bc

c(a - b) = nk

so nk is a multiple of c.

but gcd(c,n) = 1 so, k is a multiple of c

Let k = cl

ac = ncl + bc

a = nl + b

a = b (mod n)

Hence proved

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.