:: NTALGO_1 semantic presentation begin theorem :: NTALGO_1:1 (Bool "for" (Set (Var "x")) "," (Set (Var "p")) "being" ($#m1_hidden :::"Integer":::) "holds" (Bool (Set (Set "(" (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set (Var "p")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "p"))) ($#r1_hidden :::"="::: ) (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set (Var "p"))))) ; definitionlet "a", "b" be ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ); func :::"ALGO_GCD"::: "(" "a" "," "b" ")" -> ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) means :: NTALGO_1:def 1 (Bool "ex" (Set (Var "A")) "," (Set (Var "B")) "being" ($#m1_subset_1 :::"sequence":::) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "st" (Bool "(" (Bool (Set (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k1_int_2 :::"abs"::: ) "a")) & (Bool (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k1_int_2 :::"abs"::: ) "b")) & (Bool "(" "for" (Set (Var "i")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "holds" (Bool "(" (Bool (Set (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k4_nat_d :::"mod"::: ) (Set "(" (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ))) ")" ) ")" ) & (Bool it ($#r1_hidden :::"="::: ) (Set (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set "(" ($#k5_nat_1 :::"min*"::: ) "{" (Set (Var "i")) where i "is" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) : (Bool (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) "}" ")" ))) ")" )); end; :: deftheorem defines :::"ALGO_GCD"::: NTALGO_1:def 1 : (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) (Bool "for" (Set (Var "b3")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "holds" (Bool "(" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set ($#k1_ntalgo_1 :::"ALGO_GCD"::: ) "(" (Set (Var "a")) "," (Set (Var "b")) ")" )) "iff" (Bool "ex" (Set (Var "A")) "," (Set (Var "B")) "being" ($#m1_subset_1 :::"sequence":::) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "st" (Bool "(" (Bool (Set (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k1_int_2 :::"abs"::: ) (Set (Var "a")))) & (Bool (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k1_int_2 :::"abs"::: ) (Set (Var "b")))) & (Bool "(" "for" (Set (Var "i")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "holds" (Bool "(" (Bool (Set (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k4_nat_d :::"mod"::: ) (Set "(" (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ))) ")" ) ")" ) & (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set (Set (Var "A")) ($#k8_nat_1 :::"."::: ) (Set "(" ($#k5_nat_1 :::"min*"::: ) "{" (Set (Var "i")) where i "is" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) : (Bool (Set (Set (Var "B")) ($#k8_nat_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) "}" ")" ))) ")" )) ")" ))); theorem :: NTALGO_1:2 (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "holds" (Bool (Set ($#k1_ntalgo_1 :::"ALGO_GCD"::: ) "(" (Set (Var "a")) "," (Set (Var "b")) ")" ) ($#r1_hidden :::"="::: ) (Set (Set (Var "a")) ($#k3_int_2 :::"gcd"::: ) (Set (Var "b"))))) ; begin scheme :: NTALGO_1:sch 1 QuadChoiceRec{ F1() -> ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m1_hidden :::"set"::: ) , F2() -> ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m1_hidden :::"set"::: ) , F3() -> ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m1_hidden :::"set"::: ) , F4() -> ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m1_hidden :::"set"::: ) , F5() -> ($#m1_subset_1 :::"Element"::: ) "of" (Set F1 "(" ")" ), F6() -> ($#m1_subset_1 :::"Element"::: ) "of" (Set F2 "(" ")" ), F7() -> ($#m1_subset_1 :::"Element"::: ) "of" (Set F3 "(" ")" ), F8() -> ($#m1_subset_1 :::"Element"::: ) "of" (Set F4 "(" ")" ), P1[ ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) "," ($#m1_hidden :::"set"::: ) ] } : (Bool "ex" (Set (Var "f")) "being" ($#m1_subset_1 :::"Function":::) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "," (Set F1 "(" ")" )(Bool "ex" (Set (Var "g")) "being" ($#m1_subset_1 :::"Function":::) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "," (Set F2 "(" ")" )(Bool "ex" (Set (Var "h")) "being" ($#m1_subset_1 :::"Function":::) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "," (Set F3 "(" ")" )(Bool "ex" (Set (Var "i")) "being" ($#m1_subset_1 :::"Function":::) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "," (Set F4 "(" ")" ) "st" (Bool "(" (Bool (Set (Set (Var "f")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set F5 "(" ")" )) & (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set F6 "(" ")" )) & (Bool (Set (Set (Var "h")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set F7 "(" ")" )) & (Bool (Set (Set (Var "i")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set F8 "(" ")" )) & (Bool "(" "for" (Set (Var "n")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "holds" (Bool P1[(Set (Var "n")) "," (Set (Set (Var "f")) ($#k8_nat_1 :::"."::: ) (Set (Var "n"))) "," (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "n"))) "," (Set (Set (Var "h")) ($#k8_nat_1 :::"."::: ) (Set (Var "n"))) "," (Set (Set (Var "i")) ($#k8_nat_1 :::"."::: ) (Set (Var "n"))) "," (Set (Set (Var "f")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "n")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) "," (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "n")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) "," (Set (Set (Var "h")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "n")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) "," (Set (Set (Var "i")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "n")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ))]) ")" ) ")" ))))) provided (Bool "for" (Set (Var "n")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) (Bool "for" (Set (Var "x")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F1 "(" ")" ) (Bool "for" (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F2 "(" ")" ) (Bool "for" (Set (Var "z")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F3 "(" ")" ) (Bool "for" (Set (Var "w")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F4 "(" ")" ) (Bool "ex" (Set (Var "x1")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F1 "(" ")" )(Bool "ex" (Set (Var "y1")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F2 "(" ")" )(Bool "ex" (Set (Var "z1")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F3 "(" ")" )(Bool "ex" (Set (Var "w1")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set F4 "(" ")" ) "st" (Bool P1[(Set (Var "n")) "," (Set (Var "x")) "," (Set (Var "y")) "," (Set (Var "z")) "," (Set (Var "w")) "," (Set (Var "x1")) "," (Set (Var "y1")) "," (Set (Var "z1")) "," (Set (Var "w1"))])))))))))) proof end; definitionlet "x", "y" be ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ); func :::"ALGO_EXGCD"::: "(" "x" "," "y" ")" -> ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k3_zfmisc_1 :::"[:"::: ) (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) ($#k3_zfmisc_1 :::":]"::: ) ) means :: NTALGO_1:def 2 (Bool "ex" (Set (Var "g")) "," (Set (Var "w")) "," (Set (Var "q")) "," (Set (Var "t")) "," (Set (Var "a")) "," (Set (Var "b")) "," (Set (Var "v")) "," (Set (Var "u")) "being" ($#m1_subset_1 :::"sequence":::) "of" (Set ($#k4_numbers :::"INT"::: ) )(Bool "ex" (Set (Var "istop")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "st" (Bool "(" (Bool (Set (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool (Set (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) "x") & (Bool (Set (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) "y") & (Bool (Set (Set (Var "t")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool "(" "for" (Set (Var "i")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "holds" (Bool "(" (Bool (Set (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k5_int_1 :::"div"::: ) (Set "(" (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ))) & (Bool (Set (Set (Var "t")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ))) & (Bool (Set (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Set "(" (Set "(" (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ))) & (Bool (Set (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Set "(" (Set "(" (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ))) & (Bool (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "t")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ))) ")" ) ")" ) & (Bool (Set (Var "istop")) ($#r1_hidden :::"="::: ) (Set ($#k5_nat_1 :::"min*"::: ) "{" (Set (Var "i")) where i "is" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) : (Bool (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) "}" )) & "(" (Bool (Bool (Set ($#k6_numbers :::"0"::: ) ) ($#r1_xxreal_0 :::"<="::: ) (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop"))))) "implies" (Bool it ($#r1_hidden :::"="::: ) (Set ($#k3_xtuple_0 :::"["::: ) (Set "(" (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) "," (Set "(" (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) "," (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ($#k3_xtuple_0 :::"]"::: ) )) ")" & "(" (Bool (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop"))) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "implies" (Bool it ($#r1_hidden :::"="::: ) (Set ($#k3_xtuple_0 :::"["::: ) (Set "(" ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ")" ) "," (Set "(" ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ")" ) "," (Set "(" ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ")" ) ($#k3_xtuple_0 :::"]"::: ) )) ")" ")" ))); end; :: deftheorem defines :::"ALGO_EXGCD"::: NTALGO_1:def 2 : (Bool "for" (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) (Bool "for" (Set (Var "b3")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k3_zfmisc_1 :::"[:"::: ) (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) ($#k3_zfmisc_1 :::":]"::: ) ) "holds" (Bool "(" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "x")) "," (Set (Var "y")) ")" )) "iff" (Bool "ex" (Set (Var "g")) "," (Set (Var "w")) "," (Set (Var "q")) "," (Set (Var "t")) "," (Set (Var "a")) "," (Set (Var "b")) "," (Set (Var "v")) "," (Set (Var "u")) "being" ($#m1_subset_1 :::"sequence":::) "of" (Set ($#k4_numbers :::"INT"::: ) )(Bool "ex" (Set (Var "istop")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "st" (Bool "(" (Bool (Set (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool (Set (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set (Var "x"))) & (Bool (Set (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set (Var "y"))) & (Bool (Set (Set (Var "t")) ($#k8_nat_1 :::"."::: ) (Set ($#k6_numbers :::"0"::: ) )) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool "(" "for" (Set (Var "i")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "holds" (Bool "(" (Bool (Set (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k5_int_1 :::"div"::: ) (Set "(" (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ))) & (Bool (Set (Set (Var "t")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ))) & (Bool (Set (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Set "(" (Set "(" (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "u")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ))) & (Bool (Set (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Set "(" (Set "(" (Set (Var "q")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "v")) ($#k8_nat_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ))) & (Bool (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "t")) ($#k8_nat_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ))) ")" ) ")" ) & (Bool (Set (Var "istop")) ($#r1_hidden :::"="::: ) (Set ($#k5_nat_1 :::"min*"::: ) "{" (Set (Var "i")) where i "is" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) : (Bool (Set (Set (Var "w")) ($#k8_nat_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set ($#k6_numbers :::"0"::: ) )) "}" )) & "(" (Bool (Bool (Set ($#k6_numbers :::"0"::: ) ) ($#r1_xxreal_0 :::"<="::: ) (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop"))))) "implies" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set ($#k3_xtuple_0 :::"["::: ) (Set "(" (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) "," (Set "(" (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) "," (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ($#k3_xtuple_0 :::"]"::: ) )) ")" & "(" (Bool (Bool (Set (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop"))) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "implies" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set ($#k3_xtuple_0 :::"["::: ) (Set "(" ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "a")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ")" ) "," (Set "(" ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "b")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ")" ) "," (Set "(" ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "g")) ($#k8_nat_1 :::"."::: ) (Set (Var "istop")) ")" ) ")" ) ($#k3_xtuple_0 :::"]"::: ) )) ")" ")" ))) ")" ))); theorem :: NTALGO_1:3 (Bool "for" (Set (Var "i2")) "," (Set (Var "i1")) "being" ($#m1_hidden :::"Integer":::) "st" (Bool (Bool (Set (Var "i2")) ($#r1_xxreal_0 :::"<="::: ) (Set ($#k6_numbers :::"0"::: ) ))) "holds" (Bool (Set (Set (Var "i1")) ($#k6_int_1 :::"mod"::: ) (Set (Var "i2"))) ($#r1_xxreal_0 :::"<="::: ) (Set ($#k6_numbers :::"0"::: ) ))) ; theorem :: NTALGO_1:4 (Bool "for" (Set (Var "i2")) "," (Set (Var "i1")) "being" ($#m1_hidden :::"Integer":::) "st" (Bool (Bool (Set (Var "i2")) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "holds" (Bool (Set ($#k4_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "i1")) ($#k6_int_1 :::"mod"::: ) (Set (Var "i2")) ")" )) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k4_xcmplx_0 :::"-"::: ) (Set (Var "i2"))))) ; theorem :: NTALGO_1:5 (Bool "for" (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set ($#k1_int_2 :::"abs"::: ) (Set (Var "y"))) ($#r1_hidden :::"<>"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "holds" (Bool (Set ($#k1_int_2 :::"abs"::: ) (Set "(" (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set (Var "y")) ")" )) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k1_int_2 :::"abs"::: ) (Set (Var "y"))))) ; theorem :: NTALGO_1:6 (Bool "for" (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "holds" (Bool "(" (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "x")) "," (Set (Var "y")) ")" ")" ) ($#k3_mcart_1 :::"`3_3"::: ) ) ($#r1_hidden :::"="::: ) (Set (Set (Var "x")) ($#k3_int_2 :::"gcd"::: ) (Set (Var "y")))) & (Bool (Set (Set "(" (Set "(" (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "x")) "," (Set (Var "y")) ")" ")" ) ($#k1_mcart_1 :::"`1_3"::: ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "x")) ")" ) ($#k2_xcmplx_0 :::"+"::: ) (Set "(" (Set "(" (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "x")) "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "y")) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "x")) ($#k3_int_2 :::"gcd"::: ) (Set (Var "y")))) ")" )) ; definitionlet "x", "p" be ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ); func :::"ALGO_INVERSE"::: "(" "x" "," "p" ")" -> ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) means :: NTALGO_1:def 3 (Bool "for" (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set (Var "y")) ($#r1_hidden :::"="::: ) (Set "x" ($#k6_int_1 :::"mod"::: ) "p"))) "holds" (Bool "(" "(" (Bool (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" "p" "," (Set (Var "y")) ")" ")" ) ($#k3_mcart_1 :::"`3_3"::: ) ) ($#r1_hidden :::"="::: ) (Num 1))) "implies" (Bool "(" "(" (Bool (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" "p" "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) ) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "implies" (Bool "ex" (Set (Var "z")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set (Var "z")) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" "p" "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) )) & (Bool it ($#r1_hidden :::"="::: ) (Set "p" ($#k2_xcmplx_0 :::"+"::: ) (Set (Var "z")))) ")" )) ")" & "(" (Bool (Bool (Set ($#k6_numbers :::"0"::: ) ) ($#r1_xxreal_0 :::"<="::: ) (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" "p" "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) ))) "implies" (Bool it ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" "p" "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) )) ")" ")" ) ")" & "(" (Bool (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" "p" "," (Set (Var "y")) ")" ")" ) ($#k3_mcart_1 :::"`3_3"::: ) ) ($#r1_hidden :::"<>"::: ) (Num 1))) "implies" (Bool it ($#r1_hidden :::"="::: ) (Set ($#k1_xboole_0 :::"{}"::: ) )) ")" ")" )); end; :: deftheorem defines :::"ALGO_INVERSE"::: NTALGO_1:def 3 : (Bool "for" (Set (Var "x")) "," (Set (Var "p")) "," (Set (Var "b3")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "holds" (Bool "(" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set ($#k3_ntalgo_1 :::"ALGO_INVERSE"::: ) "(" (Set (Var "x")) "," (Set (Var "p")) ")" )) "iff" (Bool "for" (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set (Var "y")) ($#r1_hidden :::"="::: ) (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set (Var "p"))))) "holds" (Bool "(" "(" (Bool (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k3_mcart_1 :::"`3_3"::: ) ) ($#r1_hidden :::"="::: ) (Num 1))) "implies" (Bool "(" "(" (Bool (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) ) ($#r1_xxreal_0 :::"<"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "implies" (Bool "ex" (Set (Var "z")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set (Var "z")) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) )) & (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set (Set (Var "p")) ($#k2_xcmplx_0 :::"+"::: ) (Set (Var "z")))) ")" )) ")" & "(" (Bool (Bool (Set ($#k6_numbers :::"0"::: ) ) ($#r1_xxreal_0 :::"<="::: ) (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) ))) "implies" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k2_mcart_1 :::"`2_3"::: ) )) ")" ")" ) ")" & "(" (Bool (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k3_mcart_1 :::"`3_3"::: ) ) ($#r1_hidden :::"<>"::: ) (Num 1))) "implies" (Bool (Set (Var "b3")) ($#r1_hidden :::"="::: ) (Set ($#k1_xboole_0 :::"{}"::: ) )) ")" ")" )) ")" )); theorem :: NTALGO_1:7 (Bool "for" (Set (Var "x")) "," (Set (Var "p")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set (Var "y")) ($#r1_hidden :::"="::: ) (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set (Var "p")))) & (Bool (Set (Set "(" ($#k2_ntalgo_1 :::"ALGO_EXGCD"::: ) "(" (Set (Var "p")) "," (Set (Var "y")) ")" ")" ) ($#k3_mcart_1 :::"`3_3"::: ) ) ($#r1_hidden :::"="::: ) (Num 1))) "holds" (Bool (Set (Set "(" (Set "(" ($#k3_ntalgo_1 :::"ALGO_INVERSE"::: ) "(" (Set (Var "x")) "," (Set (Var "p")) ")" ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "x")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "p"))) ($#r1_hidden :::"="::: ) (Set (Num 1) ($#k6_int_1 :::"mod"::: ) (Set (Var "p"))))) ; begin definitionlet "nlist" be ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k2_zfmisc_1 :::"[:"::: ) (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) ($#k2_zfmisc_1 :::":]"::: ) ); func :::"ALGO_CRT"::: "nlist" -> ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) means :: NTALGO_1:def 4 (Bool "(" "(" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) "nlist") ($#r1_hidden :::"="::: ) (Num 1))) "implies" (Bool it ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Num 1) ")" ) ($#k1_xtuple_0 :::"`1"::: ) )) ")" & "(" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) "nlist") ($#r1_hidden :::"<>"::: ) (Num 1))) "implies" (Bool "ex" (Set (Var "m")) "," (Set (Var "n")) "," (Set (Var "prodc")) "," (Set (Var "prodi")) "being" ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) )(Bool "ex" (Set (Var "M0")) "," (Set (Var "M")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "m"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) "nlist")) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "n"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) "nlist")) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "prodc"))) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) "nlist" ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1))) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "prodi"))) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) "nlist" ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1))) & (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Num 1)) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "i"))) & (Bool (Set (Var "i")) ($#r1_xxreal_0 :::"<="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1)))) "holds" (Bool "ex" (Set (Var "d")) "," (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set (Var "x")) ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "x")))) & (Bool (Set (Var "y")) ($#r1_hidden :::"="::: ) (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ))) & (Bool (Set (Var "d")) ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Set (Var "prodi")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set ($#k3_ntalgo_1 :::"ALGO_INVERSE"::: ) "(" (Set (Var "y")) "," (Set (Var "d")) ")" )) & (Bool (Set (Set (Var "prodc")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set (Var "y"))) ")" )) ")" ) & (Bool (Set (Var "M0")) ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Var "M")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "prodc")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "M0")))) & (Bool (Set (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Num 1)) ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Num 1) ")" ) ($#k1_xtuple_0 :::"`1"::: ) )) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "i"))) & (Bool (Set (Var "i")) ($#r1_xxreal_0 :::"<="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1)))) "holds" (Bool "ex" (Set (Var "u")) "," (Set (Var "u0")) "," (Set (Var "u1")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set (Var "u0")) ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k1_xtuple_0 :::"`1"::: ) )) & (Bool (Set (Var "u1")) ($#r1_hidden :::"="::: ) (Set (Set "(" "nlist" ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Var "u")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set "(" (Set (Var "u0")) ($#k6_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "prodi")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "u1")))) & (Bool (Set (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k2_xcmplx_0 :::"+"::: ) (Set "(" (Set (Var "u")) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "prodc")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ))) ")" )) ")" ) & (Bool it ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "M")))) ")" ))) ")" ")" ); end; :: deftheorem defines :::"ALGO_CRT"::: NTALGO_1:def 4 : (Bool "for" (Set (Var "nlist")) "being" ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k2_zfmisc_1 :::"[:"::: ) (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) ($#k2_zfmisc_1 :::":]"::: ) ) (Bool "for" (Set (Var "b2")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "holds" (Bool "(" (Bool (Set (Var "b2")) ($#r1_hidden :::"="::: ) (Set ($#k4_ntalgo_1 :::"ALGO_CRT"::: ) (Set (Var "nlist")))) "iff" (Bool "(" "(" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist"))) ($#r1_hidden :::"="::: ) (Num 1))) "implies" (Bool (Set (Var "b2")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Num 1) ")" ) ($#k1_xtuple_0 :::"`1"::: ) )) ")" & "(" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist"))) ($#r1_hidden :::"<>"::: ) (Num 1))) "implies" (Bool "ex" (Set (Var "m")) "," (Set (Var "n")) "," (Set (Var "prodc")) "," (Set (Var "prodi")) "being" ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) )(Bool "ex" (Set (Var "M0")) "," (Set (Var "M")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "m"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")))) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "n"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")))) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "prodc"))) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1))) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "prodi"))) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1))) & (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Num 1)) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "i"))) & (Bool (Set (Var "i")) ($#r1_xxreal_0 :::"<="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1)))) "holds" (Bool "ex" (Set (Var "d")) "," (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set (Var "x")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "x")))) & (Bool (Set (Var "y")) ($#r1_hidden :::"="::: ) (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ))) & (Bool (Set (Var "d")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Set (Var "prodi")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set ($#k3_ntalgo_1 :::"ALGO_INVERSE"::: ) "(" (Set (Var "y")) "," (Set (Var "d")) ")" )) & (Bool (Set (Set (Var "prodc")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"="::: ) (Set (Var "y"))) ")" )) ")" ) & (Bool (Set (Var "M0")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Var "M")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "prodc")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set (Var "M0")))) & (Bool (Set (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Num 1)) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Num 1) ")" ) ($#k1_xtuple_0 :::"`1"::: ) )) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "i"))) & (Bool (Set (Var "i")) ($#r1_xxreal_0 :::"<="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ($#k6_xcmplx_0 :::"-"::: ) (Num 1)))) "holds" (Bool "ex" (Set (Var "u")) "," (Set (Var "u0")) "," (Set (Var "u1")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set (Var "u0")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k1_xtuple_0 :::"`1"::: ) )) & (Bool (Set (Var "u1")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" ) ")" ) ($#k2_xtuple_0 :::"`2"::: ) )) & (Bool (Set (Var "u")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set "(" (Set (Var "u0")) ($#k6_xcmplx_0 :::"-"::: ) (Set "(" (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "prodi")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "u1")))) & (Bool (Set (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k2_xcmplx_0 :::"+"::: ) (Set "(" (Set (Var "u")) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "prodc")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ")" ))) ")" )) ")" ) & (Bool (Set (Var "b2")) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "n")) ($#k1_funct_1 :::"."::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "m")) ")" ) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "M")))) ")" ))) ")" ")" ) ")" ))); theorem :: NTALGO_1:8 (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set (Var "b")) ($#r1_hidden :::"<>"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "holds" (Bool (Set (Set (Var "a")) ($#k6_int_1 :::"mod"::: ) (Set (Var "b"))) "," (Set (Var "a")) ($#r2_int_1 :::"are_congruent_mod"::: ) (Set (Var "b")))) ; theorem :: NTALGO_1:9 (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set (Var "b")) ($#r1_hidden :::"<>"::: ) (Set ($#k6_numbers :::"0"::: ) ))) "holds" (Bool (Set (Set "(" (Set (Var "a")) ($#k6_int_1 :::"mod"::: ) (Set (Var "b")) ")" ) ($#k3_int_2 :::"gcd"::: ) (Set (Var "b"))) ($#r1_hidden :::"="::: ) (Set (Set (Var "a")) ($#k3_int_2 :::"gcd"::: ) (Set (Var "b"))))) ; theorem :: NTALGO_1:10 (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "," (Set (Var "c")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set (Var "c")) ($#r1_hidden :::"<>"::: ) (Set ($#k6_numbers :::"0"::: ) )) & (Bool (Set (Var "a")) ($#r1_hidden :::"="::: ) (Set (Set (Var "b")) ($#k6_int_1 :::"mod"::: ) (Set (Var "c")))) & (Bool (Set (Var "b")) "," (Set (Var "c")) ($#r1_int_2 :::"are_relative_prime"::: ) )) "holds" (Bool (Set (Var "a")) "," (Set (Var "c")) ($#r1_int_2 :::"are_relative_prime"::: ) )) ; theorem :: NTALGO_1:11 (Bool "for" (Set (Var "nlist")) "being" ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k2_zfmisc_1 :::"[:"::: ) (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) ($#k2_zfmisc_1 :::":]"::: ) ) (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "being" ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "a"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")))) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "a"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")))) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" )))) "holds" (Bool (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"<>"::: ) (Set ($#k6_numbers :::"0"::: ) )) ")" ) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" )))) "holds" (Bool "(" (Bool (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k1_xtuple_0 :::"`1"::: ) ) ($#r1_hidden :::"="::: ) (Set (Set (Var "a")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k2_xtuple_0 :::"`2"::: ) ) ($#r1_hidden :::"="::: ) (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")))) ")" ) ")" ) & (Bool "(" "for" (Set (Var "i")) "," (Set (Var "j")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" ))) & (Bool (Set (Var "j")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" ))) & (Bool (Set (Var "i")) ($#r1_hidden :::"<>"::: ) (Set (Var "j")))) "holds" (Bool (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) "," (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "j"))) ($#r1_int_2 :::"are_relative_prime"::: ) ) ")" )) "holds" (Bool "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" )))) "holds" (Bool (Set (Set "(" ($#k4_ntalgo_1 :::"ALGO_CRT"::: ) (Set (Var "nlist")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "a")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" )))))) ; theorem :: NTALGO_1:12 (Bool "for" (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) (Bool "for" (Set (Var "b")) "," (Set (Var "m")) "being" ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Num 2) ($#r1_xxreal_0 :::"<="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")))) & (Bool "(" "for" (Set (Var "i")) "," (Set (Var "j")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")) ")" ))) & (Bool (Set (Var "j")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")) ")" ))) & (Bool (Set (Var "i")) ($#r1_hidden :::"<>"::: ) (Set (Var "j")))) "holds" (Bool (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) "," (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "j"))) ($#r1_int_2 :::"are_relative_prime"::: ) ) ")" ) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")) ")" )))) "holds" (Bool (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "y")) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ))) ")" ) & (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Num 1)) ($#r1_hidden :::"="::: ) (Num 1))) "holds" (Bool "for" (Set (Var "k")) "being" ($#m2_subset_1 :::"Element"::: ) "of" (Set ($#k5_numbers :::"NAT"::: ) ) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "k"))) & (Bool (Set (Var "k")) ($#r1_xxreal_0 :::"<="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")))) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "i"))) & (Bool (Set (Var "i")) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "k")))) "holds" (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ))) ")" )) "holds" (Bool (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "k")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ) ")" )) ($#r1_hidden :::"="::: ) (Set (Set (Var "y")) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "k")) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ) ")" )))))) ; theorem :: NTALGO_1:13 (Bool "for" (Set (Var "b")) "being" ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "b"))) ($#r1_hidden :::"="::: ) (Num 1))) "holds" (Bool (Set ($#k19_rvsum_1 :::"Product"::: ) (Set (Var "b"))) ($#r1_hidden :::"="::: ) (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Num 1)))) ; theorem :: NTALGO_1:14 (Bool "for" (Set (Var "b")) "being" ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) (Bool "ex" (Set (Var "m")) "being" ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool "(" (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "m"))) ($#r1_hidden :::"="::: ) (Set (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")) ")" ) ($#k2_nat_1 :::"+"::: ) (Num 1))) & (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Num 1)) ($#r1_hidden :::"="::: ) (Num 1)) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Num 1) ($#r1_xxreal_0 :::"<="::: ) (Set (Var "i"))) & (Bool (Set (Var "i")) ($#r1_xxreal_0 :::"<="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "b"))))) "holds" (Bool (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set (Var "i")) ($#k1_nat_1 :::"+"::: ) (Num 1) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k3_xcmplx_0 :::"*"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ))) ")" ) & (Bool (Set ($#k19_rvsum_1 :::"Product"::: ) (Set (Var "b"))) ($#r1_hidden :::"="::: ) (Set (Set (Var "m")) ($#k1_funct_1 :::"."::: ) (Set "(" (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")) ")" ) ($#k2_nat_1 :::"+"::: ) (Num 1) ")" ))) ")" ))) ; theorem :: NTALGO_1:15 (Bool "for" (Set (Var "nlist")) "being" ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k2_zfmisc_1 :::"[:"::: ) (Set ($#k4_numbers :::"INT"::: ) ) "," (Set ($#k4_numbers :::"INT"::: ) ) ($#k2_zfmisc_1 :::":]"::: ) ) (Bool "for" (Set (Var "a")) "," (Set (Var "b")) "being" ($#~v1_xboole_0 "non" ($#v1_xboole_0 :::"empty"::: ) ) ($#m2_finseq_1 :::"FinSequence"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) (Bool "for" (Set (Var "x")) "," (Set (Var "y")) "being" ($#m1_subset_1 :::"Element"::: ) "of" (Set ($#k4_numbers :::"INT"::: ) ) "st" (Bool (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "a"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "b")))) & (Bool (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "a"))) ($#r1_hidden :::"="::: ) (Set ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")))) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" )))) "holds" (Bool (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) ($#r1_hidden :::"<>"::: ) (Set ($#k6_numbers :::"0"::: ) )) ")" ) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" )))) "holds" (Bool "(" (Bool (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k1_xtuple_0 :::"`1"::: ) ) ($#r1_hidden :::"="::: ) (Set (Set (Var "a")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")))) & (Bool (Set (Set "(" (Set (Var "nlist")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k2_xtuple_0 :::"`2"::: ) ) ($#r1_hidden :::"="::: ) (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")))) ")" ) ")" ) & (Bool "(" "for" (Set (Var "i")) "," (Set (Var "j")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" ))) & (Bool (Set (Var "j")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" ))) & (Bool (Set (Var "i")) ($#r1_hidden :::"<>"::: ) (Set (Var "j")))) "holds" (Bool (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i"))) "," (Set (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "j"))) ($#r1_int_2 :::"are_relative_prime"::: ) ) ")" ) & (Bool "(" "for" (Set (Var "i")) "being" ($#m1_hidden :::"Nat":::) "st" (Bool (Bool (Set (Var "i")) ($#r2_hidden :::"in"::: ) (Set ($#k2_finseq_1 :::"Seg"::: ) (Set "(" ($#k3_finseq_1 :::"len"::: ) (Set (Var "nlist")) ")" )))) "holds" (Bool (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" )) ($#r1_hidden :::"="::: ) (Set (Set "(" (Set (Var "a")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set "(" (Set (Var "b")) ($#k1_funct_1 :::"."::: ) (Set (Var "i")) ")" ))) ")" ) & (Bool (Set (Var "y")) ($#r1_hidden :::"="::: ) (Set ($#k19_rvsum_1 :::"Product"::: ) (Set (Var "b"))))) "holds" (Bool (Set (Set "(" ($#k4_ntalgo_1 :::"ALGO_CRT"::: ) (Set (Var "nlist")) ")" ) ($#k6_int_1 :::"mod"::: ) (Set (Var "y"))) ($#r1_hidden :::"="::: ) (Set (Set (Var "x")) ($#k6_int_1 :::"mod"::: ) (Set (Var "y"))))))) ;