tag:blogger.com,1999:blog-19847492389000012602024-03-08T05:52:31.158-08:00All About PrimesLarry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.comBlogger16125tag:blogger.com,1999:blog-1984749238900001260.post-57661315887329713142021-04-12T00:31:00.001-07:002021-04-12T00:31:38.649-07:00Solution to the Depressed Cubic Equation<p><b>Theorem 9</b>: Depressed Cubic Equation</p><p>If $x^3 + bx = c$, then:</p><p>$$x = \sqrt[3]{\frac{c}{2} + \sqrt{\dfrac{c^2}{4} + \frac{b^3}{27}}} + \sqrt[3]{\frac{c}{2} - \sqrt{\dfrac{c^2}{4} + \frac{b^3}{27}}}$$</p><p>Proof:</p><p>(1) $x^3 = -bx + c$</p><p>(2) There exists real numbers $u,v$ such that $x = u + v$</p><p>(3) $(u+v)^3 = u^3 + 3u^2v + 3uv^2 + v^3 = 3uv(u+v) + (u^3 + v^3)$</p><p>(4) Since $b = -3uv$, it follows that $v = \dfrac{-b}{3u}$</p><p>(5) $c = u^3 + v^3 = u^3 + \dfrac{-b^3}{27u^3}$</p><p>(6) It follows that:</p><p>$$u^6 - u^3c + \dfrac{-b^3}{27}= 0$$</p><p>(7) Using the <a href="https://allaboutprimes.blogspot.com/2021/04/quadratic-equation.html" target="_blank">solution</a> for the quadratic equation, we have:</p><p>$$u^3 = \frac{c \pm \sqrt{c^2 + \frac{4b^3}{27}}}{2} = \frac{c}{2} \pm \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}$$</p><p>(8) From the symmetry of the equation, we can assume that:</p><p>$$u^3 = \frac{c}{2} + \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}$$</p><p>$$v^3 = c - u^3 = c - \frac{c}{2} - \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3} = \frac{c}{2} - \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}$$</p><p>(9) $x = u + v = \sqrt[3]{\frac{c}{2} + \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}} + \sqrt[3]{\frac{c}{2} - \sqrt{\left(\frac{c}{2}\right)^2 + \left(\frac{b}{3}\right)^3}}$</p><p><br /></p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-17691712980833757522021-04-11T23:29:00.002-07:002021-04-12T00:10:00.149-07:00Solution to the Quadratic Equation<p><b>Theorem 8</b>: If $ax^2 + bx + c=0$, then:</p><p>$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$</p><p>Proof:</p><p>(1) $x^2 + \dfrac{bx}{a} + \dfrac{c}{a} = 0$</p><p>(2) $x^2 + \dfrac{bx}{a} = -\dfrac{c}{a}$</p><p>(3) $x^2 + \dfrac{bx}{a} + \left(\dfrac{b}{2a}\right)^2 = -\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2$</p><p>(4) $\left(x + \dfrac{b}{2a}\right)^2 = -\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2$</p><p>(5) $x + \dfrac{b}{2a} = \pm \sqrt{-\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2}$</p><p>(6) $x = -\dfrac{b}{2a} \pm \sqrt{-\dfrac{c}{a} + \left(\dfrac{b}{2a}\right)^2} = \dfrac{-b \pm \sqrt{b^2 - 4ac}}{2a}$</p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-38742979265004624502021-04-10T10:21:00.003-07:002021-04-10T10:23:59.279-07:00The Square Root of 2 is irrational<p><b>Theorem 7</b>: The Square Root of $2$ cannot be represented by the ratio of two integers</p><p>Proof:</p><p>(1) Assume that the squre root of $2$ could be represented by a ratio of two integers with $a$ and $b$ the reduced form.</p><p>$$\frac{a}{b} = \sqrt{2}$$ </p><p>(2) Squaring both sides:</p><p>$$a^2 = 2b^2$$</p><p>(3) Since $a$ must be even, there exists $c$ such that $a=2c$ and:</p><p>$$a^2 = (2c)^2 = 4c^2 = 2b^2$$</p><p>(4) It follows that $b$ must be even since:</p><p>$$2c^2 = b^2$$</p><p>(5) Then there exists $d$ such that $b=2d$ and:</p><p>$$\sqrt{2} = \frac{2c}{2d} = \frac{c}{d}$$</p><p>(6) But then we have a contradiction since $a$ and $b$ can be reduced to $c$ and $d$.</p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-12733492456957605532021-04-09T18:32:00.003-07:002021-04-10T09:46:21.761-07:00Infinitude of Prime Numbers<p><b>Theorem 6</b>: Infinitude of Prime Numbers</p><p>There are an infinite number of prime numbers.</p><p>Proof:</p><p>(1) Assume that there is a a finite number of primes. </p><p>(2) Let $P$ be the product of all primes.</p><p>(3) Let $q = P+1$</p><p>(4) By the Fundamental Theorem of Arithmetic, either $q$ is prime or $q$ is a product of primes.</p><p>(5) If $q$ is prime, then $q | (P + 1) - P = 1$ which s impossible.</p><p>(6) If $r$ is a prime that divides $q$, then we have the same problem since $r | (P + 1) - P = 1$</p><p><br /></p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-68888161120513468002021-04-09T09:19:00.002-07:002021-04-09T09:20:58.367-07:00Fundamental Theorem of Arithmetic<b>Theorem 5</b>: The Fundamental Theorem of Arithmetic<div><br /></div><div>Every integer greater than $1$ is either prime or can be represented as the unique product of powers of prime numbers.</div><div><br /></div><div>Proof:</div><div><br /></div><div>(1) First, prove existence. It is true for the base case where $n=2$ since $2$ is a prime.</div><div><br /></div><div>(2) Assume that it is true for all $i$ with $i \le n$</div><div><br /></div><div>(3) For $n+1$, if $n+1$ is prime, then it is true. If $n+1$ is not prime, then there exists integers $a,b$ such that $n+1 = ab$ with $a \le n$ and $b \le n$. Since $a \le n$ and $b \le n$, they can be represented by a prime or a product of primes with $a=p_1p_2\dots{p_n}$ and $b=q_1q_2\dots{q_n}$</div><div><br /></div><div>(4) Then $n+1 = ab = p_1p_2\dots{p_n}q_1q_2\dots{q_n}$ which means that $n+1$ can be represented as a product of powers of prime numbers.</div><div><br /></div><div>(5) Assume that there is an integer that has two different product of powers of prime numbers.</div><div><br /></div><div>(6) Let $y$ be the least integer where this is true so that $y = p_1p_2\dots{p_m} = q_1q_2\dots{q_n}$ with $p_1\dots{p_m}$ and $q_1\dots{q_n}$.</div><div><br /></div><div>(7) From Euclid's Generalized Lemma, $p_1$ divides $q_i$ where $1 \le i \le n$. But, then $\frac{y}{p_1} = p_2\dots{p_m} = \frac{q_1q_2\dots{q_n}}{p_1}$ which is smaller than $n$ and contradicts our assumption in step(6).</div>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-27958288359530165012021-04-09T04:43:00.003-07:002021-04-09T09:12:23.601-07:00Euclid's Lemma<p><b>Theorem 4:</b> Euclid's Lemma</p><p>If a prime $p$ divides the product $ab$ of two integers $a$ and $b$, then $p$ divides $a$ or $p$ divides $b$</p><p>Proof:</p><p>(1) Assume that $p | ab$ but $p \nmid a$</p><p>(2) From <a href="https://allaboutprimes.blogspot.com/2021/04/bezouts-identity.html" target="_blank">Bezout's Identity</a>, there exists $r,s$ such that $rp + sa = 1$</p><p>(3) Multiply both sides by $b$ to get: $rpb + sab = b$</p><p>(4) Since $p | ab$, it follows that $p | b$</p><p><br /></p><p><b>Corollary 4.1</b>: Euclid's Generalized Lemma</p><p>If a prime $p$ divides $a_1a_2\dots{a_m}$, then $p$ divides $a_i$ where $1 \le i \le m$</p><p>Proof:</p><p>(1) Base Case: The base case is Euclid's Lemma. If $p | a_1a_2$, then $p | a_1$ or $p | a_2$</p><p>(2) Assume that up to $n$ if $p | a_1a_2\dots{a_n}$, then $p|a_i$ with $1 \le i \le n$</p><p>(3) Let $b = a_1a_2\dots{a_n}$. </p><p>(4) Inductive Case: From Euclid's Lemma, if $p | ba_{n+1}$, then $p | b$ or $p|a_{n+1}$.</p><p><br /></p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-49576033674081864002021-04-09T04:32:00.003-07:002021-04-09T04:33:12.095-07:00Bezout's Identity<b>Theorem 3</b>: Bezout's Identity<div><br /></div><div>Let $a$ and $b$ be nonzero integers with greatest common divisor $d$. Then, there exists integers $x$ and $y$ such that $ax + by = d$.</div><div><br /></div><div>Proof:</div><div><br /></div><div>(1) For integers $a,b$ let $S$ be a set that includes all $ax+by$ where $ax + by > 0$</div><div><br /></div><div>(2) The set is non-empty since it contains either $a$ or $-a$ where $y=0$ and $x=1$ or $x=-1$</div><div><br /></div><div>(3) By the <a href="https://allaboutprimes.blogspot.com/2021/04/well-ordering-principle.html" target="_blank">Well-Ordering Principle</a>, $S$ has a minimal element $as + bt$ and let $d = as+bt$</div><div><br /></div><div>(4) Using <a href="https://allaboutprimes.blogspot.com/2021/04/euclids-division-lemma.html" target="_blank">Euclid's Divsion Lemma</a>, there exists $q_1, q_2, r_1, r_2$ such that:</div><div><ul style="text-align: left;"><li>$a = q_1d + r_1$</li><li>$b = q_2d + r_2$</li></ul><div>(5) It follows that:</div></div><div><ul style="text-align: left;"><li>$r_1 = a - q_1d = a - q_1(as + bt) = a(1 - q_1s) + b(-q_1t)$ which must equal $0$ since $r_1 < d$ but $d$ is the least element in $S$. The same argument applies to $r_2$ so that $r_2 = 0$</li></ul><div>(6) Then, $d$ divides both $a$ and $b$.</div></div><div><br /></div><div>(7) Let $c$ be any common divisor of $a$ and $b$ such that $a =cu$ and $b = cv$</div><div><br /></div><div>(8) $d = as + bt = cus + cvt = c(us + vt)$ so that it follows that $c$ divides $d$ and further that $c \le d$</div>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-34514877899955668692021-04-09T03:31:00.006-07:002021-04-09T03:43:53.088-07:00Euclid's Division Lemma<p><b>Theorem 2:</b> Euclid's Division Lemma</p><p>Given two integers $a$ and $b$ with $b \ne 0$, there exist unique integers $q$ and $r$ such that:</p><p></p><ul style="text-align: left;"><li>$a = bq+r$</li><li>$0 \le r < |b|$</li></ul><p></p><p>Note: Where $|b|$ is the <a href="https://en.wikipedia.org/wiki/Absolute_value" target="_blank">absolute value</a> of $b$.</p><p><br /></p><p>Proof:</p><p>(1) Case 1: $a \ge 0$</p><p>(2) Let $S$ be the set of all integers $a - bk$ where $k$ is an integer and $a - bk \ge 0$</p><p>(3) $S$ is non-empty since either $a = a - b\times0 \ge 0$ which is in $S$</p><p>(4) By the <a href="https://allaboutprimes.blogspot.com/2021/04/well-ordering-principle.html" target="_blank">Well-Ordering Principle</a>, there exists an integer $q$ such that $a - bq$ is the least element in $S$</p><p>(5) Let $r = a - bq$. $0 \le r$ by definition of $S$. Further $r < b$ since if $r \ge b$, then it is not the least element since $r - b = a - bq - b = a - b(q+1) \ge 0$ would be less than $r$ and an element in $S$.</p><p>(6) $r,q$ must be unique. Assume that there exists $r', q'$ such that $a = qb + r = q'b + r'$ and $|r - r'| > 0$ and $|q - q'| > 0$. Then, $b > |r - r'| = b|q - q'| > b$ which is impossible.</p><p>(7) Case 2: $a < 0$ In this case, let $a' = -a$. It now follows that $a' \ge 0$ and there exists unique $r,q$. It now follows that $a = -(bq +r) = b(-q) -r$ If $r > 0$, then $a = b(-q+1) + (b-r)$ with $0 < b-r < b$</p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com1tag:blogger.com,1999:blog-1984749238900001260.post-2214317178884342592021-04-09T02:53:00.002-07:002021-04-09T03:11:43.647-07:00Well-Ordering Principle<p><b>Theorem 1:</b> Well-Ordering Princple</p><p>Every non-empty set of non-negative integers contains a least element</p><p><br /></p><p>Proof:</p><p><br />(1) Assume that there exists a non-empty set $S$ of positive integers that does not contain a least element.</p><p>(2) Let $P(n)$ be true if $n$ is an element of $S$</p><p>(3) $P(0)$ is false. If true, then $0$ would be the least element for $S$</p><p>(4) Assume that for all $i \le n, P(i)$ is false. </p><p>(5) It follows that $P(n+1)$ is false. If not, then $n+1$ would be the least element for $S$.</p><p>(6) But, then by the <a href="https://allaboutprimes.blogspot.com/2021/04/principle-of-mathematical-induction.html" target="_blank">Principle of Mathematical Induction</a>, there is no positive integer in $S$</p><p>(7) This contradicts our assumption in (1) that $S$ is non-empty. Therefore, we can reject our assumption in step (1).</p><p><br /></p><p>Note: This is an example of a <a href="https://en.wikipedia.org/wiki/Proof_by_contradiction" target="_blank">proof by contradiction</a>.</p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-14271772621027428752021-04-09T02:41:00.000-07:002021-04-09T02:41:06.660-07:00Principle of Mathematical Induction<p><b>Axiom 1: Principle of Mathematical Induction</b></p><p>A proof by induction consists of 2 steps:</p><p>(1) <b>Base Case</b>: Proves that the statement is true for one case independent of all other cases.</p><p>(2) <b>Inductive Case</b>: Proves that if the statement holds for any case $n=k$, then it must also hold for $n=k+1$</p><p>The principle can be understood with the analogy of a ladder. if we can climb on the bottom rung of a ladder and for each rung, we can climb to the next, then it follows that we can climb as high as we like up to the top of the ladder. </p><p><br /></p><p>This principle is very important in the establishment of advanced mathematical arguments.</p><p><br /></p>Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com1tag:blogger.com,1999:blog-1984749238900001260.post-47738096267631703202020-05-05T01:42:00.001-07:002020-05-05T10:37:25.672-07:00The Prime NumbersThe Ancient Greeks loved to classify numbers. Numbers that could be represented as the ratio of two whole numbers were <a href="https://en.wikipedia.org/wiki/Rational_number">rational numbers</a>. Numbers such as $\sqrt{2}$ which could not were irrational <a href="https://en.wikipedia.org/wiki/Irrational_number">numbers</a>. A <a href="https://en.wikipedia.org/wiki/Perfect_number">perfect number</a>, such as 6, is equal to the sum of its proper <a href="https://en.wikipedia.org/wiki/Divisor#Further_notions_and_facts">divisors</a>. <a href="https://en.wikipedia.org/wiki/Amicable_numbers">Amicable numbers</a>, such as 220 and 284, are pairs of numbers where each is the sum of the proper divisors of the other.<br />
<br />
Without a doubt, the most important of these classifications was the concept of a <a href="https://en.wikipedia.org/wiki/Prime_number">prime number</a>. A prime number is any positive integer that has exactly two divisors. $5$ is a prime number but $8$ is not. $1$ is not, $0$ is not, and negative numbers are not. While the definition is clear, one might immediately ask, why should one care.<br />
<br />
There are two big reasons why we should care. If mathematics is the study of patterns, some of the most amazing and surprising patterns relate to prime numbers. Investigating prime numbers turns out to be a royal path to deep mathematical insights. For example, one of the most important problems in mathematics today is the <a href="https://en.wikipedia.org/wiki/Riemann_hypothesis">Reimann Hypothesis</a> which concerns the relationship between prime numbers and the complex <a href="https://en.wikipedia.org/wiki/Riemann_zeta_function">zeta function</a>. By the way, if anyone solves it, there's <a href="https://en.wikipedia.org/wiki/Millennium_Prize_Problems">a million dollar prize</a> waiting to be claimed.<br />
<br />
The other reason to care about primes is that their properties have become fundamental to the very running of global eCommerce. Prime numbers start out very common and become surprisingly rare as one starts to consider very large numbers. It turns out that determining whether a number is prime can take a significant computation effort if the prime is large enough. In fact, one of the great pursuits of spare computation capacity is the <a href="https://en.wikipedia.org/wiki/Great_Internet_Mersenne_Prime_Search">search for new primes</a>. Each time a new largest prime is discovered, it is worthy of a news headline. For example, <a href="https://www.npr.org/2018/12/21/679207604/the-world-has-a-new-largest-known-prime-number">here</a> is a news headline from NPR in 2018.<br />
<br />
Because there are an infinite number of primes (more about that later) and because it is possible to find primes up to the limits of current computational power, they have become an excellent foundation for security. Indeed, this is the foundation of <a href="https://en.wikipedia.org/wiki/Public-key_cryptography">public key encryption</a>. For example, <a href="https://en.wikipedia.org/wiki/RSA_(cryptosystem)">RSA</a>, one of the earliest public key encryptions is based on the difficulty of factoring the product of two large prime numbers.<br />
<br />
But let's start smaller. Let's focus on fundamental patterns. For me, there are two incredibly surprising facts about primes that can serve as a starting point. Of course, one or both may not be surprising to you. First, each positive number is characterized by a unique combination of primes.<br />
<br />
If I take any set of primes (for example $2,3,5$) at a specific power (for this example, we'll choose the power of $1$), then there is ONLY one number equal to their product. In this case, $30$. This property is called <a href="https://en.wikipedia.org/wiki/Unique_factorization_domain">unique factorization</a>. The natural numbers are characterized by unique factorization. If there is a prime that divides one but not the other number, they are not equal. If there is a power of a prime that divides one but not the other, they are not equal. From this perspective, they provide an opportunity to simplify reasoning about very large numbers. If I have two very complicated equations which I want to compare, I can quickly see that they are not equal if a prime divides one but does not the other. For example, I can say without a doubt for all integer values of $x$ and $y$, the following will never be equal:<br />
<br />
$$4^x \ne 7^y$$<br />
<br />
I mentioned in a previous post that natural numbers are just one of many types of numbers. One of the most surprising facts for me is that not all number systems are characterized by unique factorization. In other words, there are numbers where they are products of different primes and yet they are still equal. With our intuitions about the concept of number from the whole numbers and the integers, this may seem impossible. If don't believe me, you can check it out for yourself. For example, not all <a href="https://en.wikipedia.org/wiki/Quadratic_integer#Quadratic_integer_rings">quadratic integers</a> are characterized by unique factorization. Even the great genius <a href="https://en.wikipedia.org/wiki/Leonhard_Euler">Leonhard Euler</a> (pronounced Oiler) was not beyond making a bad assumption about unique factorization. If you are interested, I provide the details of his mistake <a href="http://fermatslasttheorem.blogspot.com/2005/06/eulers-mistake.html">here</a>.<br />
<br />
Unique factorization is such as an important properties of integers that the theorem that establishes unique factorization is called the <a href="https://en.wikipedia.org/wiki/Fundamental_theorem_of_arithmetic">Fundamental Theorem of Arithmetic</a>.<br />
<br />
In my next blog post, I will walk through a simple proof of this fundamental theorem.Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-11454862734447220522020-05-03T12:41:00.001-07:002020-05-03T18:20:11.185-07:00The Natural NumbersA <a href="https://en.wikipedia.org/wiki/Number">number</a>, as a concept, is a surprisingly ambiguous term. There are <a href="https://mathworld.wolfram.com/WholeNumber.html">whole numbers</a>, <a href="https://en.wikipedia.org/wiki/Fraction_(mathematics)">fractions</a>, <a href="https://en.wikipedia.org/wiki/Negative_number">negative numbers</a>, <a href="https://en.wikipedia.org/wiki/Real_number">real numbers</a>, <a href="https://en.wikipedia.org/wiki/Irrational_number">irrational numbers</a>, <a href="https://en.wikipedia.org/wiki/Imaginary_number">imaginary numbers</a>, and <a href="https://en.wikipedia.org/wiki/Transcendental_number">transcendental numbers</a>. It may not be intuitively obvious what they all have in common. There are also mathematical operations that are not defined and are probably not numbers at all such as $\dfrac{1}{0}$ (see <a href="https://en.wikipedia.org/wiki/Division_by_zero">here</a>) or $0^0$ (see <a href="https://en.wikipedia.org/wiki/Undefined_(mathematics)">here</a>). The concept of infinity is another difficult to nail down concept. Is it a number? It turns out that there are different types of infinity. For example, the number of counting numbers (1, 2, 3, ...) is less than the number of points in an infinitely divisible line (see <a href="https://en.wikipedia.org/wiki/Cardinality_of_the_continuum">here</a>). I will tackle these more advanced topics later<br />
<div>
<br /></div>
<div>
Historically, the concept of number began with the activities of counting and measuring. Counting led to the whole numbers which did not include 0 at the very beginning and measuring led to simple fractions (more complicated fractions require a more complicated number system). </div>
<div>
<br /></div>
<div>
The most important historical breakthroughs which we pretty much take for granted today are:</div>
<div>
<ul>
<li><b>Invention of number symbols</b> (typically, the earliest form of writing that comes after use of tally scratches and tally scratch groupings) (For context, see <a href="https://en.wikipedia.org/wiki/History_of_writing">history of writing</a> and <a href="https://en.wikipedia.org/wiki/History_of_ancient_numeral_systems">history of ancient numeral systems</a>)</li>
<li><b>Discovery of zero</b> (For context, see <a href="https://en.wikipedia.org/wiki/0#History">history of zero</a>)</li>
<li><b>Positional Notation</b> which allows all numbers to be represented by a finite set of digits (For context, see <a href="https://en.wikipedia.org/wiki/Positional_notation">here</a>)</li>
<li><b>Negative numbers</b> (For context, see <a href="https://en.wikipedia.org/wiki/Negative_number#History">history of negative numbers</a>)</li>
<li><b>Irrational numbers</b> which showed that not all measurements are ratios of whole numbers (For context, see <a href="https://en.wikipedia.org/wiki/Irrational_number#History">history of irrational numbers</a>)</li>
<li><b>The Decimal System</b> (For context, see <a href="https://en.wikipedia.org/wiki/Decimal">here</a>. Not all societies used Base 10. The Ancient Babylonians for example used a <a href="https://en.wikipedia.org/wiki/Sexagesimal">Sexagesimal System</a> which is Base 60).</li>
</ul>
<div>
In mathematics, the set of positive whole numbers and zero is called the <a href="https://en.wikipedia.org/wiki/Natural_number">Natural Numbers</a> and is represented by <b>N</b>;. When combined with the set of negative numbers, it becomes the sets of <a href="https://en.wikipedia.org/wiki/Integer">Integers</a> which is represented by <b>Z</b>. (Why <b>Z</b>, it comes from the German word <i>Zahlen </i>for 'numbers')</div>
</div>
<div>
<br /></div>
<div>
The study of the properties of Integers is called <a href="https://en.wikipedia.org/wiki/Number_theory">number theory</a> and this will be the primary focus of this blog. </div>
<div>
<br /></div>
<div>
In my view, the most surprising and deepest insight in all of mathematics is that natural numbers, despite their appearances of being the simplest of mathematical objects, contain some of the most challenging and important problems known to mathematics. </div>
<div>
<br /></div>
<div>
These challenges have led to the development of <a href="https://en.wikipedia.org/wiki/Public-key_cryptography">public key cryptography</a> which today powers the global economy. Innovations such as <a href="https://en.wikipedia.org/wiki/Blockchain">block chain</a>, which build on top of the complexity of mathematical problems, will further transform our economic, social, and political institutions that depend on hierarchy and centralized authority. </div>
<div>
<br /></div>
<div>
One popular definition of Mathematics is "the study of patterns" (see <a href="https://www.maa.org/press/periodicals/convergence/mathematics-as-the-science-of-patterns-mathematics-as-the-science-of-patterns">here</a> for an interesting overview). Many of the most surprising and profound patterns can be found in Number Theory.</div>
Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-67805323295213555492020-05-02T14:40:00.001-07:002020-05-02T14:42:43.451-07:00A Change In DirectionStarting today, I will update this blog on a regular basis. I will use this blog as an exploration of the fundamental properties of primes as well as an attempt to generalize ideas.<br />
<br />
If the past is any indication, my attempts will usually reflect a misunderstanding of a fundamental or a mistake in one step of my argument. So, when I make my attempts, I will make sure to provide a thorough explanation of the mistakes that I made.<br />
<br />
I will organize the blog posts as an attempt at a book. So, as the blog proceeds, I will re-edit previous blog posts in the attempt to create a consistent narrative. So, in theory, a person could start on the first blog post and proceed from there or start on what will become the table of contents and jump from there into any topic of interest.<br />
<br />
I will start with very elementary ideas. This will be a very personal journey. So, I will proceed from the elementary ideas based on my interests and my attempt to generalize standard results.<br />
<br />
I hope that others will find this interesting. I warn everyone that while I am a serious amateur, I will make mistakes. These blog posts will be primarily interesting to other amateurs. For serious math students, I strongly recommend going to the blogs of professional mathematicians such as <a href="https://terrytao.wordpress.com/">Terence Tao</a> and <a href="https://dms.umontreal.ca/~andrew/">Andrew Granville</a> who are two of the most amazing writers and brilliant mathematicians.<br />
<br />
Since I am an amateur, I will also make every effort to call out my sources and so that if my argument is unclear, it is possible to go to the source to find a professional explanation.<br />
<br />
Most importantly, enjoy. The journey is the purpose. :-)<br />
<br />
<br />Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-1680843372325519992020-02-25T14:34:00.000-08:002020-02-25T14:34:37.951-08:00There are at least $n$ primes between $n$ and $n^2$<br />
<br />
Theorem 1: $\pi(2^k) \le 3\dfrac{2^k}{k} $<br />
<br />
(1) For $k \le 5$:<br />
<br />
$\pi(2^1) = 1 \le 2\dfrac{2^1}{1} = 4$<br />
$\pi(2^2) = 2 \le 2\dfrac{ 2^2}{2} = 4$<br />
$\pi(2^3) = 4 \le 2\dfrac{2^3}{3} = \dfrac{16}{3} > 5$<br />
$\pi(2^4) = 6 \le 2\dfrac{2^4}{4} = 8$<br />
$\pi(2^5) = 11 \le 2\dfrac{2^5}{5} = \dfrac{64}{5} > 12$<br />
<br />
(2) Assume it is true up to some $k \ge 5$<br />
<br />
(3) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$ since:<br />
<br />
(a) $2^{2n} = \sum\limits_{i \le 2n}{{2n}\choose i}$<br />
<br />
(b) $n^{\pi(2n) - \pi(n)} \le p^{\pi(2n) - \pi(n)} \le \prod\limits_{n < p \le2n}p \le {{2n}\choose{n}} \le 2^{2n}$<br />
<br />
(c) $(\pi(2n) - \pi(n))\log n \le (2n)\log 2$<br />
<br />
(d) $\pi(2n) - \pi(n) \le (2n)\dfrac{\log 2}{\log n}$<br />
<br />
(4) $\pi(2^{k+1}) - \pi(2^k) \le (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$ so that $\pi(2^{k+1}) \le \pi(2^k) + (2^{k+1})\dfrac{\log 2}{\log 2^{k}}$<br />
<br />
(5) $\log 2^{k} = k\log 2$ so that $\dfrac{1}{k} = \dfrac{\log 2}{\log 2^{k}}$<br />
<br />
(6) $5k+5 < 6k$ so that $\dfrac{5}{k} < \dfrac{6}{k+1}$<br />
<br />
(7) $\pi(2^{k+1}) \le \pi(2^k) + \dfrac{2^{k+1}}{k} \le \dfrac{3\times2^k}{k} + \dfrac{2\times2^k}{k} = \dfrac{5\times2^k}{k} \le \dfrac{3\times2^{k+1}}{k+1}$<br />
<br />
<br />
Corollary: $\pi(x) \le 6 \log 2 \dfrac{x}{\log x}$<br />
<br />
(1) For $x \le 4, \pi(x) \le 6\log 2 \dfrac{x}{\log x}$<br />
<br />
$\pi(2) = 1 \le 6\log2\dfrac{2}{\log 2}$ since $\log 2 < 12\log 2$<br />
<br />
$\pi(3) = 2 \le 6\log 2\dfrac{3}{\log 3}$ since $2\log 3 < 18\log 2$<br />
<br />
$\pi(4) = 2 \le 6\log 2\dfrac{4}{\log 4}$ since $2\log 4 < 24\log 2$<br />
<br />
(2) There exists $k$ such that $2^k \le x \le 2^{k+1}$<br />
<br />
(3) $\dfrac{1}{k+1} < \dfrac{\log 2}{\log 2^{k}}$ since $\log 2^k < (k+1)(\log 2)$<br />
<br />
(4) $\pi(x) \le \pi(2^{k+1}) \le 3\dfrac{2^{k+1}}{k+1} \le 6\dfrac{2^{k}}{k+1} < 6\log 2\dfrac{2^k}{\log 2^k} \le 6\log 2\dfrac{x}{\log x}$<br />
<br />
Let $v_p(n)$ be the maximum power of $p$ that divides $n$<br />
<br />
Lemma 1: $v_p(n!) = \sum\limits_{m \ge 1}\left\lfloor\dfrac{n}{p^m}\right\rfloor$<br />
<br />
There are $\left\lfloor\dfrac{n!}{p}\right\rfloor$ instances of numbers divisible by $p$.<br />
<br />
There are $\left\lfloor\dfrac{n!}{p^2}\right\rfloor$ instances of numbers divisible by $p^2$<br />
<br />
And so on.<br />
<br />
Lemma 2: $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor \in \{0, 1\}$<br />
<br />
(1) Let $\{x\}$ be the fractional part of $x$<br />
<br />
(2) If $\{x\} < \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 0$<br />
<br />
(3) If $\{x\} \ge \dfrac{1}{2}$, then $\lfloor{2x}\rfloor - 2\lfloor{x}\rfloor = 1$<br />
<br />
Theorem 2: $\pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$<br />
<br />
(1) If $m > \dfrac{\log 2n}{\log p}$, then $\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor = 0$<br />
<br />
(2) $v_p\left({{2n}\choose{n}}\right) = \sum\limits_{m \ge 1}\left(\left\lfloor\dfrac{2n}{p^m}\right\rfloor - 2\left\lfloor\dfrac{n}{p^m}\right\rfloor\right) \le<br />
\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor$<br />
<br />
(3) $\dfrac{2^{2n}}{2n} \le {{2n}\choose{n}}$<br />
<br />
(4) $2n\log 2 - \log 2n \le \log {{2n}\choose{n}} \le \sum\limits_{p \le 2n}\left\lfloor\dfrac{\log 2n}{\log p}\right\rfloor\log p \le \sum\limits_{p \le 2n}\log 2n = \pi(2n)\log 2n$<br />
<br />
(5) $\pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1$<br />
<br />
(6) For $2 \le x \le 16, \pi(x) \ge \dfrac{\log 2}{2}\dfrac{x}{\log x}$<br />
<br />
<ul>
<li>$\pi(2) = 1 = \dfrac{\log 2}{2}\dfrac{2}{\log 2} = 1$</li>
<li>$\pi(3) = 2 > \dfrac{3}{2} > \dfrac{\log 2}{2}\dfrac{3}{\log 3}$</li>
<li>$\pi(4) = 2 = \dfrac{4}{2} > \dfrac{\log 2}{2}\dfrac{4}{\log 4}$</li>
<li>$\pi(5) = 3 \ge \dfrac{5}{2} > \dfrac{\log 2}{2}\dfrac{5}{\log 5}$</li>
<li>$\pi(6) = 3 = \dfrac{6}{2} > \dfrac{\log 2}{2}\dfrac{6}{\log 6}$</li>
<li>$\pi(7) = 4 > \dfrac{7}{2} > \dfrac{\log 2}{2}\dfrac{7}{\log 7}$</li>
<li>$\pi(8) = 4 = \dfrac{8}{2} > \dfrac{\log 2}{2}\dfrac{8}{\log 8}$</li>
<li>$\pi(9) = 4 > \dfrac{3}{2} = \dfrac{\log 2}{3\log 2}\dfrac{9}{2} > \dfrac{\log 2}{2}\dfrac{9}{\log 9}$</li>
<li>$\pi(10) =4 > \dfrac{5}{3} = \dfrac{\log 2}{3\log 2}\dfrac{10}{2} > \dfrac{\log 2}{2}\dfrac{10}{\log 10}$</li>
<li>$\pi(11)=5 > \dfrac{11}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{11}{2} > \dfrac{\log 2}{2}\dfrac{11}{\log 11}$</li>
<li>$\pi(12)=5 > 2 = \dfrac{\log 2}{3 \log 2}\dfrac{12}{2} > \dfrac{\log 2}{2}\dfrac{12}{\log 12}$</li>
<li>$\pi(13)=6 > \dfrac{13}{6} = \dfrac{\log 2}{3 \log 2}\dfrac{13}{2} > \dfrac{\log 2}{2}\dfrac{13}{\log 13}$</li>
<li>$\pi(14)=6 > \dfrac{7}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{14}{2} > \dfrac{\log 2}{2}\dfrac{14}{\log 14}$</li>
<li>$\pi(15)=6 > \dfrac{5}{2} = \dfrac{\log 2}{3 \log 2}\dfrac{15}{2} > \dfrac{\log 2}{2}\dfrac{15}{\log 15}$</li>
<li>$\pi(16)=6 > \dfrac{8}{3} = \dfrac{\log 2}{3 \log 2}\dfrac{16}{2} > \dfrac{\log 2}{2}\dfrac{16}{\log 16}$</li>
</ul>
<br />
<br />
(7) There exists $n$ such that $16 \le 2n < x \le 2n+2$<br />
<br />
(8) $\dfrac{2n}{\log 2n} - \dfrac{n+1}{\log 2n} = \dfrac{n-1}{\log 2n} \ge \dfrac{7}{\log 16} = \dfrac{7}{4\log 2} > \dfrac{4}{4\log 2} = \dfrac{1}{\log 2}$<br />
<br />
(9) $\pi(x) \ge \pi(2n) \ge \log 2\dfrac{2n}{\log 2n} - 1 = \dfrac{2n\log 2 - \log 2n}{\log 2n} = \dfrac{\log\frac{2^{2n}}{2n}}{\log 2n}$<br />
<br />
(10) for $n=8$, $2^6 > 8$<br />
<br />
(11) $2(2^{n-2}) = 2^{(n+1)-2} > 2n > n+1$ so that $\dfrac{2^{n-2}}{n} > 1$ and $\dfrac{2^{n-1}}{2n} > 1$ and $\dfrac{2^{2n}}{2n} > 2^{n+1}$<br />
<br />
(12) $\dfrac{\log\frac{2^{2n}}{2n}}{\log 2n} \ge \dfrac{\log 2^{n+1}}{\log (2n+2)} = \dfrac{(n+1)\log 2}{\log (2n+2)}$<br />
<br />
(13) Since $n+1 = \dfrac{2n+2}{2} \ge \dfrac{x}{2}$, it follows that $\dfrac{(n+1)\log 2}{\log (2n+2)} \ge \dfrac{x\log 2}{2\log x}$<br />
<br />
Corollary: For $46 \ge n \ge 4$, there are at least $n$ primes between $n$ and $n^2$<br />
<br />
(1) For $n \ge 28$, then:<br />
<br />
<ul>
<li>Between $4$ and $16$, there are 4 primes: $\{5, 7, 11, 13\}$</li>
<li>Between $5$ and $25$, there are 6 primes: $\{7,11,13,17,19,23\}$</li>
<li>Between $6$ and $36$, there are more than $6$ primes: $\{7,11,13,17,19,23,\dots\}$</li>
<li>Between $7$ and $49$, there are more than $7$ primes: $\{11,13, 17, 19, 23, 29, 31,\dots\}$</li>
<li>Between $8$ and $64$, there are more than $8$ primes: $\{11, 13,17,19,23,29,31,37,\dots\}$</li>
<li>Between $9$ and $81$, there are more than $9$ primes: $\{11,13,17,19,23,29,31,37,41,\dots\}$</li>
<li>Between $10$ and $100$, there are more than $10$ primes: $\{11,13,17,19,23,29,31,37,41,43,dotts\}$</li>
<li>Between $11$ and $121$, there are more than $11$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,\dots\}$</li>
<li>Between $12$ and $144$, there are more than $12$ primes: $\{13,17,19,23,29,31,37,41,43,47,53,59,\dots\}$</li>
<li>Between $13$ and $169$, there are more than $13$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,\dots\}$</li>
<li>Between $14$ and $196$, there are more than $14$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,\dots\}$</li>
<li>Between $15$ and $225$, there are more than $15$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,\dots\}$</li>
<li>Between $16$ and $256$, there are more than $16$ primes: $\{17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,\dots\}$</li>
<li>Between $17$ and $289$, there are more than $17$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,\dots\}$</li>
<li>Between $18$ and $324$, there are more than $18$ primes: $\{19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,\dots\}$</li>
<li>Between $19$ and $361$, there are more than $19$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,\dots\}$</li>
<li>Between $20$ and $400$, there are more than $20$ primes: $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,\dots\}$</li>
<li>Between $21$ and $441$, there are more than $21$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,\dots\}$</li>
<li>Between $22$ and $484$, there are more than $22$ primes, $\{23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113\dots\}$</li>
<li>Between $23$ and $529$, there are more than $23$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,\dots\}$</li>
<li>Between $24$ and $576$, there are more than $24$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,\dots\}$</li>
<li>Between $25$ and $625$, there are more than $25$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,\dots\}$</li>
<li>Betwen $26$ and $676$, there are more than $26$ primes, $\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,\dots\}$</li>
<li>Between $27$ and $729$, there are more than $27$ primes, $\$\{29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,\dots\}$</li>
</ul>
<br />
<br />
(2) $\pi(n^2) - \pi(n) \ge \dfrac{(n^2)\log 2}{2\log (n^2)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(n^2)\log 2}{4\log (n)} - \dfrac{(6n)\log 2}{\log n} = \dfrac{(\frac{n}{4} - 6)(n\log 2)}{\log n}$<br />
<br />
<br />Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-90845838275414524172015-01-29T04:53:00.000-08:002015-01-29T04:53:06.037-08:00An infinitude of primesEuclid provided a proof for the infinitude of primes. The following proof is based on his argument:<br />
<div>
<br /></div>
<div>
<b>Theorem 1: There are an infinite number of primes</b></div>
<div>
<br /></div>
<div>
(1) Assume that $p_n$ is the largest prime.</div>
<div>
(2) Let $q = p_n! + 1$</div>
<div>
(3) Since $q > p_n$, $q$ cannot be a prime (by our assumption).</div>
<div>
(4) So, therefore a prime $p$ divides $q$</div>
<div>
(5) But if $p \le p_n$, then $p | p_n!$ and $p | (p_n! + 1) - p_n! = 1$ which is impossible.</div>
<div>
(6) Therefore, we have a contradiction since $p > p_n$ but $p$ is a prime.</div>
<div>
<br /></div>
<div>
QED</div>
<div>
<br /></div>
<div>
<br /></div>
Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0tag:blogger.com,1999:blog-1984749238900001260.post-41543945847327053272014-12-28T20:46:00.003-08:002014-12-28T20:46:52.562-08:00IntroductionThe purpose of this blog will be for me to focus on primes and the fundamental theorems related to them.<br />
<br />
These will represent my notes. The goal is to present the fundamental ideas of number theory in as clear a manner as I can without requiring any background beyond standard arithmetic, a genuine interest in math, and an openness to the concepts involved.<br />
<br />
The content will be taken straight from number theory text books, classic math papers, and forums on math web sites.<br />
<br />
My favorite math web site for asking questions about mathematics is <a href="http://math.stackexchange.com/">math.stackexchange.com</a>. If you haven't been to this site, I encourage you to visit if you have any questions.<br />
<br />
<br />Larry Freemanhttp://www.blogger.com/profile/06906614246430481533noreply@blogger.com0