Number Theory | The GCD as a linear combination. 

Thanks, I just filmed and edited a video of this identity for polynomials. It should be up in a few days.

Michael Penn thanx a lot for the proof

Same thoughts here. Amazing proof!

Best mathematicians combine intution without loss in generality.

yup same thought and its correct

hello may I know what you mean by gives motivation for definitions and theories?

@@khbye2411 hello, so in math sometimes we are presented with theories that seem to have no motivation. Often it’s the case, the more math we learn the clearer the reason for those theories. Hence motivation to declare an idea a theorem

Hey! I know I'm slightly late, but since d divides a and b, and c also does that, and c divides d, that means d>=c (d,c€N). And since we didn't make any assumptions about c other than its a natural no that divides a and b, and yet, d is greater or equal to it, hence, its the greatest common divisor. I hope this was clear

No one cares

Think back to long division -- we keep going until the remainder is less than the divisor, otherwise we really haven't finished our division. For example, we don't say 53 divided by 4 is 10 with a remainder of 13, we say it is 13 with a remainder of 1. That is, we don't say 53 = 4(10) + 12, we say 53 = 4(13) + 1, where the r lies between 0 and 4.

When he says 'subset of N', he does not necessarily mean that it is a strict/proper subset of N (that is, it *could* be N itself); however, it is yet unclear as to whether it is exactly N or just some part of N, noting that if it were always precisely N, then the proof would follow trivially (as gcd(a,b) is in N by definition).

Consider a = 2, b = 4. Clearly - as we've defined that x,y are integers - any solution to our given form can only be an even integer, whereby we have at least one counterexample to S always being equivalent to N.

Suppose a = 17 and d = 6, so d does not divide a, as 6 doesn't divide 17. But, you can write 17 = 6(2) + 5. Here a = 17, d = 6, r = 5. So, a = d(q) + r. Notice that r can't be 6, because if it were, then 17 = 6(2) + 6 = 6(3) and then 6 would divide 17, which it obviously doesn't. Similarly, r can't be zero, because if it could be, than we could find an integer q such that 17 = 6(q) + 0 = 6q, and clearly there is no integer q that satisfies 17 = 6q. Putting it all together we have a = d(q) + r, where 0

@@davidbrisbane7206 as a sidenote, since the equation a = d.q + r is symmetric with respect to q, we can also write 0

Never ask a mathematician for applications

@@ranjitsarkar3126 it’s all for fun and glory :)

The GCD is used for a variety of applications in number theory, particularly in modular arithmetic and thus encryption algorithms such as RSA. It is also used for simpler applications, such as simplifying fractions.

Lol Bezout's Identity

Very clever 👏👏.