Question

In: Advanced Math

Let a and b be positive integers, and let d be their greatest common divisor. Prove...

Let a and b be positive integers, and let d be their greatest common divisor. Prove that there are infinitely many integers x and y such that ax+by = d. Next, given one particular solution x0 and y0 of this equation, show how to find all the solutions.

Expert Solution

The equation ax+by=c has solutions if and only if gcd(a,b)|c.

If so, it has infinitely many solutions, and any one solution can be used to generate all the other ones.

the greatest common divisor of a and b divides both ax and by,

hence divides c , if there is a solution.

given any integers a and b you can find integers v and w such that av+bw =gcd(a,b); the numbers v and w are not unique, but you only need one pair.

Once you find v and w, since we are assuming that gcd(a,b) divides c, there exists an integer "m" such that gcd(a,b)m=c . Multiplying av+bw=gcd(a,b) through by m you get

a(vm)+b(wm)=gcd(a,b)m=c.

this gives one solution, with x=vm and y=wm.

suppose that ax₁+by₁=c is a solution, and ax+by=c is some other solution.

Taking the difference between the two equation ( ax₁+by₁=c & ax+by=c),

a(x₁−x)+b(y₁−y)=0. Therefore, a(x₁−x)=b(y−y₁)

means that a divides b(y−y₁), and therefore divides y−y₁.

Therefore, for some integer r. Substituting into the equation a(x₁−x)=b(y−y₁) gives

which give or .

So,

if ax₁+by₁=cax₁+by₁=c is any solution,

then all solutions are of the form and .

so this is the proof that there are infinitely many integers x and y such that ax+by = d.

Colby Messinger answered 2 years ago

8.Let a and b be integers and d a positive integer. (a) Prove that if d...

8.Let a and b be integers and d a positive integer. (a) Prove that if d divides a and d divides b, then d divides both a + b and a − b. (b) Is the converse of the above true? If so, prove it. If not, give a specific example of a, b, d showing that the converse is false. 9. Let a, b, c, m, n be integers. Prove that if a divides each of b and c,...

let d be a positive integer. Prove that Q[sqrt d] = {a + b sqrt d|...

let d be a positive integer. Prove that Q[sqrt d] = {a + b sqrt d| a, b is in Q} is a field. provide explanations.

Java program: Greatest Common Divisor Write a program which finds the greatest common divisor of two...

Java program: Greatest Common Divisor Write a program which finds the greatest common divisor of two natural numbers a and b Input: a and b are given in a line separated by a single space. Output: Output the greatest common divisor of a and b. Constraints: 1 ≤ a, b ≤ 109 Hint: You can use the following observation: For integers x and y, if x ≥ y, then gcd(x, y) = gcd(y, x%y) Sample Input 1 54 20 Sample Output...

I want a unique c++ code for the following. (Greatest Common Divisor) Given two integers x...

I want a unique c++ code for the following. (Greatest Common Divisor) Given two integers x and y, the following recursive definition determines the greatest common divisor of x and y, written gcd(x,y):     5 5 ± x y x y y x y y gcd( , ) if 0 gcd( , % ) if 0 Note: In this definition, % is the mod operator. Write a recursive function, gcd, that takes as parameters two integers and...

Let S{a, b, c, d} be a set of four positive integers. If pairs of distinct...

Let S{a, b, c, d} be a set of four positive integers. If pairs of distinct elements of S are added, the following six sums are obtained:5,10, 11,13,14,19. Determine the values of a, b, c, and d. (There are two possibilities. )

Show that if a, b are positive integers and d = hcf(a, b), then there are...

Show that if a, b are positive integers and d = hcf(a, b), then there are positive integers s, t such that d = sa − tb.

A. 271 and 516 1. Find the greatest common divisor, d, of the two numbers from part...

A. 271 and 516 1. Find the greatest common divisor, d, of the two numbers from part A using the Euclidean algorithm. Show and explain all work. 2. Find all solutions for the congruence ax ? d (mod b) where a and b are the integers from part A and d is the greatest common divisor from part A1. Show and explain all work.

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1....

Let m, n be natural numbers such that their greatest common divisor gcd(m, n) = 1. Prove that there is a natural number k such that n divides ((m^k) − 1).

a.) Prove the following: Lemma. Let a and b be integers. If both a and b...

a.) Prove the following: Lemma. Let a and b be integers. If both a and b have the form 4k+1 (where k is an integer), then ab also has the form 4k+1. b.)The lemma from part a generalizes two products of integers of the form 4k+1. State and prove the generalized lemma. c.) Prove that any natural number of the form 4k+3 has a prime factor of the form 4k+3.

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf)...

3. In mathematics, the greatest common divisor (gcd), sometimes known as the greatest common factor (gcf) or highest common factor (hcf), of two non-zero integers, is the largest positive integer that divides both numbers. The greatest common divisor of a and b is written as gcd (a, b), or sometimes simply as (a, b). For example, gcd (12, 18) = 6, gcd (−4, 14) = 2 and gcd (5, 0) = 5. Two numbers are called co-prime or relatively prime...