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.

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

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

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:

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

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

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 .

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

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.

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.

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

nada

step-by-step explanation: