DSA Math Notes

Properties of GCD

• \( \gcd\left(a,b\right)=\gcd\left(b,a\right) \) i.e. GCD is a cumutative function.
• \( \gcd\left(a,\gcd\left(b,c\right)\right)=\gcd\left(\gcd\left(a,b\right),c\right) \). i.e. GCD is assosiative function. Therefore, the GCD of multiple values can be simply denoted as \( \gcd\left(a,b,c,…\right) \).
• \( \gcd\left(a,0\right)=a \). Because any number \( a \) can equally devide both \( a \) as well as \( 0 \)
• If \( c \) is any constant integer, then \( \gcd\left(a,c\times a+r\right)=\gcd\left(a,r\right) \)
• Euclidean algorithm for GCD: Euclidean algorithm is based on the previous property ( \( \gcd\left(a,c\times a+r\right)=\gcd\left(a,r\right) \)). According to Euclidean algo, if \( a\ge b \) and \( r \) is remainder of \[ \frac{a}{b} \] then \( \gcd\left(a,b\right)=\gcd\left(r,b\right) \). Euclidean algo can be used to efficiently calculate GCD’s of two integers using recursive function calls.

    public int gcd(int a, int b) {
        if (b == 0) return a;
        //notice that the position of a % b, b are swapped, this is to ensure
        //that the right argument is always smaller than left argument
        //if not swapped, seperate condition checks have to be implemented which
        //will check the larger and smaller numbers to calculate the remainder
        return gcd(b, a % b);
    }

• If \( g \) is gcd of \( a \) and \( b \) then \( g \) is also a divisor of \( a+b \). In other words, \( \gcd\left(a,b\right)=\gcd\left(a,b,a+b\right) \).

• \( \gcd\left(a,b\right)=\gcd\left(a,a+b\right) \). Similarly, \( \gcd\left(a,b,c,…\right)=\gcd\left(a,a+b,a+b+c,…\right) \)
• \( \gcd\left(a,b\right)=\gcd\left(-a,b\right)=\gcd\left(a,-b\right)=\gcd\left(-a,-b\right) \)
• \( \gcd\left(…,a_i,….,a_j…\right)=\gcd\left(…,a_i,….,a_j+n\cdot a_i…\right) \).
• If \( a_1\text{ and }a_2 \) are co-prime, then \( \gcd\left(an,b\right)=\gcd\left(n,b\right) \)
• If \( \gcd\left(a,b\right)=d \), \( \Rightarrow a=P\cdot d \) and \( \Rightarrow b=Q\cdot d \) where \( P \) and \( Q \) are some constants, then \( P \) and \( Q \) are co-prime.
  • \( \gcd\left(P,Q\right)=1 \)

From wikipedia

• If a divides the product b⋅c, and gcd(a, b) = d, then a/d divides c.
• If m is a positive integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).
• If m is a positive common divisor of a and b, then gcd(a/m, b/m) = gcd(a, b)/m. This can further be deduced into following:
  1. \[ \gcd\left(\frac{a_1}{\gcd\left(a_1,…,a_i\right)},…,\frac{a_i}{\gcd\left(a_1,…,a_i\right)}\right)=\frac{\gcd\left(a_1,…,a_i\right)}{\gcd\left(a_1,…,a_i\right)}=1 \]
  2. \[ \gcd\left(a_1,…,a_i\right)=m\cdot\gcd\left(\frac{a_1}{m},…,\frac{a_i}{m}\right) \]
• If m is any integer, then gcd(a + m⋅b, b) = gcd(a, b)
• If a₁ and a₂ are relatively prime, then gcd(a₁⋅a₂, b) = gcd(a₁, b)⋅gcd(a₂, b)
• gcd(n^a − 1, n^b − 1) = n^gcd(a,b) − 1

https://en.wikipedia.org/wiki/Greatest_common_divisor#Properties

In addition to calculating just the GCD using euclidean algo as explained above in properties of GCD, the Extended Euclidean algorithm also helps in finding the coefficients of Bézout’s identity \( x \) and \( y \). i.e., if \( \gcd\left(a,b\right)=d \), then the extended euclidean helps in finding coefficients \( x \) and \( y \), such that \( xa+yb=d \).

The above equation is called Bézout’s identity. This equation is particularly usefull when \( a \) and \( b \) are co-primes, in that case, \( xa+yb=1 \) which implies that \( x \) is modular multiplicative inverse of \( a \) and \( y \) is modular multiplicative inverse of \( b \). Modular multiplicative inverse, for instance, has application in cryptography.

• Nice video explaining the Extended Euclidean algorithm for calculating cofficients of Bézout’s identity.

Implementation of Extended Euclidean Algorithm

class Solution{
    private int x, y, g;
 
    private void gcd(int a, int b) {
 
        //keep in mind the default value of x and y for base condition
        if (b == 0) {
            x = 1;
            y = 0;
            g = a;
            return;
        }
 
        //notice how x and y become x0 and y0 due to the recursive call
        gcd(b, a % b);
        int x0 = x, y0 = y;
 
        //following is performed based on the derived relations between x, y, x0 and y0
        x = y0;
        y = x0 - y0 * (a/b);
 
    }
 
    public void printGCD(int a,int b){
        x = 0; y = 0; g = 0;
 
        gcd(a, b);
 
        System.out.println("GCD of "+a+" and "+b+" : " + g);
        System.out.println("bezout's identity (a*x + b*y = GCD) : "+a+"*"+x+" + "+b+"*"+y+" = "+g);
    }
}
 
