{
localUrl: '../page/fundamental_theorem_of_arithmetic.html',
arbitalUrl: 'https://arbital.com/p/fundamental_theorem_of_arithmetic',
rawJsonUrl: '../raw/5rh.json',
likeableId: '3323',
likeableType: 'page',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [
'EricBruylant'
],
pageId: 'fundamental_theorem_of_arithmetic',
edit: '5',
editSummary: '',
prevEdit: '4',
currentEdit: '5',
wasPublished: 'true',
type: 'wiki',
title: 'Fundamental Theorem of Arithmetic',
clickbait: 'The FTA tells us that natural numbers can be decomposed uniquely into prime factors; it is the basis of almost all number theory.',
textLength: '5907',
alias: 'fundamental_theorem_of_arithmetic',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'PatrickStevens',
editCreatedAt: '2016-08-07 10:18:06',
pageCreatorId: 'PatrickStevens',
pageCreatedAt: '2016-08-04 12:45:57',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '1',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '40',
text: '[todo: make Number Theory a parent of this]\n\n[summary: The Fundamental Theorem of Arithmetic is a statement about the [45h natural numbers]; it says that every natural number may be decomposed as a product of [4mf primes], and this expression is unique up to reordering the factors. It is an extremely important theorem, and it is the basis of the field of [-number_theory].]\n\nThe Fundamental Theorem of Arithmetic states that every [-45h] (greater than or equal to $2$) may be expressed as a product of [4mf prime numbers], and the product is unique up to reordering.\n\nThis theorem is one of the main reasons $1$ is not considered to be prime: indeed, if it were prime then $3 \\times 5$ could be factorised into primes as $3 \\times 5 \\times 1$, but these would be two *different* factorisations of the number $15$.\nThe FTA's statement is much cleaner if $1$ is not thought of as prime.\n\nIn a more general context, the FTA says precisely that the [3gq ring] $\\mathbb{Z}$ is a [-unique_factorisation_domain]; there is therefore a much more abstract proof than the elementary one we will present further on in this article:\n\n- $\\mathbb{Z}$ is a [euclidean_domain Euclidean domain] (with Euclidean function given by "take the modulus");\n- Therefore $\\mathbb{Z}$ is a [-5r5] ([euclidean_domain_is_pid proof]);\n- And principal ideal domains are unique factorisation domains ([principal_ideal_domain_has_unique_factorisation proof]).\n\n# Examples\n\n- The FTA does not talk about $0$ or $1$; this is because these numbers are conventionally considered neither prime nor composite.\n- Even if we haven't bothered to calculate $17 \\times 23 \\times 23$, we can immediately say that it is odd. Indeed, by the FTA, $2$ cannot divide $17 \\times 23^2$, because the complete list of prime factors of this number is $\\{ 17, 23, 23\\}$, and $2$ is prime.\n\n# Proof\n\nTimothy Gowers has an [excellent article](https://gowers.wordpress.com/2011/11/18/proving-the-fundamental-theorem-of-arithmetic/) about the proof of the FTA.\n\nThe FTA consists of two parts: we must show that every number can be decomposed as primes, and also that every number can be decomposed *uniquely*.\n\n## Every number can be written as a product of primes\n\nThis part is the easier, and it uses [-strong_induction] (a version of [5fz proof by induction]).\n\nClearly $2$ can be written as a product of primes, because it *is* prime; so it can be written as just itself.\n\nNow, for $n$ bigger than $2$, if $n$ is prime then we are immediately done (just write it as itself).\nOtherwise, $n$ is not prime, so it can be written as $a \\times b$, say, with $a$ and $b$ both less than $n$.\n\nBut by the inductive hypothesis, we can express $a$ and $b$ each as products of primes, so we can express $n$ as the combined product of the two sets of factors of $a$ and $b$.\n\n%%hidden(Example):\nConsider $n = 1274$.\nWe have two options: $n$ is prime or $n$ is composite.\n\nIt turns out that $n$ is actually equal to $49 \\times 26$, so it's not prime.\n\nBy the inductive hypothesis, we can factor $49$ as a product of primes (indeed, it's $7^2$); and we can factor $26$ as a product of primes (indeed, it's $2 \\times 13$); so we can factor $1274$ as $2 \\times 7^2 \\times 13$.\n\n(If you like, you can view this as just "start again at $49$ instead of at $1274$, and spit out what you get; then start again at $26$ instead of $1274$, and spit out what you get; and finally combine the spittings-out"; no mention of a spooky "inductive hypothesis" at all.)\n\nNote that at this point, we haven't any guarantee at all that this is the *only* prime factorisation; all we assert so far is that it is *a* prime factorisation.\n%%\n\n## Every number can be decomposed *uniquely* as a product of primes\n\nFor this, we will need a basic (but non-obvious and important) fact about the behaviour of prime numbers: [5mh Euclid's lemma], which states that if a prime $p$ divides a product $ab$, then $p$ divides at least one of $a$ and $b$.\n\nWe will work by induction on $n$ again.\nIf $n = 2$ then the result is immediate: a number can only be divided by numbers which are not larger than it, but $1$ and $2$ are the only such numbers.\n\nSuppose $n$ can be written as both $p_1 p_2 \\dots p_r$ and $q_1 q_2 \\dots q_s$, where each $p_i$ and $q_j$ is prime (but there might be repeats: maybe $p_1 = p_2 = q_3 = q_7$, for instance).\nWe need to show that $r=s$ and that (possibly after reordering the lists) $p_i = q_i$ for each $i$.\n\nCertainly $p_1$ divides $n$, because it divides $p_1 p_2 \\dots p_r$.\nTherefore it divides $q_1 q_2 \\dots q_s$, and hence it divides one of $q_1$ or $q_2 \\dots q_s$, by Euclid's lemma.\nTherefore either it divides $q_1$, or it divides one of $q_2$ or $q_3 \\dots q_s$; by induction, $p_1$ divides some $q_i$.\nBecause we don't care about the ordering of the list, let us reorder the list if necessary so that in fact $i=1$: put the factor $q_i$ at the start of the list.\n\nNow, $q_1$ is prime, and $p_1$ is not equal to $1$ but it divides $q_1$; hence $p_1 = q_1$.\n\nDividing through by $p_1$, then, we obtain $p_2 \\dots p_r = q_2 \\dots q_s$, a strictly smaller number; so by the inductive hypothesis, $r-1 = s-1$ (so $r=s$) and the unordered list of $p_i$ is the same as the unordered list of $q_i$ for $i \\geq 2$.\n\nThis proves the theorem.\n\n# Why is this not obvious?\n\nTimothy Gowers has a [good piece](https://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious/) on why this result is not just obvious.\nOf course, what is "obvious" and what is not "obvious" varies heavily depending on who you're talking to.\nFor this author personally, the true reason it's not obvious is Gowers's reason number 4: because there are very similar structures which do *not* have the property of unique factorisation.\n(Gowers uses $\\mathbb{Z}[\\sqrt{-5}]$; on the [5m1 page on irreducibles], we show that $\\mathbb{Z}[\\sqrt{-3}]$ could be used just as well.)',
metaText: '',
isTextLoaded: 'true',
isSubscribedToDiscussion: 'false',
isSubscribedToUser: 'false',
isSubscribedAsMaintainer: 'false',
discussionSubscriberCount: '1',
maintainerCount: '1',
userSubscriberCount: '0',
lastVisit: '',
hasDraft: 'false',
votes: [],
voteSummary: 'null',
muVoteSummary: '0',
voteScaling: '0',
currentUserVote: '-2',
voteCount: '0',
lockedVoteType: '',
maxEditEver: '0',
redLinkCount: '0',
lockedBy: '',
lockedUntil: '',
nextPageId: '',
prevPageId: '',
usedAsMastery: 'false',
proposalEditNum: '0',
permissions: {
edit: {
has: 'false',
reason: 'You don't have domain permission to edit this page'
},
proposeEdit: {
has: 'true',
reason: ''
},
delete: {
has: 'false',
reason: 'You don't have domain permission to delete this page'
},
comment: {
has: 'false',
reason: 'You can't comment in this domain because you are not a member'
},
proposeComment: {
has: 'true',
reason: ''
}
},
summaries: {},
creatorIds: [
'PatrickStevens'
],
childIds: [],
parentIds: [
'math'
],
commentIds: [],
questionIds: [],
tagIds: [
'start_meta_tag'
],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [
{
id: '5947',
parentId: 'irreducibles_are_prime_in_integers',
childId: 'fundamental_theorem_of_arithmetic',
type: 'requirement',
creatorId: 'PatrickStevens',
createdAt: '2016-08-04 12:30:45',
level: '1',
isStrong: 'true',
everPublished: 'true'
}
],
subjects: [],
lenses: [],
lensParentId: '',
pathPages: [],
learnMoreTaughtMap: {},
learnMoreCoveredMap: {},
learnMoreRequiredMap: {},
editHistory: {},
domainSubmissions: {},
answers: [],
answerCount: '0',
commentCount: '0',
newCommentCount: '0',
linkedMarkCount: '0',
changeLogs: [
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18535',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '5',
type: 'newEdit',
createdAt: '2016-08-07 10:18:06',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18371',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '4',
type: 'newEdit',
createdAt: '2016-08-04 19:49:12',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18370',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '3',
type: 'newEdit',
createdAt: '2016-08-04 19:47:00',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18331',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '2',
type: 'newEdit',
createdAt: '2016-08-04 12:50:48',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18327',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '0',
type: 'newRequirement',
createdAt: '2016-08-04 12:45:58',
auxPageId: 'irreducibles_are_prime_in_integers',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18329',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '0',
type: 'newParent',
createdAt: '2016-08-04 12:45:58',
auxPageId: 'math',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18330',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '0',
type: 'newTag',
createdAt: '2016-08-04 12:45:58',
auxPageId: 'start_meta_tag',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18326',
pageId: 'fundamental_theorem_of_arithmetic',
userId: 'PatrickStevens',
edit: '1',
type: 'newEdit',
createdAt: '2016-08-04 12:45:57',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}