정리

GCD, Euclid Algorithm gcd(a, b) = gcd(b, a%b) 를 기반으로 함. Modular Arthmetic a mod b = (a+kb) mod b, k는 임의의 정수 x*y mod b = (x mod b * y mod b) mod b Extended Euclid Algorithm 유클리드 알고리즘으로 나온 최대공약수로부터 역추적하며 gcd(a, b) = ax + by가 되는 x와 y를 찾음. int extended_gcd(int a, int b, int *x, int *y) { if (b == 0) { *x = 1; *y = 0; return a; } int x1 = *x; int y1 = *y; int gcd = extended_gcd(b, a % b, &x1, &y1); *..