Hykilpikonna
230 lines
22 KiB
HTML
230 lines
22 KiB
HTML
<!DOCTYPE html>
|
||
<html xmlns="http://www.w3.org/1999/xhtml" lang="" xml:lang="">
|
||
<head>
|
||
<meta charset="utf-8" />
|
||
<meta name="generator" content="pandoc" />
|
||
<meta name="viewport" content="width=device-width, initial-scale=1.0, user-scalable=yes" />
|
||
<title>6.3 Proofs and Algorithms I: Primality Testing</title>
|
||
<style>
|
||
code{white-space: pre-wrap;}
|
||
span.smallcaps{font-variant: small-caps;}
|
||
span.underline{text-decoration: underline;}
|
||
div.column{display: inline-block; vertical-align: top; width: 50%;}
|
||
div.hanging-indent{margin-left: 1.5em; text-indent: -1.5em;}
|
||
ul.task-list{list-style: none;}
|
||
pre > code.sourceCode { white-space: pre; position: relative; }
|
||
pre > code.sourceCode > span { display: inline-block; line-height: 1.25; }
|
||
pre > code.sourceCode > span:empty { height: 1.2em; }
|
||
code.sourceCode > span { color: inherit; text-decoration: inherit; }
|
||
div.sourceCode { margin: 1em 0; }
|
||
pre.sourceCode { margin: 0; }
|
||
@media screen {
|
||
div.sourceCode { overflow: auto; }
|
||
}
|
||
@media print {
|
||
pre > code.sourceCode { white-space: pre-wrap; }
|
||
pre > code.sourceCode > span { text-indent: -5em; padding-left: 5em; }
|
||
}
|
||
pre.numberSource code
|
||
{ counter-reset: source-line 0; }
|
||
pre.numberSource code > span
|
||
{ position: relative; left: -4em; counter-increment: source-line; }
|
||
pre.numberSource code > span > a:first-child::before
|
||
{ content: counter(source-line);
|
||
position: relative; left: -1em; text-align: right; vertical-align: baseline;
|
||
border: none; display: inline-block;
|
||
-webkit-touch-callout: none; -webkit-user-select: none;
|
||
-khtml-user-select: none; -moz-user-select: none;
|
||
-ms-user-select: none; user-select: none;
|
||
padding: 0 4px; width: 4em;
|
||
color: #aaaaaa;
|
||
}
|
||
pre.numberSource { margin-left: 3em; border-left: 1px solid #aaaaaa; padding-left: 4px; }
|
||
div.sourceCode
|
||
{ }
|
||
@media screen {
|
||
pre > code.sourceCode > span > a:first-child::before { text-decoration: underline; }
|
||
}
|
||
code span.al { color: #ff0000; font-weight: bold; } /* Alert */
|
||
code span.an { color: #60a0b0; font-weight: bold; font-style: italic; } /* Annotation */
|
||
code span.at { color: #7d9029; } /* Attribute */
|
||
code span.bn { color: #40a070; } /* BaseN */
|
||
code span.bu { } /* BuiltIn */
|
||
code span.cf { color: #007020; font-weight: bold; } /* ControlFlow */
|
||
code span.ch { color: #4070a0; } /* Char */
|
||
code span.cn { color: #880000; } /* Constant */
|
||
code span.co { color: #60a0b0; font-style: italic; } /* Comment */
|
||
code span.cv { color: #60a0b0; font-weight: bold; font-style: italic; } /* CommentVar */
|
||
code span.do { color: #ba2121; font-style: italic; } /* Documentation */
|
||
code span.dt { color: #902000; } /* DataType */
|
||
code span.dv { color: #40a070; } /* DecVal */
|
||
code span.er { color: #ff0000; font-weight: bold; } /* Error */
|
||
code span.ex { } /* Extension */
|
||
code span.fl { color: #40a070; } /* Float */
|
||
code span.fu { color: #06287e; } /* Function */
|
||
code span.im { } /* Import */
|
||
code span.in { color: #60a0b0; font-weight: bold; font-style: italic; } /* Information */
|
||
code span.kw { color: #007020; font-weight: bold; } /* Keyword */
|
||
code span.op { color: #666666; } /* Operator */
|
||
code span.ot { color: #007020; } /* Other */
|
||
code span.pp { color: #bc7a00; } /* Preprocessor */
|
||
code span.sc { color: #4070a0; } /* SpecialChar */
|
||
code span.ss { color: #bb6688; } /* SpecialString */
|
||
code span.st { color: #4070a0; } /* String */
|
||
code span.va { color: #19177c; } /* Variable */
|
||
code span.vs { color: #4070a0; } /* VerbatimString */
|
||
code span.wa { color: #60a0b0; font-weight: bold; font-style: italic; } /* Warning */
|
||
</style>
|
||
<link rel="stylesheet" href="../tufte.css" />
|
||
<script src="https://cdn.jsdelivr.net/npm/mathjax@3/es5/tex-mml-chtml.js" type="text/javascript"></script>
|
||
<!--[if lt IE 9]>
|
||
<script src="//cdnjs.cloudflare.com/ajax/libs/html5shiv/3.7.3/html5shiv-printshiv.min.js"></script>
|
||
<![endif]-->
|
||
</head>
|
||
<body>
|
||
<div style="display:none">
|
||
\(
|
||
\newcommand{\NOT}{\neg}
|
||
\newcommand{\AND}{\wedge}
|
||
\newcommand{\OR}{\vee}
|
||
\newcommand{\XOR}{\oplus}
|
||
\newcommand{\IMP}{\Rightarrow}
|
||
\newcommand{\IFF}{\Leftrightarrow}
|
||
\newcommand{\TRUE}{\text{True}\xspace}
|
||
\newcommand{\FALSE}{\text{False}\xspace}
|
||
\newcommand{\IN}{\,{\in}\,}
|
||
\newcommand{\NOTIN}{\,{\notin}\,}
|
||
\newcommand{\TO}{\rightarrow}
|
||
\newcommand{\DIV}{\mid}
|
||
\newcommand{\NDIV}{\nmid}
|
||
\newcommand{\MOD}[1]{\pmod{#1}}
|
||
\newcommand{\MODS}[1]{\ (\text{mod}\ #1)}
|
||
\newcommand{\N}{\mathbb N}
|
||
\newcommand{\Z}{\mathbb Z}
|
||
\newcommand{\Q}{\mathbb Q}
|
||
\newcommand{\R}{\mathbb R}
|
||
\newcommand{\C}{\mathbb C}
|
||
\newcommand{\cA}{\mathcal A}
|
||
\newcommand{\cB}{\mathcal B}
|
||
\newcommand{\cC}{\mathcal C}
|
||
\newcommand{\cD}{\mathcal D}
|
||
\newcommand{\cE}{\mathcal E}
|
||
\newcommand{\cF}{\mathcal F}
|
||
\newcommand{\cG}{\mathcal G}
|
||
\newcommand{\cH}{\mathcal H}
|
||
\newcommand{\cI}{\mathcal I}
|
||
\newcommand{\cJ}{\mathcal J}
|
||
\newcommand{\cL}{\mathcal L}
|
||
\newcommand{\cK}{\mathcal K}
|
||
\newcommand{\cN}{\mathcal N}
|
||
\newcommand{\cO}{\mathcal O}
|
||
\newcommand{\cP}{\mathcal P}
|
||
\newcommand{\cQ}{\mathcal Q}
|
||
\newcommand{\cS}{\mathcal S}
|
||
\newcommand{\cT}{\mathcal T}
|
||
\newcommand{\cV}{\mathcal V}
|
||
\newcommand{\cW}{\mathcal W}
|
||
\newcommand{\cZ}{\mathcal Z}
|
||
\newcommand{\emp}{\emptyset}
|
||
\newcommand{\bs}{\backslash}
|
||
\newcommand{\floor}[1]{\left \lfloor #1 \right \rfloor}
|
||
\newcommand{\ceil}[1]{\left \lceil #1 \right \rceil}
|
||
\newcommand{\abs}[1]{\left | #1 \right |}
|
||
\newcommand{\xspace}{}
|
||
\newcommand{\proofheader}[1]{\underline{\textbf{#1}}}
|
||
\)
|
||
</div>
|
||
<header id="title-block-header">
|
||
<h1 class="title">6.3 Proofs and Algorithms I: Primality Testing</h1>
|
||
</header>
|
||
<section>
|
||
<p>Now let’s see an example of applying the concept of mathematical proof to justify the correctness of an algorithm. First, recall that we say that an integer <span class="math inline">\(p\)</span> is <em>prime</em> when it is greater than 1 and the only numbers that divide <span class="math inline">\(p\)</span> are 1 and <span class="math inline">\(p\)</span> itself. We saw earlier that we could implement a predicate in Python to determine whether <code>p</code> is prime:</p>
|
||
<div class="sourceCode" id="cb1"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb1-1"><a href="#cb1-1"></a><span class="kw">def</span> is_prime(p: <span class="bu">int</span>) <span class="op">-></span> <span class="bu">bool</span>:</span>
|
||
<span id="cb1-2"><a href="#cb1-2"></a> <span class="co">"""Return whether p is prime."""</span></span>
|
||
<span id="cb1-3"><a href="#cb1-3"></a> possible_divisors <span class="op">=</span> <span class="bu">range</span>(<span class="dv">0</span>, p <span class="op">+</span> <span class="dv">1</span>)</span>
|
||
<span id="cb1-4"><a href="#cb1-4"></a> <span class="cf">return</span> (</span>
|
||
<span id="cb1-5"><a href="#cb1-5"></a> p <span class="op">></span> <span class="dv">1</span> <span class="kw">and</span></span>
|
||
<span id="cb1-6"><a href="#cb1-6"></a> <span class="bu">all</span>({d <span class="op">==</span> <span class="dv">1</span> <span class="kw">or</span> d <span class="op">==</span> p <span class="cf">for</span> d <span class="kw">in</span> possible_divisors <span class="cf">if</span> divides(d, p)})</span>
|
||
<span id="cb1-7"><a href="#cb1-7"></a> )</span></code></pre></div>
|
||
<p>This implementation is a direct translation of the mathematical definition of prime numbers, with the only difference being our restriction of the range of possible divisors.<label for="sn-0" class="margin-toggle sidenote-number"></label><input type="checkbox" id="sn-0" class="margin-toggle"/><span class="sidenote"> In fact, we can justify that this range is correct in a separate proof!</span> However, you might have noticed that this algorithm is “inefficient” because it checks more numbers than necessary.</p>
|
||
<p>Often when this version of <code>is_prime</code> is taught, the range of possible divisors extends only to the square root of the input <code>p</code>:</p>
|
||
<div class="sourceCode" id="cb2"><pre class="sourceCode python"><code class="sourceCode python"><span id="cb2-1"><a href="#cb2-1"></a><span class="im">from</span> math <span class="im">import</span> floor, sqrt</span>
|
||
<span id="cb2-2"><a href="#cb2-2"></a></span>
|
||
<span id="cb2-3"><a href="#cb2-3"></a></span>
|
||
<span id="cb2-4"><a href="#cb2-4"></a><span class="kw">def</span> is_prime(p: <span class="bu">int</span>) <span class="op">-></span> <span class="bu">bool</span>:</span>
|
||
<span id="cb2-5"><a href="#cb2-5"></a> <span class="co">"""Return whether p is prime."""</span></span>
|
||
<span id="cb2-6"><a href="#cb2-6"></a> possible_divisors <span class="op">=</span> <span class="bu">range</span>(<span class="dv">2</span>, floor(sqrt(p)) <span class="op">+</span> <span class="dv">1</span>)</span>
|
||
<span id="cb2-7"><a href="#cb2-7"></a> <span class="cf">return</span> (</span>
|
||
<span id="cb2-8"><a href="#cb2-8"></a> p <span class="op">></span> <span class="dv">1</span> <span class="kw">and</span></span>
|
||
<span id="cb2-9"><a href="#cb2-9"></a> <span class="bu">all</span>({<span class="kw">not</span> divides(d, p) <span class="cf">for</span> d <span class="kw">in</span> possible_divisors})</span>
|
||
<span id="cb2-10"><a href="#cb2-10"></a> )</span></code></pre></div>
|
||
<p>This version is intuitively faster, as the range of possible divisors to check is smaller. But how do we actually know that this version of <code>is_prime</code> is correct? We could write some tests, but as we discussed earlier both unit tests and property-based tests do not guarantee absolute correctness, they just give confidence. Luckily, for algorithms like this one that are based on the mathematical properties of the input, we do have a tool that guarantees absolutely certainty: proofs!</p>
|
||
<h2 id="a-property-of-prime-numbers">A property of prime numbers</h2>
|
||
<p>Formally, we can justify the correctness by formally proving the following statement.</p>
|
||
<div class="theorem">
|
||
<p>Let <span class="math inline">\(p \in \Z\)</span>. Then <span class="math inline">\(p\)</span> is prime if and only if <span class="math inline">\(p > 1\)</span> and for every integer <span class="math inline">\(d\)</span> in the range <span class="math inline">\(2 \leq d \leq \sqrt{p}\)</span>, <span class="math inline">\(d\)</span> does not divide <span class="math inline">\(p\)</span>.</p>
|
||
<p>Or, translated into predicate logic: <span class="math display">\[\forall p \in \Z,~ \mathit{Prime}(p) \Leftrightarrow \big(p > 1 \land (\forall d \in \N,~ 2 \leq d \leq \sqrt{p} \Rightarrow d \nmid p) \big).\]</span></p>
|
||
</div>
|
||
<p>How do we go about proving that this statement is correct? We’ve seen in the past how to prove implications, but how about biconditionals? Recall that a biconditional <span class="math inline">\(p \Leftrightarrow q\)</span> is equivalent to <span class="math inline">\((p \Rightarrow q) \land (q \Rightarrow p)\)</span>. So if we want to argue that a biconditional is True, we do so by proving the two different implications.</p>
|
||
<div class="framed">
|
||
<p><strong>A typical proof of a biconditional.</strong></p>
|
||
<p>Given statement to prove: <span class="math inline">\(p \Leftrightarrow q\)</span>.</p>
|
||
<div class="proof">
|
||
<p>This proof is divided into two parts.</p>
|
||
<p><strong>Part 1</strong> (<span class="math inline">\(p \Rightarrow q\)</span>): Assume <span class="math inline">\(p\)</span>.</p>
|
||
<p>[Proof that <span class="math inline">\(q\)</span> is True.]</p>
|
||
<p><strong>Part 2</strong> (<span class="math inline">\(q \Rightarrow p\)</span>): Assume <span class="math inline">\(q\)</span>.</p>
|
||
<p>[Proof that <span class="math inline">\(p\)</span> is True.]</p>
|
||
</div>
|
||
</div>
|
||
<h3 id="proving-the-first-implication">Proving the first implication</h3>
|
||
<div class="discussion">
|
||
<p>The first implication we’ll prove is that if <span class="math inline">\(p\)</span> is prime, then <span class="math inline">\(p > 1\)</span> and <span class="math inline">\(\forall d \in \N,~ 2 \leq d \leq \sqrt{p} \Rightarrow d \nmid p\)</span>. We get to assume that <span class="math inline">\(p\)</span> is prime, and will need to prove two things: that <span class="math inline">\(p > 1\)</span>, and that <span class="math inline">\(\forall d \in \N,~ 2 \leq d \leq \sqrt{p} \Rightarrow d \nmid p\)</span>.</p>
|
||
<p>Let’s remind ourselves what the definition of prime is in predicate logic:</p>
|
||
<p><span class="math display">\[\mathit{Prime}(p):~ p > 1 \land \big(\forall d \in \N,~ d \mid p \Rightarrow d = 1 \lor d = p \big)\]</span></p>
|
||
<p>The first part comes straight from the definition of prime. For the second part, we should also be able to use the definition of prime: if <span class="math inline">\(d\)</span> is between 2 and <span class="math inline">\(\sqrt{p}\)</span>, then it can’t equal 1 or <span class="math inline">\(p\)</span>, which are the only possible divisors of <span class="math inline">\(p\)</span>.</p>
|
||
<p>Let’s see how to write this up formally.</p>
|
||
</div>
|
||
<div class="proof">
|
||
<p>Let <span class="math inline">\(p \in \Z\)</span> and assume that <span class="math inline">\(p\)</span> is prime. We need to prove that <span class="math inline">\(p > 1\)</span> and for all <span class="math inline">\(d \in \N\)</span>, if <span class="math inline">\(2 \leq d \leq \sqrt p\)</span> then <span class="math inline">\(d\)</span> does not divide <span class="math inline">\(p\)</span>.</p>
|
||
<p><strong>Part 1</strong>: proving that <span class="math inline">\(p > 1\)</span>.</p>
|
||
<p>By the definition of prime, we know that <span class="math inline">\(p > 1\)</span>.</p>
|
||
<p><strong>Part 2</strong>: proving that for all <span class="math inline">\(d \in \N\)</span>, if <span class="math inline">\(2 \leq d \leq \sqrt p\)</span> then <span class="math inline">\(d\)</span> does not divide <span class="math inline">\(p\)</span>.</p>
|
||
<p>Let <span class="math inline">\(d \in \N\)</span> and assume <span class="math inline">\(2 \leq d \leq \sqrt p\)</span>. We’ll prove that <span class="math inline">\(d\)</span> does not divide <span class="math inline">\(p\)</span>.</p>
|
||
<p>First, since <span class="math inline">\(2 \leq d\)</span>, we know <span class="math inline">\(d > 1\)</span>, and so <span class="math inline">\(d \neq 1\)</span>. Second, since <span class="math inline">\(p > 1\)</span>, we know that <span class="math inline">\(\sqrt p < p\)</span>, and so <span class="math inline">\(d \leq \sqrt p < p\)</span>.</p>
|
||
<p>This means that <span class="math inline">\(d \neq 1\)</span> and <span class="math inline">\(d \neq p\)</span>. By the definition of prime again, we can conclude that <span class="math inline">\(d \nmid p\)</span>.</p>
|
||
</div>
|
||
<p>What we’ve proved so far is that if <span class="math inline">\(p\)</span> is prime, then it has no divisors between 2 and <span class="math inline">\(\sqrt p\)</span>. How does this apply to our algorithm <code>is_prime</code>? When its input <code>p</code> is a prime number, we know that the expressions <code>p > 1</code> and <code>all(not divides(d, p) for d in possible_divisors)</code> will both evaluate to <code>True</code>, and so the function will return <code>True</code>. In other words, we’ve proven that <code>is_prime</code> returns the correct value for <em>every</em> prime number, without a single test case! Pretty awesome.</p>
|
||
<h3 id="proving-the-second-implication">Proving the second implication</h3>
|
||
<p>Though we know that <code>is_prime</code> is correct for prime numbers, we’ve said nothing at all about how it behaves when given a non-prime number. To prove that its behaviour is correct in this case as well, we need to prove the other conditional.</p>
|
||
<div class="discussion">
|
||
<p>We now need to prove the second implication, which is the converse of the first: if <span class="math inline">\(p > 1\)</span> and <span class="math inline">\(\forall d \in \N,~ 2 \leq d \leq \sqrt{p} \Rightarrow d \nmid p\)</span>, then <span class="math inline">\(p\)</span> must be prime. Expanding the definition of prime, we need to prove that <span class="math inline">\(p > 1\)</span> (which we’ve assumed!) and that for all <span class="math inline">\(d_1 \in \N,~ d_1 \mid p \Rightarrow d_1 = 1 \lor d_1 = p\)</span>.</p>
|
||
<p>So the idea here is to let <span class="math inline">\(d_1 \in \N\)</span> and assume <span class="math inline">\(d_1 \mid p\)</span>, and use the condition that <span class="math inline">\(\forall d \in \N,~ 2 \leq d \leq \sqrt{p} \Rightarrow d \nmid p\)</span> to prove that <span class="math inline">\(d_1\)</span> is 1 or <span class="math inline">\(p\)</span>.</p>
|
||
</div>
|
||
<div class="proof">
|
||
<p>Let <span class="math inline">\(p \in \N\)</span>, and assume <span class="math inline">\(p > 1\)</span> and that <span class="math inline">\(\forall d \in \N,~ 2 \leq d \leq \sqrt{p} \Rightarrow d \nmid p\)</span>. We want to prove that <span class="math inline">\(p\)</span> is prime, i.e., that <span class="math inline">\(p > 1\)</span> and that <span class="math inline">\(\forall d_1 \in \N,~ d_1 \mid p \Rightarrow d_1 = 1 \lor d_1 = p\)</span>.</p>
|
||
<p>We know the first part (<span class="math inline">\(p > 1\)</span>) is true because it’s one of our assumptions. For the second part, first let <span class="math inline">\(d_1 \in \N\)</span>, and assume <span class="math inline">\(d_1 \mid p\)</span>. We’ll prove that <span class="math inline">\(d_1 = 1 \lor d_1 = p\)</span>.</p>
|
||
<p>From our second assumption, we know that since <span class="math inline">\(d_1 \mid p\)</span>, it is not between 2 and <span class="math inline">\(\sqrt p\)</span>.<label for="sn-1" class="margin-toggle sidenote-number"></label><input type="checkbox" id="sn-1" class="margin-toggle"/><span class="sidenote"> More precisely, the <em>contrapositive</em> of our second assumption says that for all <span class="math inline">\(d \in \N\)</span>, <span class="math inline">\(d \mid p \Rightarrow d < 2 \lor d > \sqrt p\)</span>.</span> So then either <span class="math inline">\(d_1 < 2\)</span> or <span class="math inline">\(d_1 > \sqrt p\)</span>. We divide our proof into two <strong>cases</strong> based on these possibilities.</p>
|
||
<p><strong>Case 1</strong>: assume <span class="math inline">\(d_1 < 2\)</span>.</p>
|
||
<p>Since <span class="math inline">\(d_1 \in \N\)</span>, it must be 0 or 1 in this case. We know <span class="math inline">\(0 \nmid p\)</span> because <span class="math inline">\(p > 1\)</span>, and so <span class="math inline">\(d_1 = 1\)</span>.</p>
|
||
<p><strong>Case 2</strong>: assume <span class="math inline">\(d_1 > \sqrt p\)</span>.</p>
|
||
<p>Since we assumed <span class="math inline">\(d_1 \mid p\)</span>, we expand the definition of divisibility to conclude that <span class="math inline">\(\exists k \in \Z,~ p = d_1 k\)</span>. Since <span class="math inline">\(d_1 > \sqrt p\)</span> in this case, we know that <span class="math inline">\(k = \frac{p}{d_1} < \frac{p}{\sqrt{p}} = \sqrt{p}\)</span>.</p>
|
||
<p>Since <span class="math inline">\(p = d_1k\)</span>, we know that <span class="math inline">\(k \mid p\)</span> as well, and so our second assumption applied to <span class="math inline">\(k\)</span> tells us that <span class="math inline">\(k\)</span> is not between 2 and <span class="math inline">\(\sqrt p\)</span>.</p>
|
||
<p>So <span class="math inline">\(k < \sqrt{p}\)</span> and is not between 2 and <span class="math inline">\(\sqrt p\)</span>. Therefore <span class="math inline">\(k = 1\)</span>, and so <span class="math inline">\(d_1 = \frac{p}{k} = p\)</span>.</p>
|
||
</div>
|
||
<p>To wrap up this example, let’s see how this implication connects to our function <code>is_prime</code>. What we’ve proved is that if <code>is_prime(p)</code> returns <code>True</code>, then <code>p</code> must be prime. This sounds very similar to what we said in the previous section, but it is different! The contrapositive this statement here is useful: if <code>p</code> is NOT prime, then <code>is_prime(p)</code> returns <code>False</code>.</p>
|
||
<p>So putting the two implications together, we have:</p>
|
||
<ul>
|
||
<li>For all integers <code>p</code>, if <code>p</code> is prime then <code>is_prime(p)</code> returns <code>True</code>.</li>
|
||
<li>For all integers <code>p</code>, if <code>is_prime(p)</code> returns <code>True</code> then <code>p</code> is prime.<label for="sn-2" class="margin-toggle sidenote-number"></label><input type="checkbox" id="sn-2" class="margin-toggle"/><span class="sidenote"> Or equivalently, if <code>p</code> is not prime then <code>is_prime(p)</code> returns <code>False</code>.</span></li>
|
||
</ul>
|
||
<p>Since every integer <code>p</code> is either prime or not prime, we can conclude that this implementation of <code>is_prime</code> is <strong>correct</strong> according to its specification.</p>
|
||
<h2 id="algorithm-correctness-and-theoretical-properties">Algorithm correctness and theoretical properties</h2>
|
||
<p>Notice the duality between the statement of correctness for <code>is_prime</code> and the biconditional we had set out to prove: for every natural number <span class="math inline">\(p\)</span>, <span class="math inline">\(p\)</span> is prime if and only if <span class="math inline">\(p > 1\)</span> and for every integer <span class="math inline">\(d\)</span> in the range <span class="math inline">\(2 \leq d \leq \sqrt{p}\)</span>, <span class="math inline">\(d \nmid p\)</span>. The correctness of our <em>algorithm</em> is derived from the <em>theoretical properties of prime numbers</em> that we expressed in formal predicate logic. We admit this is a relatively simple example of this connection between algorithm and mathematical theory, but we had to start somewhere! Our future examples will draw on connections like this, but in far deeper ways.</p>
|
||
</section>
|
||
<footer>
|
||
<a href="https://www.teach.cs.toronto.edu/~csc110y/fall/notes/">CSC110 Course Notes Home</a>
|
||
</footer>
|
||
</body>
|
||
</html>
|