Question

In: Advanced Math

3. (4 marks) Let a and b be positive integers. Is gcd(5a + b, 11a +...

3. Let a and b be positive integers. Is gcd(5a + b, 11a + 2b) = gcd(2a + b, 3a + 2b)?

If yes provide a proof. If not, provide a counterexample.

Solutions

Expert Solution

Solution:

Let be an integer matrix and let

Then, we have

(Cramer's Rule)

where is the adjoint matrix (the transpose of the cofactor matrix), and so
(From and the

Associativity of Matrix multiplication)

Let and . Then by the first matrix equation

( , then )

and by the second matrix equation .
In particular, if .

Here, we have

(Since )

Similarly, we have

(Since )

Hence

Colby Messinger answered 1 year ago

Next > < Previous

Related Solutions

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.

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 L1 be the language of the binary representations of all positive integers divisible by 4....

Let L1 be the language of the binary representations of all positive integers divisible by 4. Let L2 be the language of the binary representations of all positive integers not divisible by 4. None of the elements of these languages have leading zeroes. a) Write a regular expression denoting L1. b) Write a regular expression denoting L2. c) a) Draw a state diagram (= deterministic finite state automaton) with as few states as possible which recognizes L1. This state diagram...

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

(A) Let a,b,c∈Z. Prove that if gcd(a,b)=1 and a∣bc, then a∣c. (B) Let p ≥ 2....

(A) Let a,b,c∈Z. Prove that if gcd(a,b)=1 and a∣bc, then a∣c. (B) Let p ≥ 2. Prove that if 2p−1 is prime, then p must also be prime. (Abstract Algebra)

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose...

Let a1 ≥ a2, . . . , an be a sequence of positive integers whose sum is 2n − 2. Prove that there exists a tree T on n vertices whose vertices have degrees a1, a2, . . . , an. Sketch of solution: Prove that there exist i and j such that ai = 1 and aj ≥ 2. Remove ai, subtract 1 from aj and induct on n.

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.

Thank You Define the gcd of three integers a, b, c as the largest common divisor...

Thank You Define the gcd of three integers a, b, c as the largest common divisor of a, b, c, and denote it by (a, b, c). Show that (a, b, c) = ((a, b), c) and that (a, b, c) can be expressed as a linear combination of a, b, c.

Let t= 20389208 mod 4 and M= t+25 a. Find integers a and b such that...

Let t= 20389208 mod 4 and M= t+25 a. Find integers a and b such that 0<a<M, 0<b<M and ab= 0 (mod M) b. Find integers a and b such that 0<a<M, 0<b<M and ab= 1 (mod M) Thank you in advance!

Ex 3. Consider the following definitions: Definition: Let a and b be integers. A linear combination...

Ex 3. Consider the following definitions: Definition: Let a and b be integers. A linear combination of a and b is an expression of the form ax + by, where x and y are also integers. Note that a linear combination of a and b is also an integer. Definition: Given two integers a and b we say that a divides b, and we write a|b, if there exists an integer k such that b = ka. Moreover, we write...

Subjects