Mathematics, 14.09.2019 09:10 artemiscrock1350

Would like assistance in understanding and solving this example on elementary number theory with the steps of the solution to better understand, .
a) let a = 123 and b = 76. find (a, b) using the euclidean algorithm. then find x and y such that ax+by = (a, b).
b) show that 361x+2109y = 1000 does not have integer solutions.

Answers: 1

Show answers

Answers

Answer from: mruffier6239

The gcd(123,76) is equal to 1. The linear combination is $1=-21 \cdot 123+34 \cdot 76$

The 361x+2109y = 1000 does not have integer solutions because the gcd(2109, 361) is equal to 19 and $19\not| \:1000$

Step-by-step explanation:

Point a:

The greatest common divisor (GCD) of two numbers is the largest numbers that divide them both. The Euclidean algorithm is an efficient method for computing the GCD without explicitly factoring the two integers.

These are the steps:

Let a=x, b=yGiven x,y, use the division algorithm to write x=yq + r (q = quotient and r = remainder)if r=0, stop and output y; this is the gcd of a,bif r ≠ 0, replace (x,t) by (y,r): Go to step 2

The division algorithm is an algorithm in which given 2 integers n and d, it computes their quotient q and remainder r, where $0\leq r$ . Let's say we have to divide n (dividend) by d (divisor):

Subtract d from n repeatedly.The resulting number is known as the remainder r, and the number of times that d is subtracted is called the quotient q.

To compute gcd(123,76), divide the larger number by the smaller number, using the division algorithm we have:

$\frac{123}{76} = 123-76 =47$

At this point, we cannot subtract 76 again. Hence 1 is the quotient ( we subtract 76 from 123 one time) and 47 is the remainder. We can express this as a linear combination $123=76 \cdot 1+47$ .

Using the same reasoning and the steps of the Euclidean algorithm we have:

$gcd(123,76)=\\123=76 \cdot 1 +47\\76=47 \cdot 1 +29\\47=29 \cdot 1 +18\\29=18 \cdot 1 +11\\18=11 \cdot 1 +7\\11=7\cdot 1 +4\\7= 4\cdot 1+3\\4 = 3 \cdot 1 +1\\3 = 1 \cdot 3 +0$

The gcd(123,76) is equal to 1.

To represent 1 as a linear combination of the integers 123 and 76, we start with the next-to-last of the above equations and successively eliminate the remainders 3, 4, 7, 11, 18, 29, and 47.

$1=4-3 \cdot 1\\1=4-(7-4 \cdot 1) \cdot 1\\1=2\cdot 4 - 7\cdot 1\\1=2\cdot(11 -7 \cdot 1) -7 \cdot 1\\1=2\cdot 11 -7 \cdot 3\\1=2\cdot 11 -(18-11\cdot 1) \cdot 3\\1=5\cdot 11-3\cdot 18\\1=5\cdot (29-18\cdot 1)-3\cdot 18\\1=5\cdot 29 -8\cdot 18\\1=5\cdot 29 -8\cdot (47-29\cdot 1)\\1=13\cdot 29 -8\cdot 47\\1=13 \cdot (76-47 \cdot 1)-8\cdot 47\\1=13 \cdot 76 -21 \cdot 47\\1=13 \cdot 76 -21 \cdot (123-76\cdot 1)\\1=-21 \cdot 123+34 \cdot 76$

Point b:

We can use this theorem:

When ax + by = c is solvable. Given integers a, b, and c with a and b not both 0, there exist integers x and y such that ax + by = c if and only if (a,b) | c

In this particular expression 361x+2109y = 1000 we need to find the gcd(2109, 361) and check if gcd(2109, 361) | 1000 is true.

$2109=361\cdot 5 +304\\361 = 304 \cdot 1 +57\\304= 57\cdot 5 +19\\57=19\cdot 3 +0$

The gcd(2109, 361) is equal to 19. We can see that 19 does not divide 1000 ( $19\not| \:1000$ ), that is the reason 361x+2109y = 1000 does not have integer solutions.

Answer from: Quest

Cisco co cop hop h0 cop go srry cop hop h0 d8

Answer from: Quest

yes because as the functions are graphed they eventually will intersect unless otherwise

step-by-step explanation:

Another question on Mathematics

Mathematics, 21.06.2019 21:40

Which statement is true about a number and its additive inverse? a. their product is always one. b. their sum is always one. c. they are always reciprocals of each other. d. their sum is always zero.

Answers: 1

Answer

Mathematics, 22.06.2019 00:10

Given: p: 2x = 16 q: 3x – 4= 20 which is the converse of p - q? if 2x + 16, then 3x - 4 20. if 3x –4 +20, then 2x # 16. lf 2x = 16, then 3x - 4 = 20. lf 3x – 4= 20, then 2x = 16. o o

Answers: 1

Answer

Mathematics, 22.06.2019 00:30

92ft long and 48 wide resurface 2.75$

Answers: 1

Answer

Mathematics, 22.06.2019 01:00

Find the measure for the angle indicated in bold

Answers: 1

Answer

You know the right answer?

Would like assistance in understanding and solving this example on elementary number theory with the...