需要的，構造互質集合是證明尤拉定理的基礎啊。
數論中的尤拉定理，指的是 ax≡1(modn) 。這個式子是在a和n互質的前提下成立的。 下面簡單闡述證明過程。
首先，我們知道在1到n的數中，與n互質的一共有φ(n)個，所以我們把這φ(n)個數拿出來，放到構造出的集合Zn中（注意，這就是題主問的問題中的互質集合），即為x1,x2……xφ(n)x1,x2……xφ(n)。 那麼接下來，我們可以再設出一個集合為M，設M中的數為： m1=a∗x1，m2=a∗x2，……，mφ(n)=a∗xφ(n)下面我們證明兩個推理：
一、M中任意兩個數都不模n同餘。 反證法。 證明：假設M中存在兩個數設為ma,mb模n同餘。 即ma≡mb移項得到：ma−mb=n∗k再將m用x來表示得到:a∗xa−a∗xb=n∗k。提取公因式得到a∗(xa−xb)=n∗k我們現在已知a與n互質，那麼式子就可以轉化為：xa−xb≡0（modn），因為a中沒有與n的公因子（1除外）所以a對模n同餘0並沒有什麼貢獻。 又因為xa,xb都是小於n的並且不會相同，所以xa−xb一定是小於n的，那麼上述的式子自然全都不成立。 假設不成立。 證得：M中任意兩個數都不模n同餘。
二、M中的數除以n的餘數全部與n互質。 證明：我們已知mi=a∗xi，又因為a與n互質，xi與n互質，所以可得mi與n互質。 帶入到歐幾里得演算法中推一步就好了。 即： gcd(a∗xi,n)=gcd(mi,n)=gcd(n,mimodn)=1 證畢。
根據我們證得的兩個性質，就可以開始推式子了。 首先，根據第二個性質可以知道，M中的數分別對應X中的每個數模n同餘。 所以可以得到： m1∗m2∗……∗mφ(n)≡x1∗x2∗……∗xφ(n)(modn) 現在我們把mi替換成x的形式，就可以得到： a∗x1∗a∗x2∗……∗a∗xφ(n)≡x1∗x2∗……∗xφ(n)(modn) 。這裡應該移項，但是在移項之前，將這麼多的a先乘起來： aφ(n)∗(x1∗x2……∗xφ(n))≡x1∗x2……∗xφ(n)(modn) ，這裡終於湊出了aφ(n)，那麼移項：(aφ(n)−1)∗(x1∗x2……∗xφ(n))≡0(modn) 然後，就證得尤拉定理：aφ(n)≡1(modn)。
需要的，構造互質集合是證明尤拉定理的基礎啊。
數論中的尤拉定理，指的是 ax≡1(modn) 。這個式子是在a和n互質的前提下成立的。 下面簡單闡述證明過程。
首先，我們知道在1到n的數中，與n互質的一共有φ(n)個，所以我們把這φ(n)個數拿出來，放到構造出的集合Zn中（注意，這就是題主問的問題中的互質集合），即為x1,x2……xφ(n)x1,x2……xφ(n)。 那麼接下來，我們可以再設出一個集合為M，設M中的數為： m1=a∗x1，m2=a∗x2，……，mφ(n)=a∗xφ(n)下面我們證明兩個推理：
一、M中任意兩個數都不模n同餘。 反證法。 證明：假設M中存在兩個數設為ma,mb模n同餘。 即ma≡mb移項得到：ma−mb=n∗k再將m用x來表示得到:a∗xa−a∗xb=n∗k。提取公因式得到a∗(xa−xb)=n∗k我們現在已知a與n互質，那麼式子就可以轉化為：xa−xb≡0（modn），因為a中沒有與n的公因子（1除外）所以a對模n同餘0並沒有什麼貢獻。 又因為xa,xb都是小於n的並且不會相同，所以xa−xb一定是小於n的，那麼上述的式子自然全都不成立。 假設不成立。 證得：M中任意兩個數都不模n同餘。
二、M中的數除以n的餘數全部與n互質。 證明：我們已知mi=a∗xi，又因為a與n互質，xi與n互質，所以可得mi與n互質。 帶入到歐幾里得演算法中推一步就好了。 即： gcd(a∗xi,n)=gcd(mi,n)=gcd(n,mimodn)=1 證畢。
根據我們證得的兩個性質，就可以開始推式子了。 首先，根據第二個性質可以知道，M中的數分別對應X中的每個數模n同餘。 所以可以得到： m1∗m2∗……∗mφ(n)≡x1∗x2∗……∗xφ(n)(modn) 現在我們把mi替換成x的形式，就可以得到： a∗x1∗a∗x2∗……∗a∗xφ(n)≡x1∗x2∗……∗xφ(n)(modn) 。這裡應該移項，但是在移項之前，將這麼多的a先乘起來： aφ(n)∗(x1∗x2……∗xφ(n))≡x1∗x2……∗xφ(n)(modn) ，這裡終於湊出了aφ(n)，那麼移項：(aφ(n)−1)∗(x1∗x2……∗xφ(n))≡0(modn) 然後，就證得尤拉定理：aφ(n)≡1(modn)。