{ localUrl: '../page/cauchy_theorem_on_subgroup_existence_intuitive.html', arbitalUrl: 'https://arbital.com/p/cauchy_theorem_on_subgroup_existence_intuitive', rawJsonUrl: '../raw/4ys.json', likeableId: '2904', likeableType: 'page', myLikeValue: '0', likeCount: '2', dislikeCount: '0', likeScore: '2', individualLikes: [ 'AlexeiAndreev', 'EricBruylant' ], pageId: 'cauchy_theorem_on_subgroup_existence_intuitive', edit: '1', editSummary: '', prevEdit: '0', currentEdit: '1', wasPublished: 'true', type: 'wiki', title: 'Cauchy's theorem on subgroup existence: intuitive version', clickbait: '', textLength: '6021', alias: 'cauchy_theorem_on_subgroup_existence_intuitive', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'PatrickStevens', editCreatedAt: '2016-06-30 15:51:06', pageCreatorId: 'PatrickStevens', pageCreatedAt: '2016-06-30 15:51:06', seeDomainId: '0', editDomainId: 'AlexeiAndreev', submitToDomainId: '0', isAutosave: 'false', isSnapshot: 'false', isLiveEdit: 'true', isMinorEdit: 'false', indirectTeacher: 'false', todoCount: '2', isEditorComment: 'false', isApprovedComment: 'true', isResolved: 'false', snapshotText: '', anchorContext: '', anchorText: '', anchorOffset: '0', mergedInto: '', isDeleted: 'false', viewCount: '46', text: 'Cauchy's Theorem states that if $G$ is a finite [-group], and $p$ is a [4mf prime] dividing the [3gg order] of $G$, then $G$ has an element of order $p$.\nEquivalently, it has a subgroup of order $p$.\n\nThis theorem is very important as a partial converse to [4jn Lagrange's theorem]: while Lagrange's theorem gives us *restrictions* on what subgroups can exist, Cauchy's theorem tells us that certain subgroups *definitely do* exist.\nIn this direction, Cauchy's theorem is generalised by the [sylow_theorems_on_subgroup_existence Sylow theorems].\n\n# Proof\n\nLet $G$ be a group, and write $e$ for its identity.\nWe will try and find an element of order $p$.\n\nWhat does it mean for an element $x \\not = e$ to have order $p$? Nothing more nor less than that $x^p = e$.\n(This is true because $p$ is prime; if $p$ were not prime, we would additionally have to stipulate that $x^i$ is not $e$ for any smaller $i < p$.)\n\nNow follows the magic step which casts the problem in the "correct" light.\n\nConsider all possible combinations of $p$ elements from the group.\nFor example, if $p=5$ and the group elements are $\\{ a, b, c, d, e\\}$ with $e$ the identity, then $(e, e, a, b, a)$ and $(e,a,b,a,e)$ are two different such combinations.\nThen $x \\not = e$ has order $p$ if and only if the combination $(x, x, \\dots, x)$ multiplies out to give $e$.\n\nThe rest of the proof will be simply following what this magic step has told us to do.\n\nSince we want to find some $x$ where $(x, x, \\dots, x)$ multiplies to give $e$, it makes sense only to consider the combinations which multiply out to give $e$ in the first place.\nSo, for instance, we will exclude the tuple $(e, e, a, b, a)$ from consideration if it is the case that $eeaba$ is the identity (equivalently, that $aba = e$).\nFor convenience, we will label the set of all the allowed combinations: let us call it $X$.\n\nOf the tuples in $X$, we are looking for one with a very specific property: every entry is equal.\nFor example, the tuple $(a,b,c,b,b)$ is no use to us, because it doesn't tell us an element $x$ such that $x^p = e$; it only tells us that $abcbb = e$.\nSo we will be done if we can find a tuple in $X$ which has every element equal (and which is not the identity).\n\nWe don't really have anything to go on here, but it will surely help to know the size of $X$: it is $|G|^{p-1}$, since every element of $X$ is determined exactly by its first $p-1$ places (after which the last is fixed).\nThere are no restrictions on the first $p-1$ places, though: we can find a $p$th element to complete any collection of $p-1$.\n\n%%hidden(Example):\nIf $p=5$, and we have the first four elements $(a, a, b, e, \\cdot)$, then we know the fifth element *must* be $b^{-1} a^{-2}$.\nIndeed, $aabe(a^{-1} a^{-2}) = e$, and [ inverse elements of a group are unique], so nothing else can fill the last slot.\n%%\n\nSo we have $X$, of size $|G|^{p-1}$; we have that $p$ divides $|G|$ (and so it divides $|X|$); and we also have an element $(e,e,\\dots,e)$ of $X$.\nBut notice that if $(a_1, a_2, \\dots, a_p)$ is in $X$, then so is $(a_2, a_3, \\dots, a_p, a_1)$; and so on through all the rotations of an element.\nWe can actually group up the elements of $X$ into buckets, where two tuples are in the same bucket if (and only if) one can be rotated to make the other.\n\nHow big is a bucket? If a bucket contains something of the form $(a, a, \\dots, a)$, then of course that tuple can only be rotated to give one thing, so the bucket is of size $1$.\nBut if the bucket contains any tuple $T$ which is not "the same element repeated $p$ times", then there must be exactly $p$ things in the bucket: namely the $p$ things we get by rotating $T$. (Exercise: verify this!)\n\n%%hidden(Show solution):\nThe bucket certainly does contain every rotation of $T$: we defined the bucket such that if a tuple is in the bucket, then so are all its rotations.\nMoreover, everything in the bucket is a rotation of $T$, because two tuples are in the bucket if and only if we can rotate one to get the other; equivalently, $A$ is in the bucket if and only if we can rotate it to get $T$.\n\nHow many such rotations are there? We claimed that there were $p$ of them.\nIndeed, the rotations are precisely $$(a_1, a_2, \\dots, a_p), (a_2, a_3, \\dots, a_p, a_1), \\dots, (a_{p-1}, a_p, a_1, \\dots, a_{p-2}), (a_p, a_1, a_2, \\dots, a_{p-1})$$\nand there are $p$ of those; are they all distinct?\nYes, they are, and this is because $p$ is prime (it fails when $p=8$, for instance, because $(1,1,2,2,1,1,2,2)$ can be rotated four places to give itself).\nIndeed, if we could rotate the tuple $T$ nontrivially (that is, strictly between $1$ and $p$ times) to get itself, then the integer $n$, the "number of places we rotated", must divide the integer "length of the tuple". [todo: explain this better]\nBut that tells us that $n$ divides the prime $p$, so $n$ is $1$ or $p$ itself, and so either the tuple is actually "the same element repeated $p$ times" (in the case $n=1$) %%note: But we're only considering $T$ which is not of this form!%%, or the rotation was the "stupid" rotation by $p$ places (in the case $n=p$).\n%%\n\nOK, so our buckets are of size $p$ exactly, or size $1$ exactly.\nWe're dividing up the members of $X$ - that is, $|G|^{p-1}$ things - into buckets of these size; and we already have one bucket of size $1$, namely $(e,e,\\dots,e)$.\nBut if there were no more buckets of size $1$, then we would have $p$ dividing $|G|^{p-1}$ and also dividing the size of all but one of the buckets.\nMixing together all the other buckets to obtain an uber-bucket of size $|G|^{p-1} - 1$, the total must be divisible by $p$, since each individual bucket was %%note:Compare with the fact that the sum of even numbers is always even; that is the case that $p=2$.%%; so $|G|^{p-1} - 1$ is divisible by $p$.\nBut that is a contradiction, since $|G|^{p-1}$ is also divisible by $p$.\n\nSo there is another bucket of size $1$.\nA bucket of size $1$ contains something of the form $(a,a,\\dots,a)$: that is, it has shown us an element of order $p$.', 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: [ 'cauchy_theorem_on_subgroup_existence' ], commentIds: [], questionIds: [], tagIds: [ 'needs_clickbait_meta_tag' ], relatedIds: [], markIds: [], explanations: [], learnMore: [], requirements: [], subjects: [], lenses: [], lensParentId: 'cauchy_theorem_on_subgroup_existence', 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: '17116', pageId: 'cauchy_theorem_on_subgroup_existence_intuitive', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-07-19 02:02:34', auxPageId: 'needs_clickbait_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '14966', pageId: 'cauchy_theorem_on_subgroup_existence_intuitive', userId: 'PatrickStevens', edit: '0', type: 'newParent', createdAt: '2016-06-30 15:51:58', auxPageId: 'cauchy_theorem_on_subgroup_existence', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '14964', pageId: 'cauchy_theorem_on_subgroup_existence_intuitive', userId: 'PatrickStevens', edit: '1', type: 'newEdit', createdAt: '2016-06-30 15:51:06', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }