```{
localUrl: '../page/irreducibles_are_prime_in_integers.html',
arbitalUrl: 'https://arbital.com/p/irreducibles_are_prime_in_integers',
rawJsonUrl: '../raw/5mh.json',
likeableId: '3245',
likeableType: 'page',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [
'JaimeSevillaMolina'
],
pageId: 'irreducibles_are_prime_in_integers',
edit: '5',
editSummary: '',
prevEdit: '4',
currentEdit: '5',
wasPublished: 'true',
type: 'wiki',
title: 'Euclid's Lemma on prime numbers',
clickbait: 'A very basic but vitally important property of the prime numbers is that they "can't be split between factors": if a prime divides a product then it must divide one of the individual factors.',
textLength: '3047',
alias: 'irreducibles_are_prime_in_integers',
externalUrl: '',
sortChildrenBy: 'likes',
hasVote: 'false',
voteType: '',
votesAnonymous: 'false',
editCreatorId: 'PatrickStevens',
editCreatedAt: '2016-08-07 14:53:46',
pageCreatorId: 'PatrickStevens',
pageCreatedAt: '2016-07-28 15:39:06',
seeDomainId: '0',
editDomainId: 'AlexeiAndreev',
submitToDomainId: '0',
isAutosave: 'false',
isSnapshot: 'false',
isLiveEdit: 'true',
isMinorEdit: 'false',
indirectTeacher: 'false',
todoCount: '0',
isEditorComment: 'false',
isApprovedComment: 'true',
isResolved: 'false',
snapshotText: '',
anchorContext: '',
anchorText: '',
anchorOffset: '0',
mergedInto: '',
isDeleted: 'false',
viewCount: '26',
text: '[summary: The [4mf prime numbers] have a special property that they "can't be distributed between terms of a product": if \$p\$ is a prime dividing a product \$ab\$ of [48l integers], then \$p\$ wholly divides one or both of \$a\$ or \$b\$. It cannot be the case that "some but not all of \$p\$ divides into \$a\$, and the rest of \$p\$ divides into \$b\$".]\n\n[summary(Technical): Let \$p\$ be a [4mf prime] natural number. Then \$p \\mid ab\$ implies \$p \\mid a\$ or \$p \\mid b\$.]\n\nEuclid's lemma states that if \$p\$ is a [4mf prime number], which divides a product \$ab\$, then \$p\$ divides at least one of \$a\$ or \$b\$.\n\n# Proof\n\n## Elementary proof\n\nSuppose \$p \\mid ab\$ %%note:That is, \$p\$ divides \$ab\$.%%, but \$p\$ does not divide \$a\$.\nWe will show that \$p \\mid b\$.\n\nIndeed, \$p\$ does not divide \$a\$, so the [-5mw] of \$p\$ and \$a\$ is \$1\$ (exercise: do this without using integer factorisation); so by [bezouts_theorem Bézout's theorem] there are integers \$x, y\$ such that \$ax+py = 1\$.\n\n%%hidden(Show solution to exercise):\nWe are not allowed to use the fact that we can factorise integers, because we need "\$p \\mid ab\$ implies \$p \\mid a\$ or \$p \\mid b\$" as a lemma on the way towards the proof of the [-5rh] (which is the theorem that tells us we can factorise integers).\n\nRecall that the highest common factor of \$a\$ and \$p\$ is defined to be the number \$c\$ such that:\n\n- \$c \\mid a\$;\n- \$c \\mid p\$;\n- for any \$d\$ which divides \$a\$ and \$p\$, we have \$d \\mid c\$.\n\n[euclidean_algorithm Euclid's algorithm] tells us that \$a\$ and \$p\$ do have a (unique) highest common factor.\n\nNow, if \$c \\mid p\$, we have that \$c = p\$ or \$c=1\$, because \$p\$ is [4mf prime].\nBut \$c\$ is not \$p\$ because we also know that \$c \\mid a\$, and we already know \$p\$ does not divide \$a\$.\n\nHence \$c = 1\$.\n%%\n\nBut multiplying through by \$b\$, we see \$abx + pby = b\$.\n\$p\$ divides \$ab\$ and divides \$p\$, so it divides the left-hand side; hence it must divide the right-hand side too.\nThat is, \$p \\mid b\$.\n\n## More abstract proof\n\nThis proof uses much more theory but is correspondingly much more general, and it reveals the important feature of \$\\mathbb{Z}\$ here.\n\n\$\\mathbb{Z}\$, viewed as a [3gq ring], is a [-5r5]. ([integers_is_pid Proof.])\nThe theorem we are trying to prove is that the [5m1 irreducibles] in \$\\mathbb{Z}\$ are all [5m2 prime] in the sense of ring theory.\n\nBut it is generally true that in a PID, "prime" and "irreducible" coincide ([5mf proof]), so the result is immediate.\n\n# Converse is false\n\nAny composite number \$pq\$ (where \$p, q\$ are greater than \$1\$) divides \$pq\$ without dividing \$p\$ or \$q\$, so the converse is very false.\n\n# Why is this important?\n\nThis lemma is a nontrivial step on the way to proving the [-5rh]; and in fact in a certain general sense, if we can prove this lemma then we can prove the FTA.\nIt tells us about the behaviour of the primes with respect to products: we now know that the primes "cannot be split up between factors" of a product, and so they behave, in a sense, [5m1 "irreducibly"].\n\nThe lemma is also of considerable use as a tiny step in many different proofs.',
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: 'true',
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: [
'5mm'
],
questionIds: [],
tagIds: [],
relatedIds: [],
markIds: [],
explanations: [],
learnMore: [],
requirements: [],
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: '18536',
pageId: 'irreducibles_are_prime_in_integers',
userId: 'PatrickStevens',
edit: '5',
type: 'newEdit',
createdAt: '2016-08-07 14:53:46',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '18217',
pageId: 'irreducibles_are_prime_in_integers',
userId: 'PatrickStevens',
edit: '4',
type: 'newEdit',
createdAt: '2016-08-03 16:07:56',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '3325',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '1',
dislikeCount: '0',
likeScore: '1',
individualLikes: [],
id: '18216',
pageId: 'irreducibles_are_prime_in_integers',
userId: 'PatrickStevens',
edit: '3',
type: 'newEdit',
createdAt: '2016-08-03 16:06:55',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17666',
pageId: 'irreducibles_are_prime_in_integers',
userId: 'PatrickStevens',
edit: '2',
type: 'newEdit',
createdAt: '2016-07-28 16:56:27',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17648',
pageId: 'irreducibles_are_prime_in_integers',
userId: 'PatrickStevens',
edit: '0',
type: 'newParent',
createdAt: '2016-07-28 15:39:07',
auxPageId: 'math',
oldSettingsValue: '',
newSettingsValue: ''
},
{
likeableId: '0',
likeableType: 'changeLog',
myLikeValue: '0',
likeCount: '0',
dislikeCount: '0',
likeScore: '0',
individualLikes: [],
id: '17646',
pageId: 'irreducibles_are_prime_in_integers',
userId: 'PatrickStevens',
edit: '1',
type: 'newEdit',
createdAt: '2016-07-28 15:39:06',
auxPageId: '',
oldSettingsValue: '',
newSettingsValue: ''
}
],
feedSubmissions: [],
searchStrings: {},
hasChildren: 'false',
hasParents: 'true',
redAliases: {},
improvementTagIds: [],
nonMetaTagIds: [],
todos: [],
slowDownMap: 'null',
speedUpMap: 'null',
arcPageIds: 'null',
contentRequests: {}
}```