Verified Program Extraction in Number Theory: The Fundamental Theorem of Arithmetic and Relatives The research for this document was funded by the Austrian Science Fund (FWF) 10.55776/ESP576 . Many thanks to Helmut Schwichtenberg for providing valuable tips on writing the Minlog code and for integrating it into the official Minlog version. Franziskus Wiesnet Abstract This article revisits standard theorems from elementary number theory through a constructive, algorithmic, and proof-theoretic perspective, within the theory of computable functionals. Key examples include Bézout’s identity, the fundamental theorem of arithmetic, and Fermat’s factorization method. All definitions and theorems are fully formalized in the proof assistant Minlog, laying the foundation for a comprehensive formal framework for number theory within Minlog. While formalization guarantees correctness, the primary emphasis is on the computational content of proofs. Leveraging Minlog’s built-in program extraction, we obtain executable terms that are exported as Haskell code. The efficiency of the extracted programs plays a central role. We show how performance considerations influence even the initial formulation of theorems and proofs. In particular, we compare formalizations based on binary encodings of natural numbers with those using the traditional unary (successor-based) representation. We present several core proofs in detail and reflect on the challenges that arise from formalization in contrast to informal reasoning. The complete formalization is available online and linked for reference. Minlog’s tactic scripts are designed to follow the structure of natural-language proofs, allowing each derivation step to be traced precisely and thus bridging the gap between formal and classical mathematical reasoning. Keywords: Proof assistants, Minlog, Theory of computational functionals, Program extraction, Program verification, Fundamental theorem of Arithmetic, Factorisation methods 1 Introduction 1.1 Novelties and Methodology of this Article This article is based on the formalization of statements from elementary arithmetic in Minlog. To date, Minlog has primarily been applied to the formalization of analysis. The only existing work addressing number theory in Minlog – specifically, the greatest common divisor – was carried out by Helmut Schwichtenberg and Ulrich Berger [ 9 ] . However, that study mainly focused on program extraction from classical proofs. Thus, the present work provides a solid foundation for the formalization of number theory within Minlog. Formalization offers several advantages compared to traditional textbook proofs, which we will explore and utilize throughout this article. Links to the Minlog implementation. The implementations underlying this article can be found in the folder examples/arith of the Minlog directory. Please note that, as of April 2025, the files are only available and functional in the dev branch of Minlog. Instructions on how to switch to the dev branch can be found on the Minlog website [ 25 ] . All relevant files are also available in a GitHub repository ( https://github.com/FranziskusWiesnet/MinlogArith/ ). For all definitions and theorems in this article, the corresponding name used in the Minlog file is provided in typewriter font . These notations additionally serve as hyperlinks to the precise line and file in the GitHub repository. When viewing the article in its original PDF format, clicking on any of these typewriter-font references will take the reader directly to the corresponding location in the Minlog code. Correctness of the statement. Formal implementation ensures the correctness of the presented theorems. This is particularly beneficial in cases involving numerous case distinctions, lengthy calculations, or subtle conditions for applying a lemma. In such situations, a textbook proof can often become difficult to follow and may unintentionally contain gaps. We will return to this advantage of formalization after presenting such complex proofs. Transparency of the proofs and definitions. Proofs constructed within a proof assistant are entirely transparent, allowing every logical step to be inspected. As with any textbook proof, we do not elaborate on every minor step in this article. However, if a particular part of a proof or definition is unclear, the reader can consult the corresponding formal implementation for clarification. One of the key advantages of Minlog is that its tactic scripts closely resemble textbook-style proofs. Moreover, large proofs are annotated and indented in the implementation to improve readability and facilitate comprehension. This article also highlights that formally conducted proofs can sometimes be significantly more intricate than one might expect based on their textbook counterparts. 1 1 1 At this point, it is also worth noting that some formal proofs turn out to be surprisingly trivial, particularly when the statement has been carefully formulated in advance. This added complexity is primarily due to the need for precise definitions and explicitly structured data types in formalization. This contrast becomes particularly salient in the context of natural versus binary representations of numbers. For instance, our formalization integrates structural properties of binary numbers into the proofs – an approach rarely taken in traditional mathematical texts, where numbers are typically treated as abstract objects. Generation of an extracted program. Minlog provides a mechanism to extract programs from proofs, as long as the proven theorem contains computational content. These programs are initially represented as terms in the language of the underlying theory. Minlog provides a built-in command to convert these terms into executable Haskell programs. Executing the extracted Haskell programs is considerably more efficient than running the corresponding terms within Minlog itself. The extracted Haskell files can also be found in the GitHub repository as gcd_pos.hs , fta_pos.hs , and factor_pos.hs . We will discuss the application of the Haskell files after presenting some theorems with computational content in this article. The corresponding tests and their results can also be found in the GitHub repository, in the files gcd_pos_text.txt , fta_pos_test.txt , and factor_pos_test.txt , respectively. Efficiency of proofs and extracted programs. This article does not define efficiency of proofs or programs formally, but rather discusses it informally. For our purposes, an efficient program is one that runs with reduced runtime, while an efficient proof is characterized by clarity and simplicity. Regardless of the exact definition of efficiency, we present two formalization approaches and compare their respective trade-offs. The first approach uses natural numbers, defined via zero and the successor function. This simple definition results in relatively straightforward proofs. However, this unary representation is inherently inefficient, as its length grows linearly with the number’s value. As a result, the runtime of many algorithms scales linearly with the number of successor operations, which becomes inefficient for large inputs. The second formalization uses positive binary numbers, represented with three constructors: 1, the 0-successor, and the 1-successor. This representation is far more efficient, since binary numbers are encoded and processed as lists of digits (0s and 1s). Consequently, algorithm runtimes scale often with the number of digits, which grows logarithmically with the numeric value. However, formalizing binary numbers introduces complexity, as it requires handling two distinct successor constructors. Moreover, for certain operations, such as bounded search from below, the binary representation offers no advantage over the unary representation of natural numbers. Therefore, we adopt a hybrid approach, leveraging the most suitable aspects of both representations, and motivate our choice of definitions based on their efficiency in specific contexts. Runtime analyses. In Haskell’s GHCi, the command :set +s enables timing statistics for executed expressions. After evaluating an expression, GHCi then displays the corresponding runtime and memory usage. This feature was used to measure the performance of the generated Haskell programs. The hardware used for testing has the following specifications: AMD RYZEN R7-4800U 1.8G~4.2G Turbo, 8C/16T Core, 12MB L3 Cache AMD Radeon GPU 1750Mhz 8 GB RAM While this system is on the lower end of modern computing hardware, it is fully sufficient for our applications. Since execution times naturally vary, runtime measurements provided in this article should be considered approximate. The Haskell source files are publicly available both in the Minlog files and in the GitHub repository, allowing for independent verification and further benchmarking. Before delving into the formalization, we will first introduce Minlog, its underlying theoretical framework, and provide references to relevant sources. 1.2 The Proof Assistant Minlog Minlog was developed in the 1990s by members of the logic group at the Ludwig-Maximilians-University in Munich under the direction of Helmut Schwichtenberg [ 36 , 37 ] . Installation instructions and documentation are available on the official Minlog website, hosted by Ludwig-Maximilians-University [ 25 ] . Furthermore, several introductions to Minlog are available [ 50 , 51 , 53 ] . Notable researchers who made significant contributions to Minlog include Ulrich Berger, Kenji Miyamoto, and Monika Seisenberger [ 7 , 24 , 26 ] . One of the first constructive works implemented in Minlog focused on the greatest common divisors of integers [ 9 ] , which is related to the topic of this article. Recently, Minlog has predominantly been employed in the field of constructive analysis [ 8 , 20 , 27 , 40 , 45 , 54 ] . However, a broad spectrum of proofs from various domains has already been implemented in Minlog [ 4 , 16 , 38 , 41 , 44 ] . A common trait among these implementations is Minlog’s dual emphasis on proof verification and program extraction. Minlog is implemented in the functional programming language Scheme. Minlog also supports exporting extracted programs to Haskell, via functions developed by Fredrik Nordvall-Forsberg. The correctness of a proof formalized in Minlog can be verified automatically through a built-in command. In simple cases, Minlog can even autonomously search for proofs. Minlog’s core philosophy is to interpret proofs as programs and to work with them accordingly [ 3 ] . Minlog provides all necessary tools for the formal extraction of programs from proofs. Furthermore, proofs can be normalized in Minlog. This process involves ensuring that proofs adhere to a standard or normalized form, enhancing their clarity and facilitating further analysis [ 6 ] . Terms in Minlog can also be transformed and evaluated. Transformations include standard \beta - and \eta -reduction of lambda expressions, as well as conversion rules for program constants. It is important to note that, due to the conversion rules for program constants, terms in Minlog do not necessarily have a unique normal form. In our setting, however, every term has a normal form and can be evaluated, as we work exclusively with total objects, which will be introduced below. 1.3 Theory of Computational Functionals Minlog is based on an extension of \textsf{HA}^{\omega} known as the Theory of Computable Functionals ( TCF ), which serves as its meta-theory. Its origins go back to Dana Scott’s seminal work on Logic of Computable Functionals [ 47 ] and Platek’s PhD thesis [ 31 ] . It also builds on fundamental ideas introduced by Kreisel [ 19 ] and Troelsta [ 49 ] . More recently, significant contributions to TCF have been made by the Munich group, including Helmut Schwichtenberg, Ulrich Berger, Wilfried Buchholz, Basil Karádais, and Iosif Petrakis [ 5 , 15 , 17 , 30 , 35 ] . It is built on partial continuous functionals and information systems, whose semantics are captured by the Scott model [ 21 , 46 ] . While we do not explore the underlying models of TCF in detail, we provide an overview of the aspects relevant to this article. For a comprehensive and formal introduction, we refer to [ 40 , 43 , 50 , 52 ] . The logical framework for TCF is the calculus of natural deduction [ 29 , 33 , 42 ] , where the implication \to and the universal quantifier \forall are the only logical symbols. Other standard logical connectives such as \wedge,\vee,\exists , and even the falsum F (at least the version we use), are introduced as inductively defined predicates. Consequently, TCF is a theory within minimal logic, omitting the law of excluded middle. The ex-falso axiom is also not necessary as it is a consequence from the axioms of TCF and the definition of F . 1.3.1 Terms and Types in TCF Terms in TCF are based on typed \lambda -calculus, meaning every term is assigned a type. Types in TCF are either type variables, function types, or algebras. Algebras can be seen as fixpoints of their constructors. For example, the type of natural numbers ( nat ) is defined as an algebra with the constructors 0:\mathbb{N} and \operatorname{S}:\mathbb{N}\to\mathbb{N} . In short notation, we express this as \mathbb{N}:=\mu_{\xi}(0:\xi,\operatorname{S}:\xi\to\xi). Positive binary numbers ( \mathtt{pos} ). Another important algebra we are dealing with in this article is the algebra of positive binary numbers \mathbb{P}:=\mu_{\xi}(1:\xi,\operatorname{S}_{0}:\xi\to\xi,\operatorname{S}_{1}:\xi\to\xi). The positive binary numbers have three constructors: the nullary constructor 1 and two successor functions \operatorname{S}_{0} and \operatorname{S}_{1} . The successor functions behave as if appending the corresponding digit to a positive number in its binary representation, in particular \operatorname{S}_{0}p=2\cdot p and \operatorname{S}_{1}p=2\cdot p+1 . Note that the representation using constructors is the reverse of the well-known binary representation, for example \operatorname{S}_{0}\operatorname{S}_{1}1 represents 6 which is 110 in binary representation. The reason for starting with 1 instead of 0 is primarily to ensure that each number is uniquely determined by its constructors. If we were to start with 0 , then for example 0 and \operatorname{S}_{0}0 would represent the same number, violating this uniqueness. This uniqueness is important to ensure that functions on positive numbers are automatically well-defined. However, as we will for example see in Theorem 2 , the absence of 0 introduces additional complexity in some cases. The third algebra we will use in this paper is Boolean algebra \mathbb{B} . It is simply defined by the two nullary constructors \operatorname{tt}:\mathbb{B} and \operatorname{ff}:\mathbb{B} . These three algebras form the basic types in this paper. Additionally, we will use function types over these three algebras. Since we do not want to explicitly specify the type every time we introduce a new variable, we will assign variables to a type based on their letters. This is also done in Minlog, and we follow the conventions of Minlog here, which is why some variables consist of two letters. Notation 1 . The following table shows the types assigned to each variable: w:\mathbb{B} l,m,n:\mathbb{N} p,q,r:\mathbb{P} ws:\mathbb{N}\to\mathbb{B} wf:\mathbb{P}\to\mathbb{B} ps,qs,rs:\mathbb{N}\to\mathbb{P} If other variables are used, their types are either irrelevant or will be specified explicitly. If we need multiple variables of the same type, we will assign them indices or other decorations, i.e. wf_{2}^{\prime} has also type \mathbb{P}\to\mathbb{B} . In addition to variables and constructors, so-called defined constants (also referred to as program constants or simply constants ) are also terms in TCF . These are defined by their type and computation rules. A simple program constant is the logarithm \operatorname{PosLog}:\mathbb{P}\to\mathbb{N} on the positive numbers, in Minlog PosLog . It essentially returns the number of digits in the binary representation minus one as a natural number. It is given by the following three computation rules \displaystyle\operatorname{PosLog}\ 1 \displaystyle:=0 \displaystyle\operatorname{PosLog}\ (\operatorname{S}_{0/1}p) \displaystyle:=\operatorname{S}(\operatorname{PosLog}\ p), where the last line represents two rules as \operatorname{S}_{0/1} shall be \operatorname{S}_{0} and \operatorname{S}_{1} . The basic arithmetic operations for both \mathbb{N} and \mathbb{P} are also defined as program constants through computation rules. There are also versions of the conjunction, disjunction and negation, that are given as program constants on Boolean algebra, \wedge^{b} , \vee^{\operatorname{b}} and \neg . For our purposes, these program constants behave the same as the corresponding logical connectives. However, formally, they are defined by the well-known computation rules. Conversion between natural numbers and positive binary numbers. Two important program constants are \operatorname{PosToNat}:\mathbb{P}\to\mathbb{N} and \operatorname{NatToPos}:\mathbb{N}\to\mathbb{P} . As their names suggest, they convert a positive number to a natural number and vice versa. Note that \operatorname{NatToPos}(0)=1 . Apart from this exception, the program constants behave as expected. While their precise definitions are somewhat more involved, they are not essential for our purposes here. We therefore refer the reader to the Minlog implementation for further details. In Minlog, the program constants PosToNat and NatToPos are essential and must always be used explicitly. In contrast, in Haskell the types nat and pos are identical. As a result, \operatorname{PosToNat} is simply the identity function, and \operatorname{NatToPos} is also the identity function, with the exception that 0 is mapped to 1 . In this article, we will use these two functions explicitly only when necessary for clarity; otherwise, we will leave them implicit. As already mentioned, many theorems come in two versions. To enhance readability, we will provide only the version for positive binary numbers whenever the alternative version is equivalent for our purposes. Note that a positive number p can also be understood as a natural number greater than 0 . For example, \forall_{p}A(p) can also be seen as \forall_{n}.\ 0\nu(wf,n) . Furthermore, these two properties are characteristic for \nu , i.e.: \displaystyle\forall_{p}.\ wf(p)\to\forall_{q}\left(p0}\,\gcd(n,m)=\operatorname{PosToNat}(\gcd(\operatorname{NatToPos}n,\operatorname{NatToPos}m)). Proof. It suffices to prove the first formula, as the second follows directly from it. To do so, we prove the equivalent statement: \displaystyle\forall_{n,p,q}.\ p+q