//Driver class
class Test {
    public static void main(String args[]) {
        new Solution().printGCD(12, 42);
    }
}

• If \( a \) and \( b \) both equally devide \( n \), i.e. \( a\mid n\text{ and }b\mid n \), then \( \operatorname{lcm}\left(a,b\right) \) also equally devides \( n \), i.e. \( \operatorname{lcm}\left(a,b\right)\mid n \)
• \( \operatorname{lcm}\left(an,bn\right)=n\operatorname{lcm}\left(a,b\right) \)
• If \( a \) and \( b \) are co-prime, then \[ \operatorname{lcm}\left(ab,n\right)=\frac{\operatorname{lcm}\left(a,n\right)\cdot\operatorname{lcm}\left(b,n\right)}{m} \]

Modulo vs Remainder

Modulo and Remainder are same when performed on positive operands, but can produce different result when operands are negative. in Java and C++, the % operator always produces the remainder of given operands. The result of % operator can be different when Modulo of operands is expected.

Remainder: The part that remains after integer devision of two operands.

Modulo (Euclidean division): Modulo is based on the division theorem according to which, if \( a \) and \( b \) are two integers, than there exist two integers \( q \) and \( r \), such that

int aMODb(int a, int b) {
    int mod = a % b;
    if (mod < 0)
        mod = Math.abs(b) + mod;
    return mod;
}

Congruence

• If a % m = b, then it can be said that “a is congruent to b with respect to modulo m” denoted \( a\equiv b\left(\text{mod}\ m\right) \)
• In other words, two integers a and b are said to be congruent module m if m is a divisor of their difference.
  \( \Rightarrow \) If \( a\equiv b\left(\text{mod}\ m\right) \) then \( a-b=k\cdot m \) (where \( k \) is some constant)

Modular multiplicative inverse

\( x \) is a modular multiplicative inverse of integer \( a \) (with respect to modulo \( m \)) if \( ax\ \text{mod}\ m=1 \) or \( ax\equiv1\left(\text{mod}\ m\right) \). Furthermore, modular multiplicative inverse \( x \) will exist only if \( a \) and \( m \) are co-prime, i.e. GCD of \( a \) and \( m \) is 1

Modular multiplicative inverse can be obtained:

• using Extended euclidean algorithm: Extended euclidean algorithm can be used to find the coefficient \( x \) and \( y \) in equation \( xa+yb=\gcd\left(a,b\right) \). If a and b are coprime, that is, if \( xa+yb=1 \), then x is the modular multiplicative inverse of a modulo b, and y is the modular multiplicative inverse of b modulo a.
  • Note: while using extended euclidean algorithm to find Modular multiplicative inverse (MMI), the MMI can sometimes come out to be negative. Simply add \( m \) to it to make it positive
• using Fermat’s little theorm (if \( m \) is prime)

Fermat’s little theorm

According to Fermat’s little theorm, if \( p \) is a prime number, then for any integer \( a \), \( a^p\equiv a\left(\ \text{mod}\ p\right) \) (or \( a^p\ mod\ p=a\ mod\ p \))

Deviding both sides in above equation by \( a \), \[ \frac{a^p}{a}\equiv\frac{a}{a}\left(\text{mod}\ \frac{p}{\gcd\left(a,p\right)}\right) \]

If \( a \) and \( p \) are coprime to each other, we get \[ a^{p-1}\equiv1\left(\text{mod}\ p\right) \]

Multiply above equation by \[ \frac{a}{a} \], we get \[ a\times a^{p-2}\equiv1\left(\text{mod}\ p\right) \]

Above equation implies that, for any integer \( a \), \[ a^{p-2} \] will be it’s inverse with respect to modulo \( p \) if \( p \) is a prime number and both \( a \) and \( p \) are co-prime to each other.

Properties of Modulos

• Distributive: \( \left(a+b\right)\ \text{mod}\ m\ =\ \left(a\ \text{mod}\ m\ +b\ \text{mod}\ m\right)\text{mod}\ m \)
• \( \left(a\times b\right)\ \text{mod}\ m\ =\ \left(a\ \text{mod}\ m\ \times b\ \text{mod}\ m\right)\text{mod}\ m \)
• However, same is not always true when it comes to division, i.e: \[ \left(\frac{a}{b}\right)\ \text{mod}\ m\ \ne\left(\frac{a\ \text{mod}\ m}{b\ \text{mod}\ m}\right) \]
• But, If \( a\equiv b\left(\ \text{mod}\ m\ \right) \), then \[ \frac{a}{d}\equiv\frac{b}{d}\left(\ \text{mod}\ \frac{m}{\gcd\left(m,d\right)}\right) \]
• \( \Rightarrow \) If \( a\equiv b\left(\text{mod}\ m\right) \) and if an integer \( d \) is coprime with \( m \) ,then \[ \frac{a}{d}\equiv\frac{b}{d}\left(\text{mod}\ m\right) \]

How to find \[ \left(\frac{a}{b}\right)\ \text{mod}\ m \] without directly dividing a by b (in case a and b are unknowingly huge)?

XOR operator properties

Problems

• Count number of times i_th bit is set in integers when counting from integer 0 to n

Matrix Exponentiation

Leetcode problem: 1220. Count Vowels Permutation with O(logN) solution using Matrix Exponentiation.

Power of adjacency Matrix

https://math.stackexchange.com/questions/1890620/finding-path-lengths-by-the-power-of-adjacency-matrix-of-an-undirected-graph

Leetcode problem : Knight Dialer with \( O\left(\log n\right) \) solution using power of adjacency matrix