Question

Would like assistance in understanding and solving this example on Elementary Number Theory with the steps of the solution to better understand, thanks.
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.

Answer 1

Answer:

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:

1. Let a=x, b=y
2. Given x,y, use the division algorithm to write x=yq + r (q = quotient and r = remainder)
3. if r=0, stop and output y; this is the gcd of a,b
4. if 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.