Find integers x and y such that 115x + 30y = gcd (431, 29)

There are none.

Step-by-step explanation:

gcd (431,29) = 1

The reasons I came to this conclusion is because 29 is prime.

29 is not a factor of 431 so we are done.

So now we want to find (x, y) such that 115x+30y=1.

I'm going to use Euclidean's Algorithm.

115=30 (3) + 25

30=25 (1) + 5

25=5 (5)

So we know we are done when we get the remainder is 0 and I like to look at the line before the remainder 0 line to see the greatest common divisor or 115 and 30 is 5.

So 115x+30y=5 has integer solutions (x, y) where d=5 is the smallest possible positive such that 115x+30y=d will have integer solutions (x, y).

So since 1 is smaller than 5 and we are trying to solve 115x+30y=1 for integer solutions (x, y), there there is none.

Furthermore, 115x+30y=1 can be written as 5 (23x+6y) = 1 and we know that 5 is not a factor of 1.