Question

find the GCD (175,245) and write it in the form 175s + t245 with integers s,t

Answer 1

35=3*175-2*245

Answer 2

s=3, t=-2 for one solution

Answer 3

what do you mean for one solution?

Answer 4

there are infinite possibilities for s and t, i'm just giving you one possiblity

Answer 5

oh ok

Answer 6

but what is GCD of (175,245)?

Answer 7

35

Answer 8

To find the GCD (Greatest Common Denominator),
first reduce the two numbers to their prime factors:

175 = 7 * 5 * 5
245 = 7 * 7 * 5

The two numbers have one 7 and one 5 in common,
so the GCD is 7 * 5 = 35

If the top number had been 1,225, and the bottom number
remained the same, the factors would be:

1,225 = 7 * 7 * 5 * 5
245 = 7 * 7 * 5

The two numbers now have two 7’s and one 5 in common,
so the GCD is 7 * 7 * 5 = 245

If the top number had stayed the same and the bottom
number had been 1,225, the factors would be

175 = 7 * 5 * 5
1,225 = 7 * 7 * 5 * 5

The two numbers now have one 7 and two 5’s in common,
so the GCD is 7 * 5 * 5 = 175

Answer 9

hey pizzapi, would you be able to show me the step of how you got s=3 and t= -2

Answer 10

oh, I did it by inspection but you could use the euclidean algorithm to do it

245=(1)(175)+70
175=2(70)+35
70=2(35)

Thus 35=175-2(70)
35=175-2(245-175)
35=3(175)-2(245)

Answer 11

yea i am having really tough time understanding euclidean algorithm

Answer 12

would you help me understand this algorithm