utkarsh.agarwal.min19's blog

By utkarsh.agarwal.min19, history, 3 months ago, In English

• GCD of a set of numbers can be thought as a blue-print of those numbers. If u keep adding the GCD you can make all numbers that belong in that set.

• Every common divisor of a and b is a divisor of gcd(a,b).

• Gcd(a,b) where both a and b are non-zero, can also be defined as the smallest positive integer d which can be a solution/which can be expressed as a linear combination of a and b in the form d=a*p + b*q, where both p and q are integers.

• Gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.

• If 'a' divides b*c and gcd(a,b)=d , then a/d divides c.

• If m is a non-negative integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).It also follows from this property that if gcd(a,b)=g, then a/g and b/g should be coprime. Try to derive it yourslef.

• If m is any integer gcd(a,b)=gcd(a+m*b,b).

• The GCD: gcd(a, b) = gcd(b, a%b).

• If m is a positive common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m.

• GCD is a multiplicative function. That is if a1 and a2 are coprime gcd(a1*a2,b)=gcd(a1,b)*gcd(a2,b). -1. In particular, recalling that GCD is a positive integer valued function we obtain that gcd(a, b⋅c) = 1 if and only if gcd(a, b) = 1 and gcd(a, c) = 1. if the gcd is one then they need not be coprime to distribute the gcd, morever each gcd invidually should also be 1.

• The GCD is a commutative function: gcd(a, b) = gcd(b, a).

• The GCD is an associative function: gcd(a, gcd(b, c)) = gcd(gcd(a, b), c). Thus gcd(a, b, c, ...) can be used to denote the GCD of multiple arguments.

• gcd(a, b) is closely related to the least common multiple lcm(a, b): we have gcd(a, b)⋅lcm(a, b) = |a⋅b|.

• The following versions of distributivity hold true: gcd(a, lcm(b, c)) = lcm(gcd(a, b), gcd(a, c)) lcm(a, gcd(b, c)) = gcd(lcm(a, b), lcm(a, c)).

• If we have the unique prime factorizations of a = p1^e1*p2^e2 ⋅⋅⋅ pm^em and b = p1^f1*p2^f2 ⋅⋅⋅ pm^fm where ei ≥ 0 and fi ≥ 0, then the GCD of a and b is gcd(a,b) = p1^min(e1,f1) p2^min(e2,f2) ⋅⋅⋅ pm^min(em,fm).

• In a Cartesian coordinate system, gcd(a, b) can be interpreted as the number of segments between points with integral coordinates on the straight line segment joining the points (0, 0) and (a, b).

• For non-negative integers a and b, where a and b are not both zero, provable by considering the Euclidean algorithm in base n it simple states that: gcd(n^a-1,n^b-1)=n^gcd(a,b)-1

If u want an informal proof think of numbers in base 2 .We are calculating gcd's of number which contains all continuous 1 in their binary representations.. For ex: 001111 000011 their gcd can be the greatest common length which in this case is 2 thus the gcd becomes:000011 .Think of numbers in terms of length maybe you get the idea.

• An identity involving Euler's totient function: Gcd(a,b)=∑φ(k) where k are all common divisors of 'a' and 'b'

 
 
 
 
  • Vote: I like it
  • +11
  • Vote: I do not like it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is helpful for me. Thanks

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I think Third Line Is Saying "Greatest positive Integer d" Instead of Smallest.

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    No that is the beautiful part it is actually the smallest integer..try out some examples

    • »
      »
      »
      3 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      So if I Say gcd(12,24) then d is 12 (There are 1,2,3,4,6,12) and it is the maximum is guess.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

This is pretty good and helpful.

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

didn't understand the one before the last

  • »
    »
    3 months ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    the formatting ruined it: it simple states that:gcd(n^a-1,n^b-1)=n^gcd(a,b)-1

    If u want an informal proof think of numbers in base 2 .We are calculating gcds of number which contains all continuous 1 in their binary representations.. For ex: 001111 000011 their gcd can be the greates common length which in this case is 2 thus the gcd becomes:000011 .Think of numbers in terms of length maybe you get the idea

  • »
    »
    3 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    i have fixed it

»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by utkarsh.agarwal.min19 (previous revision, new revision, compare).

»
3 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Here's an interesting formula of $$$\gcd$$$ and Fibonacci number:

$$$F_{\gcd(a, b)}=\gcd(F_a,F_b)$$$
»
3 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by utkarsh.agarwal.min19 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by utkarsh.agarwal.min19 (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

can anyone explain the first one with an example ?

  • »
    »
    4 weeks ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Since GCD is a divisor for every number in the set of numbers, then we can also say that among the multiples of GCD (as in 1*GCD, 2*GCD, 3*GCD....) will contain the set of numbers too.

    For 2 numbers, a and b, if we know GCD(a,b),

    then for some positive integer m,

    a = m * GCD(a,b) == GCD(a,b) + GCD(a,b) +.....m times

    and some positive integer n,

    b = n * GCD(a,b) == GCD(a,b) + GCD(a,b) +.....n times

    • »
      »
      »
      4 weeks ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      thnx for wonderfully explaining this. Do u know some problems related to this GCD property ??

      • »
        »
        »
        »
        4 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Well, I am myself a newbie to this. If I come across, I'll post it here.