Question

Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!Plz...!.......
Someone HELP me!!!! for finding the solution for this question which is listed below:

Q-) Find the HCF of 81 and 237 and express it as a linear combination of 81 and 237.

Answer 1

HCF of 81 and 237

81 = 3 * 3 * 3 * 3

237 = 3 * 79

HCF = ?

Answer 2

i know the HCF of 81 and 237... which is listed below:(Using Euclid's Lemma)

\[237=81\times2+75\]
\[81=75\times1+6\]
\[75=6\times12+3\]
\[6=3\times2+0\]

am i right????

Answer 3

Yes! now 3 can be expressed as linear combination of 81 and 237 as 3 = 81x + 237y, where x and y are not unique.

Answer 4

hence, HCF is 3

Answer 5

Got it mayank?

Answer 6

HCF=3

Answer 7

got it!!! @mathslover and @KingAditya i mentioned it earlier!!!

Answer 8

We have to use the HCF to represent it in the linear combination of 81 and 237 :

So we can write the HCF as : 3 = 81 x + 237 y.

Lemme explain more.

Answer 9

@mathslover is this final answer????

Answer 10

Err, it's more like the whole algorithm.

Answer 11

i don't understand!!!! @Eyad plz explain it by one by one!!! plzz///

Answer 12

Which step you don't understand ?

Answer 13

after finding the HCF of 81 and 273 .......then then this whole process which is below than hcf of 81 and 273 i don't understand

Answer 14

\(\begin{array}{}
237 = 81 × 2 + 75 \\
81 = 75 × 1 + 6 \\
75 = 6 × 12 + 3\\
6 = 3 × 2 + 0
\end{array}\)

Now it is clear that HCF = 3

In the step 3 : \(\begin{array}{}
75 = 6 \times 12 + 3 --- (\text{step 5}) \\
\text{and from step 2: } \space \\
81 = 75 \times 1 + 6 \\
\text{thus we can write step 5 as : } \\

3 = 75 – (81 – 75 × 1) × 12\\
\implies 3 = 75 – (81× 12 – 75 × 12)\\
\implies 3 = 75 × 13 – 81× 12 ... \space (\text{step 6})\\
\text{From step 1:}\\

75 = 237 - 81 \times 2 \\

\text{thus from step 6 :} \\
3 = (237 – 81 × 2) × 13 – 81× 12\\
\implies 3 = (237 × 13 – 81 × 26) – 81× 12 \\
\implies 3 = 237 × 13 – 81 × 38 \\
\implies \text{H.C.F of 237 and 81 = } 237 \times 13 + 81 \times (-38) \\

\end{array}\)

∴HCF, 3 can be expressed as linear combination of 81 and 237 as 3 = 81x + 237y, where x and y are not unique.

Answer 15

I hope this clears your doubt mayank.

Answer 16

Thanks to meritnation too.

Answer 17

This whole process was proof to your query ,
81 = 3 x 27 = 3 x 9 x 3 = 3 x 3 x 3 x 3 = 34
Again, 237 = 79 x 3 = 3 x 79
Hence, H.C.F = 3 ,therefore
81*3/2-273*1/2 =243/2-273/2 =6/2 =3

Answer 18

I think @mayankdevnani is getting problem in understanding what is linear combination and what does the second part mean? Is it so Mayank?

Answer 19

yaaa.. this is true friend.....nature

Answer 20

just like : 3 = 2x + 3y, similarly in this question we will represent HCF (=3) in the form of :

81x + 237 y

Answer 21

plz wait!!!! i need time to understand!!!! plzzz wait

Answer 22

Take your time my friend.

Answer 23

3=(81-75*1)*12.....where this eq. comes?????

Answer 24

@mathslover plz expalin it one by one with your comment and then my comment!!!!! can you???

Answer 25

yes! Of course! Ready to help anyone anytime.

Linear combination , let us first understand this term .

Answer 26

yaaa.plzzz

Answer 27

ax + by = c

[ just like linear equation ]

Answer 28

okkkk

Answer 29

Can i join too.. @mathslover ?

Answer 30

See now we want to write HCF = 3 = c as in terms of ax + by. we have a = 81 and b = 237

so : 3 = 81 x + 237 y , right?

Answer 31

right

Answer 32

So now we want to find x and y, scroll up mayank and check the latex work I presented. It is clear that:

H.C.F. of 237 and 81 = 237 × 13 + 81 × (–38)
right?

Answer 33

So we have : 3 = 237 * 13 + 81 * (-38)

as the answer for the second part.

Answer 34

pzz wait!!!

Answer 35

I have to go now, sorry friend! May be @KingAditya can help you if you get any problem in understanding this. Hope you understand my problem :(

Thanks!

Answer 36

i don't understand yet!!!

Answer 37

I can make it clear to u..

Answer 38

plzzzz

Answer 39

U got what @mathslover told u?

Answer 40

237 × 13 + 81 × (–38)...where this comes...@mathslover

Answer 41

@mathslover

Answer 42

It is the 2nd part of the answer...to show the linear combination

Answer 43

@mathslover i understand!!!! plz go on!!!! but one thing arise:- where 13 comes in eq. scroll up (STEP-6)

Answer 44

@mathslover r u there????????? i need help!!! my friend

Answer 45

@mathslover plz tell

Answer 46

are you asking the step 6?

Answer 47

yaa...correct @chihiroasleaf

Answer 48

@Eyad where does 13 comes in step 6?????thats was my main problem

Answer 49

@mukushla and @gerryliyana plz help me!!!!

Answer 50

@ParthKohli and @hartnn plzz help me!!!!

Answer 51

@mathslover @hba @ParthKohli @Eyad @electrokid

Answer 52

@UnkleRhaukus @ParthKohli

Answer 53

I guess it's more of mathslover's thing. I haven't used the Extended Euclidean Algorithm a lot.

Answer 54

oh!!!! kkk

Answer 55

can you help me @mathslover and @mukushla ...little help!!!! not so big help

Answer 56

Sorry, cant help. Busy right now

Answer 57

in which work?????

Answer 58

@dmezzullo

Answer 59

@amistre64

Answer 60

this is an application of a theorem in number theory; the gcd of 2 numbers can be expressed as a linear combination of those numbers.

Answer 61

yaa!!!

Answer 62

spose gcd(a,b) = c

then ax+by = c with x,y having infintie solutions

Answer 63

okkk

Answer 64

@amistre64 will you explain me mathslover sol.???

Answer 65

you're still asking the step 6, right?

Answer 66

right!!!

Answer 67

@mayankdevnani

Answer 68

what????

Answer 69

I hope it helps you mayank.

Answer 70

i can't open it!!!!

Answer 71

You have to open it with : internet explorer.

Answer 72

it contains what????

Answer 73

it's just simple distribution and multiplication rule

\[3=75–(81×12–75×12)\]
\[3 = 75 - (81 x 12) + (75 x 12)\]
\[3=75 + 75 \times 12 –81\times12 \]
\[3 = 75 (1+12) - 81 \times 12\]
\[3 = 73 \times 13 - 81 \times 12 \]

do you get it? :)

Answer 74

Right click on it : Save link as , save it.

Then open it with internet explorer.

Answer 75

It contains your solution Mayank

Answer 76

nice hand writing man!!!!

Answer 77

plz wait for a min.

Answer 78

3=75–(81×12–75×12)

3 = 75 - (81 * 12) + (75 * 12)

3 = 75 + 75 * 12 - (81 *12)

3 = 75(12+1) - (81*12)

3 = 75 * 13 - 81 * 12

this is the explaination for step 6.

Answer 79

im not to good at trying to explain other peoples ideas :)

