### utkarsh.agarwal.min19's blog

By utkarsh.agarwal.min19, history, 3 years ago,

• 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'

| Write comment?
 » 3 years ago, # |   0 This is pretty good and helpful.
 » 3 years ago, # |   0 didn't understand the one before the last
•  » » 3 years ago, # ^ |   +3 the formatting ruined it: it simple states that:gcd(n^a-1,n^b-1)=n^gcd(a,b)-1If 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 years ago, # |   +3 Here's an interesting formula of $\gcd$ and Fibonacci number: $F_{\gcd(a, b)}=\gcd(F_a,F_b)$
•  » » 16 months ago, # ^ |   +7 This relation is pretty interesting :)Important GCD properties we will use are $gcd(a,b) = gcd(a \pm kb,b) = gcd(b, a \% b)$, such that $a \pm kb \geq 0$. $gcd(a,0) = |a|$ for $a \neq 0$ , since any number is a divisor of 0, and the greatest divisor of $a$ is $|a|$ . $gcd(a_1 \cdot a_2,b) = gcd(a_1,b) \cdot gcd(a_2,b)$, if $a_1$ and $a_2$ are relatively prime. Let assume $a>b$, the base cases are $F_{0}=0$, $F_{1}=1$ and $F_{2}=1$ . Claim $I$ : Every 2 consecutive Fibonacci numbers will always be co-prime $gcd(F_{a+1},F_{a})=1$. Proof I Proof $I$ : Using $1$-st GCD property we can say, $gcd(F_{a+1},F_{a}) = gcd(F_{a} + F_{a-1},F_{a}) = gcd(F_{a-1},F_{a})$we back to $gcd(F_{a},F_{a-1})$ same relation just 1 step down and by induction we can bring it finally down to $gcd(F_{2},F_{1}) = 1$, which proves our claim. Claim $II$ : $gcd(F_{a},F_{b}) = gcd(F_{a-b},F_{b})$ Proof IIWe know $F_{a+1}$ and $F_{a}$ are co-prime, lets start by counting $F_{a+1}$ after decaying of $F_{a+ \Delta}$ and use $3$-rd GCD property to comment on $\Delta$ which diretly relates to $a-b$ in our claim. $gcd(Cnt_{ \Delta } \cdot F_{a+1},F_{a}) = gcd( Cnt_{ \Delta}, F_{a}) \cdot gcd(F_{a+1},F_{a})$We are ignoring count of $F_{a}$ after decaying of $F_{a+ \Delta}$ because we can always erase its presense using $1$-st GCD property. $gcd(Cnt_{ \Delta } \cdot F_{a+1},F_{a}) = gcd( Cnt_{ \Delta}, F_{a}) \cdot 1$ $= gcd(Cnt_{ \Delta}, F_{a})$Lets start counting simple, Counting slowly to see pattern . . . Case $1$ : $gcd(F_{a+2},F_{a})$ , lets count how much $gcd(F_{a+2},F_{a})$ $gcd(F_{a+1} + F_{a},F_{a})$which gives us $1$,Case $2$ : $gcd(F_{a+3},F_{a})$ , lets count how much $gcd(F_{a+3},F_{a})$ $gcd(F_{a+2} + F_{a+1},F_{a})$ $gcd(2 F_{a+1} + F_{a},F_{a})$which gives us $2$,Case $3$ : $gcd(F_{a+4},F_{a})$ , lets count how much $gcd(F_{a+4},F_{a})$ $gcd(F_{a+3} + F_{a+2},F_{a})$ $gcd(F_{a+2} + F_{a+1} + F_{a+1} + F_{a},F_{a})$ $gcd(3 F_{a+1} + 2F_{a},F_{a})$which gives us $3$, For case $4$ you will get count = $5$, Hmm. . . . now we can see $Cnt_{x} = Cnt_{x-1} + Cnt_{x-2}$, count given by 2 decays, which is also Fibonacci number, which gives us $Cnt_{\Delta} = F_{\Delta}$. If we see cleverly $Cnt_{x} = Cnt_{x-1} + Cnt_{x-2}$, count given by 2 decays which is also Fibonacci number, which gives us $Cnt_{\Delta} = F_{\Delta}$. $= gcd(F_{ \Delta}, F_{a})$Now lets bring $b$ and $a$ into picture like we used in our Claim $II$, where $a = b + \Delta$. $gcd(F_{a}, F_{b}) = gcd(F_{b + \Delta}, F_{b}) = gcd(F_{\Delta}, F_{b}) = gcd(F_{a-b}, F_{b})$which proves our claim. Corollary from Claim $II$ : $gcd(F_{a},F_{b}) = gcd(F_{b},F_{a \% b})$ , from GCD property $1$ we can keep on subtracting $b$ till $a-kb \geq 0$ which gives us $a \% b$ at the end. Final Steps : Now we are seeing that subscript variables are following same pattern for finding $gcd(a,b) = gcd(b,a \% b)$ recursively and indeed we do follow the same steps because of our proven Claims are allowing us do so. Just like $gcd(a,b)$ hit base case $gcd(x,0)$ and we claim $x$ is our Greatest Common Divisor, we will hit same base case for $F_{b},F_{a \% b}$ which will give, where $x = gcd(a,b)$ $gcd(F_{a},F_{b}) = gcd(F_{x},F_{0}) = F_{x} = F_{gcd(a,b)}$ $F_{gcd(a,b)} = gcd(F_{a},F_{b})$which proves the interesting relation between $gcd$ and Fibonacci.
•  » » » 5 months ago, # ^ |   0 Genralisation of 3rd one: gcd(a*b , c) = gcd(gcd(a,c) * gcd(b ,c) , c) 
•  » » » 4 weeks ago, # ^ |   0 How to prove that cnt and F(a+1) will be relatively prime , now since cnt also follows fibonacci sequence then the abosolute differece between delta and a+1 should be 1 otherwise, we can't apply 3rd property ..
 » 21 month(s) ago, # |   +5 Evergreen post
 » 9 months ago, # |   0 When solving 664A - Complicated GCD then how to input 10^100 digits in C program?Explain the data types of C...
•  » » 9 months ago, # ^ |   +11 What's the GCD of n,n+1?
•  » » 9 months ago, # ^ |   0 I don't know about C but in C++ you can take input as string
•  » » 4 weeks ago, # ^ |   +1 Note what it want you to solve. Not the $\gcd(a,b)$ but……
 » 2 months ago, # |   0 I need to prove that GCD(Lcm(a,b),Lcm(a,c)) = LCM(a*Gcd(b,c))