Question

Use the Euclidean algorithm to express the greatest common divisor of each of these pairs of integers as a linear combination of these integers.
c) 35, 78

Answer 1

I could give you an example
and you could ask me if you don't understand something and I will explain it the best I can.

Answer 2

Example:
Let's first find the gcd of 18 and 132.

so 132 is bigger so we will start with it.
132=18( 7)+6 Note 132/18=7+6/18
18=6(3)+0 <stop when remainder is 0

so the gcd is the previous remainder
so the gcd of 18 and 132 is 6.


also let's write 6 as a linear combination of 18 and 132.

so we had above that 132=18(7)+6
solve for 6
132-18(7)=6
done!


now some examples could be longer
i could do another one

but let's see if you can at least find the gcd using eculid

Answer 3

@academicpanda which of your numbers is bigger?

Answer 4

I have this:
1=3-2
1=3-(8-2*3)
1=3-8+2*3
1=-8+2*3+3
1=3*3-8,as 2*3 is the same as 3+3 and 3+3+3 is the same as 3*3
1=3*(35-4*8)-8
1=3*35-12*8-8
1=3*35-13*8
1=3*35-13*(78-2*35)
1=3*35-13*78+26*35
1=29*35-13*78

Answer 5

well yeah that is right 29*35-13*78 is totally 1
so good job

Answer 6

I guess you had no problem with the gcd part?

Answer 7

I assume that since you were able to go backwards through that process to write 1 as a linear combination of 35 and 78.

Answer 8

yeah i wasn't sure i was using Euclidean's right lol

Answer 9

Well now you know.
Sometimes I seen a lot of people get lost in finding the linear combination thing when you have a lot of steps in finding the gcd

Answer 10

it is just basically going backwards through the gcd part rewriting the remainder as the "subject"

Answer 11

With a lot of substituting other numbers for other numbers

Answer 12

i mean they are technically the same number just written different lol

Answer 13

cool thanks!