  Our main result is a new proof of correctness of Euclid's algorithm. The
proof is conducted in algorithmic theory of natural numbers Th3. A formula H is
constructed that expresses the halting property of the algorithm. Next, the
proof of H is is presented. In the proof we make use of inference rules of
calculus of programs. The only formulas accepted without the proof are axioms
of program calculus or axioms of the theory Th3. We complete our result by
showing that the theorem on correctness of Euclid's algorithm can not be proved
in any elementary theory of natural numbers.
