{ localUrl: '../page/bezout_theorem.html', arbitalUrl: 'https://arbital.com/p/bezout_theorem', rawJsonUrl: '../raw/5mp.json', likeableId: '3304', likeableType: 'page', myLikeValue: '0', likeCount: '1', dislikeCount: '0', likeScore: '1', individualLikes: [ 'EricBruylant' ], pageId: 'bezout_theorem', edit: '3', editSummary: '', prevEdit: '2', currentEdit: '3', wasPublished: 'true', type: 'wiki', title: 'Bézout's theorem', clickbait: 'Bézout's theorem is an important link between highest common factors and the integer solutions of a certain equation.', textLength: '1877', alias: 'bezout_theorem', externalUrl: '', sortChildrenBy: 'likes', hasVote: 'false', voteType: '', votesAnonymous: 'false', editCreatorId: 'PatrickStevens', editCreatedAt: '2016-09-22 06:26:22', pageCreatorId: 'PatrickStevens', pageCreatedAt: '2016-07-28 17:23:05', 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: '39', text: '[summary: Bézout's theorem states that if $a$ and $b$ are integers, and $c$ is an integer, then the equation $ax+by = c$ has integer solutions in $x$ and $y$ if and only if the [-5mw] of $a$ and $b$ divides $c$.]\n\nBézout's theorem is an important basic theorem of number theory.\nIt states that if $a$ and $b$ are integers, and $c$ is an integer, then the equation $ax+by = c$ has integer solutions in $x$ and $y$ if and only if the [-5mw] of $a$ and $b$ divides $c$.\n\n# Proof\n\nWe have two directions of the equivalence to prove.\n\n## If $ax+by=c$ has solutions\n\nSuppose $ax+by=c$ has solutions in $x$ and $y$.\nThen the highest common factor of $a$ and $b$ divides $a$ and $b$, so it divides $ax$ and $by$; hence it divides their sum, and hence $c$.\n\n## If the highest common factor divides $c$\n\nSuppose $\\mathrm{hcf}(a,b) \\mid c$; equivalently, there is some $d$ such that $d \\times \\mathrm{hcf}(a,b) = c$.\n\nWe have the following fact: that the highest common factor is a linear combination of $a, b$. ([hcf_is_linear_combination Proof]; this [extended_euclidean_algorithm can also be seen] by working through [euclidean_algorithm Euclid's algorithm].)\n\nTherefore there are $x$ and $y$ such that $ax + by = \\mathrm{hcf}(a,b)$.\n\nFinally, $a (xd) + b (yd) = d \\mathrm{hcf}(a, b) = c$, as required.\n\n# Actually finding the solutions\n\nSuppose $d \\times \\mathrm{hcf}(a,b) = c$, as above.\n\nThe [-extended_euclidean_algorithm] can be used (efficiently!) to obtain a linear combination $ax+by$ of $a$ and $b$ which equals $\\mathrm{hcf}(a,b)$.\nOnce we have found such a linear combination, the solutions to the integer equation $ax+by=c$ follow quickly by just multiplying through by $d$.\n\n# Importance\n\nBézout's theorem is important as a step towards the proof of [5mh Euclid's lemma], which itself is the key behind the [5rh].\nIt also holds in general [5r5 principal ideal domains].', 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', 'EricBruylant' ], childIds: [], parentIds: [ 'greatest_common_divisor' ], commentIds: [], questionIds: [], tagIds: [ 'math2', 'c_class_meta_tag', 'proof_meta_tag' ], 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: '19681', pageId: 'bezout_theorem', userId: 'PatrickStevens', edit: '3', type: 'newEdit', createdAt: '2016-09-22 06:26:22', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18983', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-20 13:07:34', auxPageId: 'c_class_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18982', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '2', type: 'newEdit', createdAt: '2016-08-20 13:06:54', auxPageId: '', oldSettingsValue: '', newSettingsValue: 'fixing links' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18981', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-20 13:06:34', auxPageId: 'proof_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18980', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'deleteTag', createdAt: '2016-08-20 13:06:09', auxPageId: 'needs_parent_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18978', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'deleteParent', createdAt: '2016-08-20 13:06:07', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18976', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'newParent', createdAt: '2016-08-20 13:06:06', auxPageId: 'greatest_common_divisor', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18215', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-03 15:52:05', auxPageId: 'needs_parent_meta_tag', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '18210', pageId: 'bezout_theorem', userId: 'EricBruylant', edit: '0', type: 'newTag', createdAt: '2016-08-03 15:44:55', auxPageId: 'math2', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17679', pageId: 'bezout_theorem', userId: 'PatrickStevens', edit: '0', type: 'newParent', createdAt: '2016-07-28 17:23:06', auxPageId: 'math', oldSettingsValue: '', newSettingsValue: '' }, { likeableId: '0', likeableType: 'changeLog', myLikeValue: '0', likeCount: '0', dislikeCount: '0', likeScore: '0', individualLikes: [], id: '17677', pageId: 'bezout_theorem', userId: 'PatrickStevens', edit: '1', type: 'newEdit', createdAt: '2016-07-28 17:23:05', auxPageId: '', oldSettingsValue: '', newSettingsValue: '' } ], feedSubmissions: [], searchStrings: {}, hasChildren: 'false', hasParents: 'true', redAliases: {}, improvementTagIds: [], nonMetaTagIds: [], todos: [], slowDownMap: 'null', speedUpMap: 'null', arcPageIds: 'null', contentRequests: {} }