Lý thuyết toán về phương trình đồng dư

[honghm211 (hoan_h3)]

Hãy tìm tất cả các số nguyên dương K sao cho tất cả các phần tử của mảng A[] lấy phần dư với K đều bằng nhau

Ví dụ với mảng A[] = {6, 38, 34} ta tìm được các số K = {1, 2, 4} vì:
6%1 = 38%1 = 34%1 =0; 6%2 = 38%2 = 34%2 =0; 6%4 = 38%4 = 34%4 =2;

các anh chị cho em hỏi về cơ sở lý thuyết của thuật toán đê giải bài trên với ạ. có tài liệu hoặc anh chị giải thích giúp em với. em cảm ơn

[rogp10]

\forall i,j \begin{cases} a_i \mod K = r \iff a_i = Kq_i + r,\ 0 \leq r < K\\ a_j \mod K = r \iff a_j = Kq_j + r \end{cases}\\ \Rightarrow a_i - a_j = K(q_i - q_j) \Rightarrow a_i-a_j\ \vdots\ K.\\ \overset{def}{\Rightarrow} \underset{\forall i,j}{gcd}(a_i - a_j) \ \vdots\ K. \ \ (*)\\ \forall m, n, d \in \N,\ m\ \vdots\ d \land \ n \ \vdots\ d \iff m - n \ \vdots\ d \land n\ \vdots\ d \Rightarrow gcd(m, n) = gcd(m-n, n)\\ \text{Áp dụng vào bài: }gcd(a_i - a_{min}, a_j - a_{min}) = gcd(a_i-a_j, a_j - a_{min})\\ \text{Từ tính chất kết hợp của gcd suy ra đpcm. } \blacksquare