# Modulo và GCD
## Modulo
Phép chia lấy phần dư có những tính chất cơ bản sau:
$(a+b) \% n = (a \% n + b \% n) \% n$
$(a*b) \% n = (a \% n * b \% n) \% n$
## GCD
### Thuật toán "ngây thơ"
Duyệt từ $min(a, b)$ đến $1$ để tìm GCD.

for (int i=min(a,b);i>=1;i--){
    if (a%i==0&&b%i==0){
        return i;
    }
}

### Thuật toán Euclid
Dựa trên tính chất $GCD(a, b) = GCD(b, a \% b)$.

int gcd(a,b){
    if (b==0){
        return a;
    }
    else{
        gcd(b,a%b);
    }
}