show that if a,b,c,is positive integer and gcd(a,b)=1 , then the number n of non

Question

show that if a,b,c,is positive integer and gcd(a,b)=1 , then the number n of nonnegative solutions of ax+by=c satisfies the inequaliy c/ab-1 <n <= c/ab +1

I dont know how to solve the problem #5 how do i start it and how could i prove it ?? please help me

m m arranged so that xo xi xk. Describe k as a function of m and n. What is the shortest distance between successive x's? How are the other distances related to this shortest one? 3. Find all solutions of 19x 20y 1909 with x 0, y 0. 4. Suppose (a, b) 1, a 0, b 0, and let xo, yo be any integral solution of the equation ax by c. Find a necessary and sufficient condition, possibly depending on a, b, c, xo, yo, that the equation have a solution with x 0, y 0. 5. Show that if a, b, c e Z and (a, b) 1, then the number n of nonnegative solution of ax by c satisfies the inequality 1 n 1. ab 6. a) Let N (a 1)(b 1), where a, b e z+ and (a, b) 1. Show that ever ax by with x, y 20, whil integer c 2 N is representable in the form c N- 1 is not so representable.

Explanation / Answer

Since gcd (a,b) = 1,

Given

ax+by = c

Let ax = A and by = B

We need to find the no of solutions to the equation

A + B = c

Since a, b, x and y are all non-negative, we have the solutions in the following form

0 + c = c

1+(c-1) = c

2+(c-2) = c

and so on upto

c-1 + 1 = c

c + 0 = c

Thus there are c+1 solutions.

However, we considered the solutions of A+B = c such that both A and B are integers.

A = aX and B = bY

Not all As and Bs are perfectly divisible by a and b. The solutions are valid only when both A is divisible by a and B is divisible by b. Further since both A and B took consecutive values (0,1,2....c) and (c,c-1....0), the number of solutions

= Number of integers in the range 0,1,2.......c and c,c-1.....0 which is divisible by a and b respectively.

The number of integers in the range divisible by a = [(c+1)/a] where [x] is the greatest integer function.

Similarly the number of integers in the range divisible by b = [(c+1)/b]

Thus the number of integers in the range divisible by both a and b = [(c+1)/ab]

Thus n = [(c+1)/ab]

Now (c+1)/ab -1 < [(c+1)/ab] <= (c+1)/ab (By the definition of greatest integer function)

(c+1)/ab - 1 <= [(c+1)/ab] <= c/ab + 1/ab

=> c/ab -1 + 1/ab <= n <= c/ab + 1 (Lowest value for ab is 1*1 =1)

=> c/ab -1 < n <= c/ab + 1

Related Questions

Navigate

• Browse (All)
• Browse S
• Subjects

---

---

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