Step
*
1
2
1
1
of Lemma
Euler-Fermat
1. n : {2...}
2. a : ℕ+
3. CoPrime(n,a)
4. Πx ∈ map(λi.(ai mod n);residues-mod(n)). x = Πx ∈ residues-mod(n). x ∈ ℤ
5. Πx ∈ residues-mod(n). (ax mod n) = Πx ∈ residues-mod(n). x ∈ ℤ
6. (Πx ∈ residues-mod(n). x * a^totient(n)) ≡ (Πx ∈ residues-mod(n). x * 1) mod n
7. L : {x:ℤ| CoPrime(n,x)}  List
8. residues-mod(n) = L ∈ ({x:ℤ| CoPrime(n,x)}  List)
⊢ CoPrime(accumulate (with value c and list item x): x * cover list:  Lwith starting value: 1),n)
BY
{ ((Thin (-1) THEN ListInd (-1)) THEN Reduce 0) }
1
1. n : {2...}
2. a : ℕ+
3. CoPrime(n,a)
4. Πx ∈ map(λi.(ai mod n);residues-mod(n)). x = Πx ∈ residues-mod(n). x ∈ ℤ
5. Πx ∈ residues-mod(n). (ax mod n) = Πx ∈ residues-mod(n). x ∈ ℤ
6. (Πx ∈ residues-mod(n). x * a^totient(n)) ≡ (Πx ∈ residues-mod(n). x * 1) mod n
⊢ CoPrime(1,n)
2
1. n : {2...}
2. a : ℕ+
3. CoPrime(n,a)
4. Πx ∈ map(λi.(ai mod n);residues-mod(n)). x = Πx ∈ residues-mod(n). x ∈ ℤ
5. Πx ∈ residues-mod(n). (ax mod n) = Πx ∈ residues-mod(n). x ∈ ℤ
6. (Πx ∈ residues-mod(n). x * a^totient(n)) ≡ (Πx ∈ residues-mod(n). x * 1) mod n
7. u : {x:ℤ| CoPrime(n,x)} 
8. v : {x:ℤ| CoPrime(n,x)}  List
9. CoPrime(accumulate (with value c and list item x): x * cover list:  vwith starting value: 1),n)
⊢ CoPrime(accumulate (with value c and list item x): x * cover list:  vwith starting value: u * 1),n)
Latex:
Latex:
1.  n  :  \{2...\}
2.  a  :  \mBbbN{}\msupplus{}
3.  CoPrime(n,a)
4.  \mPi{}x  \mmember{}  map(\mlambda{}i.(ai  mod  n);residues-mod(n)).  x  =  \mPi{}x  \mmember{}  residues-mod(n).  x
5.  \mPi{}x  \mmember{}  residues-mod(n).  (ax  mod  n)  =  \mPi{}x  \mmember{}  residues-mod(n).  x
6.  (\mPi{}x  \mmember{}  residues-mod(n).  x  *  a\^{}totient(n))  \mequiv{}  (\mPi{}x  \mmember{}  residues-mod(n).  x  *  1)  mod  n
7.  L  :  \{x:\mBbbZ{}|  CoPrime(n,x)\}    List
8.  residues-mod(n)  =  L
\mvdash{}  CoPrime(accumulate  (with  value  c  and  list  item  x):  x  *  cover  list:    Lwith  starting  value:  1),n)
By
Latex:
((Thin  (-1)  THEN  ListInd  (-1))  THEN  Reduce  0)
Home
Index