Another Proof of Euclid's Theorem (infinite number of primes)?
Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.
If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.
Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.
We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.
Let $mathtt E$ be a function
$quad mathtt E: mathbb N to mathcal F (mathbb N)$
satisfying the following:
$quad quadquadforall n in mathbb N$
$tag 0 mathtt E (2) = {2}$
$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$
$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$
$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$
We have the following result:
Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').
Question: Can the theorem be proved in this $(mathbb N,+)$ setting?
If yes, we can continue.
Theorem 2: The set of all prime numbers is an infinite set.
Proof
If $a_1$ is any number, consider the 'next further out' number
$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.
A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).
Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets
$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$
So there are sets of prime numbers with more elements than any finite set. $blacksquare$
My Work
Please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.
Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question
Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
|
show 5 more comments
Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.
If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.
Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.
We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.
Let $mathtt E$ be a function
$quad mathtt E: mathbb N to mathcal F (mathbb N)$
satisfying the following:
$quad quadquadforall n in mathbb N$
$tag 0 mathtt E (2) = {2}$
$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$
$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$
$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$
We have the following result:
Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').
Question: Can the theorem be proved in this $(mathbb N,+)$ setting?
If yes, we can continue.
Theorem 2: The set of all prime numbers is an infinite set.
Proof
If $a_1$ is any number, consider the 'next further out' number
$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.
A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).
Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets
$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$
So there are sets of prime numbers with more elements than any finite set. $blacksquare$
My Work
Please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.
Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question
Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 '18 at 17:39
@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 '18 at 17:44
1
The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 '18 at 18:05
1
@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08
1
@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37
|
show 5 more comments
Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.
If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.
Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.
We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.
Let $mathtt E$ be a function
$quad mathtt E: mathbb N to mathcal F (mathbb N)$
satisfying the following:
$quad quadquadforall n in mathbb N$
$tag 0 mathtt E (2) = {2}$
$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$
$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$
$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$
We have the following result:
Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').
Question: Can the theorem be proved in this $(mathbb N,+)$ setting?
If yes, we can continue.
Theorem 2: The set of all prime numbers is an infinite set.
Proof
If $a_1$ is any number, consider the 'next further out' number
$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.
A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).
Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets
$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$
So there are sets of prime numbers with more elements than any finite set. $blacksquare$
My Work
Please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.
Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question
Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
Here $mathbb N = {2,3,4,dots}$ with the binary operation of addition.
If $m in mathbb N$ we denote by $G_{mathbb N} (m)$ the semigroup generated by $m$.
Definition: A number $p$ is said to be prime if for all $m lt p$, $;p notin G_{mathbb N} (m) $.
We denote the set of non-empty finite subsets of $mathbb N$ by $mathcal F (mathbb N)$.
Let $mathtt E$ be a function
$quad mathtt E: mathbb N to mathcal F (mathbb N)$
satisfying the following:
$quad quadquadforall n in mathbb N$
$tag 0 mathtt E (2) = {2}$
$tag 1 text{ If } (forall text{ prime } p lt n) ; n notin G_{mathbb N} (p) text{ then } mathtt E (n) = {n}$
$tag 2 text{ If } , (exists text{ prime } p lt n) ; n in G_{mathbb N} (p) text{ then } mathtt E (n) text{ is the union of all such primes}$
$tag 3 mathtt E (n+1) cap mathtt E (n) = emptyset$
We have the following result:
Theorem 1: There exist one and only one function $mathtt E$ satisfying $text{(0)}$ thru $text{(2)}$; it will also satisfy $text{(3)}$. Moreover, for every $n$, all the numbers in the set $mathtt E (n)$ are prime (the prime 'factors').
Question: Can the theorem be proved in this $(mathbb N,+)$ setting?
If yes, we can continue.
Theorem 2: The set of all prime numbers is an infinite set.
Proof
If $a_1$ is any number, consider the 'next further out' number
$tag 4 a_2 = sum_{i=1}^{a_1+1}, a_1 = sum_{i=1}^{a_1},( a_1 + 1)$.
A simple argument using $text{(3)}$ shows that $mathtt E (a_1) subsetneq mathtt E (a_2);$ (c.f. Bill Dubuque's remark).
Employing recursion we get a sequence $a_1, a_2, a_3,dots$ with a corresponding chain of strictly increasing sets
$quad mathtt E (a_1) subsetneq mathtt E (a_2) subsetneq E (a_3) dots$
So there are sets of prime numbers with more elements than any finite set. $blacksquare$
My Work
Please see
Using the recursion theorem to implement the Sieve of Eratosthenes.
The proof of theorem 2 is along the lines found in the proof given by Filip Saidak. Also, if we set $a_1$ to $1$ in theorem 2 we get the researched OEIS sequence A007018.
Note that the proof supplied by Filip Saidak has most likely been known for many years; see Bill Dubuque's answer to the math.stackexchange.com question
Is there an intuitionist (i.e., constructive) proof of the infinitude of primes?
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
abstract-algebra elementary-number-theory prime-numbers alternative-proof semigroups
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
edited Nov 24 '18 at 12:11
CopyPasteIt
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
asked Nov 22 '18 at 17:10
CopyPasteItCopyPasteIt
4,0651627
4,0651627
Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 '18 at 17:39
@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 '18 at 17:44
1
The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 '18 at 18:05
1
@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08
1
@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37
|
show 5 more comments
Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 '18 at 17:39
@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 '18 at 17:44
1
The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 '18 at 18:05
1
@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08
1
@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37
Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 '18 at 17:39
Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 '18 at 17:39
@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 '18 at 17:44
@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 '18 at 17:44
1
1
The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 '18 at 18:05
The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 '18 at 18:05
1
1
@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08
@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08
1
1
@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37
@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37
|
show 5 more comments
1 Answer
1
active
oldest
votes
It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
1
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
add a comment |
Your Answer
StackExchange.ifUsing("editor", function () {
return StackExchange.using("mathjaxEditing", function () {
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix) {
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["$", "$"], ["\\(","\\)"]]);
});
});
}, "mathjax-editing");
StackExchange.ready(function() {
var channelOptions = {
tags: "".split(" "),
id: "69"
};
initTagRenderer("".split(" "), "".split(" "), channelOptions);
StackExchange.using("externalEditor", function() {
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled) {
StackExchange.using("snippets", function() {
createEditor();
});
}
else {
createEditor();
}
});
function createEditor() {
StackExchange.prepareEditor({
heartbeatType: 'answer',
autoActivateHeartbeat: false,
convertImagesToLinks: true,
noModals: true,
showLowRepImageUploadWarning: true,
reputationToPostImages: 10,
bindNavPrevention: true,
postfix: "",
imageUploader: {
brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
allowUrls: true
},
noCode: true, onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
});
}
});
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3009367%2fanother-proof-of-euclids-theorem-infinite-number-of-primes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
1 Answer
1
active
oldest
votes
1 Answer
1
active
oldest
votes
active
oldest
votes
active
oldest
votes
It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
1
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
add a comment |
It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
1
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
add a comment |
It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
It is valid, but seems to be fundamentally the same as the classical proof; both hinge upon the fact that $p_1times p_2times cdotstimes p_n+1$ is divisible by some prime not in ${p_1,p_2,dots,p_n}$.
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
answered Nov 22 '18 at 17:22
Rafay AsharyRafay Ashary
83618
83618
1
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
add a comment |
1
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
1
1
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
@Copy It is poor form to change the question in a way that invalidates existing answers.
– Tobias Kildetoft
Nov 23 '18 at 17:08
add a comment |
Thanks for contributing an answer to Mathematics Stack Exchange!
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
Use MathJax to format equations. MathJax reference.
To learn more, see our tips on writing great answers.
Some of your past answers have not been well-received, and you're in danger of being blocked from answering.
Please pay close attention to the following guidance:
- Please be sure to answer the question. Provide details and share your research!
But avoid …
- Asking for help, clarification, or responding to other answers.
- Making statements based on opinion; back them up with references or personal experience.
To learn more, see our tips on writing great answers.
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
StackExchange.ready(
function () {
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f3009367%2fanother-proof-of-euclids-theorem-infinite-number-of-primes%23new-answer', 'question_page');
}
);
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Sign up or log in
StackExchange.ready(function () {
StackExchange.helpers.onClickDraftSave('#login-link');
});
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Required, but never shown
Note, multiplication (of positive integers) is recursive addition. That is, we define $acdot1$ to be $a$ and $acdot(n+1)$ to be $acdot n+a$.
– Barry Cipra
Nov 22 '18 at 17:39
@BarryCipra Yes I know. But I get excited when something that appears 'bound to multiplication' - the prime numbers - can get released into a more elementary framework.
– CopyPasteIt
Nov 22 '18 at 17:44
1
The proof via $,n(n!+!1),$ has more prime factors than $n$ for $,nge 1$ is surely much older than Saidak's 2005 paper. The generated sequence is OEIS A007018. Note: adding $1$ yields Sylvestoer sequence $a_{n+1} = a_n^2 - a_n + 1 = $ OEIS A000058. See the OEIS notes for other connections.
– Bill Dubuque
Nov 22 '18 at 18:05
1
@CopyPasteIt The least factor $> 1$ of $n$ is prime (i.e. irreducible) is already quite minimal.
– Bill Dubuque
Nov 22 '18 at 19:08
1
@CopyPasteIt Well one can unwind everything down to Peano arithmetic, but that won't be very arithmetically enlightening. Why prefer assembly language over the beautiful higher-level language carefully crafted by number theorists over many centuries?
– Bill Dubuque
Nov 22 '18 at 19:37