but if we do a euclidian run on this we get

237 = 81(2) + 75
81 = 75(1) + 6
75 = 6(12) + 3 <-- gcd=3
6 = 3(2) + 0

81x + 237y = 3

to find the smaller of 81 and 237, a specific value for x, we can run the reverse euclidean algorithm

0
0 1
0 - 2(1) = -2
1 -1(-2)= 3
-2-12(3) = -38 <-- x' = -38; this leaves is with y' = 13 as one soluton

Answer 80

thnx... @mathslover but in your work(file) that you upload , i can't understand your last 2 line!!!! i mean how did you get
3=237*13-81*38

Answer 81

@amistre64 and @chihiroasleaf thank you.....

Answer 82

@amistre64 and @chihiroasleaf can you help me????

Answer 83

I have : 3 = (237 * 13 - 81 *26 ) - 81 * 12

3 = 237 * 13 - 81 * 26 - 81 * 12

3 = 237 * 13 - 81*(26+12)

3 = 237 * 13 - 81 * (38)

Got it Mayank?

Answer 84

i got it @mathslover

Answer 85

i got it @mathslover

Answer 86

i believe there is a setup such that:\[x=x'+\frac bcn\]\[y=y'-\frac acn\]
but thats prolly incorrect since its from memory, but it looks something like that

Answer 87

thnx.... @amistre64 , @chihiroasleaf , @Eyad and special thanks to my friend.. @mathslover

Answer 88

Amistre, I liked your method also.

Welcome mayank.

Answer 89

can i ask you last question...its so simple!!!! mathslover

Answer 90

@mathslover

Answer 91

Hmn, Yes ask mayank...

Answer 92

i believe there is a setup such that:\[x=ax'+\frac bcn\]
but thats prolly incorrect since its from memory, but it looks something like that