Hello and welcome to Maths with Jay. Now, we’ve already seen by using Euclid’s

algorithm that we can find the highest common factor of 39 and 15. So remember that we found that it was

the last remainder in this process here; so here the highest common factor was

three. What we’re going to do next is show that we can write this number, the highest common factor, in terms of

the original two numbers, by going through the following process: so what

we’re going to do is write three equal to something times 39 minus something times

fifteen, or something times 15 minus something times 39. We start off by using what

we’ve already done, so we’re using the first three equations here from Euclid’s

algorithm and in each case we’re going to make the

remainder the subject. So to start with, we know that 9 must be 39 minus 2 times 15, and then, looking at the second line, 6 is

equal to 15 minus 1 times nine, and three is 9 minus 1 times six. And then we’re going to use what’s called

backwards substitution, working from the last line. So we’re starting off with three

being equal to 9 minus 1 times six. So we start off writing that: three is equal

to 9 minus 1 times…and then instead of the six we use the previous line, so we’re

replacing the six by 15 minus 1 times nine and then we’re simplifying that so that

we’re writing the three in terms of the nine and the 15, and then we’re using the

first line to replace the nine in terms of the 39 & the 15 and then we are simplifying that and you can

see we’ve ended up writing, as we wanted to, three in terms of 39 and 15. So 3 is

equal to two times 39 minus 5 times fifteen. And we can check that: that’s

equal to 78 minus 75 so that is in fact equal to 3. And this method will work for any two integers,

so we can use Euclid’s algorithm to find the highest common factor, and then we can

write the highest common factor in terms of the original two numbers, where we’re

multiplying one of the numbers by one integer and the other number by another integer.

Thank you for giving such a clear explanation! I have a formal test coming up on this topic and this has really helped.

good job. nice video, clear content, simple explanation , 5 stars 🙂

Thank you! This was helpful for me as I'm studying for an elementary number theory exam

I use this android app to solve it: https://play.google.com/store/apps/details?id=com.petrixapp.daniel.euclid

Thank you. So much more enlightening than that obfuscating mess of a recursive algorithm I found in my abstract algebra text.

Only one problem though

W=-5 which means it is negative and therefore not an integer…

Great explanation!! Got a little confused thinking the x's were variables instead of regular multiplications lol; helped a ton for my Discrete Math exam!

Thank you so much. My discrete math professor and textbook make little sense by comparison! 😁

Makes absolutley no sense how you got 2 x 39- 5 x 15