上面匿名答案里用了一个简单事实不过没证。这里我重新整理一个证明。
只需要证明:存在正整数m,使得 (mod det(S)) 即可(这个命题可以看作初等数论里的欧拉定理的矩阵版本)。
考虑 由抽屉原理,其中必有两个,其对应位置的元素的差被 det(S) 整除。所以存在正整数 t, m, 使得 。其中 是一个整矩阵。
由于det(A)=1,我们知道 为一个整矩阵。所以 (mod det(S))。