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

answer: a. 13/44

step-by-step explanation: judging by the information given to us, we are looking for experimental probability. we can see that 13 males have chosen chocolate ice cream. there are 44 ice creams in total (remember that the total is always the denominator). so our answer is 13/44.

Answer from: Quest

sadsdda

step-by-step explanation:

Another question on Mathematics

Mathematics, 21.06.2019 14:30

Which sentence describes why polygon mnop is congruent to polygon jklp? a. polygon jklp maps to polygon mnop through a translation. b. polygon jklp maps to polygon mnop through a rotation. c. polygon jklp maps to polygon mnop through a dilation. d. polygon jklp maps to polygon mnop through a stretch.

Answers: 2

Answer

Mathematics, 21.06.2019 21:30

Awater truck is filling a swimming pool. the equation that represents this relationship is y=19.75x where y is the number of gallons of water in the pool and x is the number of minutes the truck has been filling the pool.

Answers: 1

Answer

Mathematics, 21.06.2019 22:00

The difference of two numbers is 40. find the numbers if 0.3 parts of one number is equal to 37.5% of the other one.

Answers: 1

Answer

Mathematics, 21.06.2019 23:40

Klmn and pqrs are similar trapezoids. which side of pqrs corresponds to lm

Answers: 1

Answer

You know the right answer?

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