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,...

The greatest common divisor of two integers x and y is the largest positive integer that...

The greatest common divisor of two integers x and y is the largest positive integer that evenly divides both. For example, gcd(12,6)=6, gcd(21,14)=7, gcd(31,10)=1, gcd(55,25)=5 Recall that the gcd of two integers is gcd(a,0) = a gcd(a,b) = gcd(b, a%b) Create int gcd(int x, int y). Assume that the two integers are zero or positive. Write the code as a pure function. Put it in a file gcd.c. Of course, you will need to test it. The function Φ(n) counts...

Write a C function gcd that returns the greatest common divisor of two integers. The greatest...

Write a C function gcd that returns the greatest common divisor of two integers. The greatest common divisor (GCD) of two integers is the largest integer that evenly divides each of the two numbers.

In C++ The greatest common divisor (GCD) of two integers in the largest integer that evenly...

In C++ The greatest common divisor (GCD) of two integers in the largest integer that evenly divides each of the numbers. Write a function called GCD that has a void return type, and accepts 3 parameters (first two by value, third by reference). The function should find the greatest common divisor of the first two numbers, and have the result as its OUTGOING value. Write a main function that asks the users for two integers, and uses your function to...

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...

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. )

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...

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.