{
  localUrl: '../page/euclidean_domain_is_pid.html',
  arbitalUrl: 'https://arbital.com/p/euclidean_domain_is_pid',
  rawJsonUrl: '../raw/5vj.json',
  likeableId: '3393',
  likeableType: 'page',
  myLikeValue: '0',
  likeCount: '1',
  dislikeCount: '0',
  likeScore: '1',
  individualLikes: [
    'EricBruylant'
  ],
  pageId: 'euclidean_domain_is_pid',
  edit: '5',
  editSummary: '',
  prevEdit: '4',
  currentEdit: '5',
  wasPublished: 'true',
  type: 'wiki',
  title: 'Euclidean domains are principal ideal domains',
  clickbait: 'A Euclidean domain is one where we may somehow perform the division algorithm; this gives us access to some of the nicest properties of the integers.',
  textLength: '4227',
  alias: 'euclidean_domain_is_pid',
  externalUrl: '',
  sortChildrenBy: 'likes',
  hasVote: 'false',
  voteType: '',
  votesAnonymous: 'false',
  editCreatorId: 'PatrickStevens',
  editCreatedAt: '2016-08-14 17:43:26',
  pageCreatorId: 'PatrickStevens',
  pageCreatedAt: '2016-08-14 11:00:25',
  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: '42',
  text: '[summary: The [-division_algorithm] is a fundamental property of the [48l integers], and it turns out that almost all of the nicest properties of the integers stem from the division algorithm. All [3gq rings] which have the division algorithm (that is, [euclidean_domain Euclidean domains]) are [5r5 principal ideal domains]: they have the property that every [ideal_ring_theory ideal] has just one generator.]\n\n[summary(Technical): Let $R$ be a [euclidean_domain]. Then $R$ is a [-5r5].]\n\nA common theme in [3gq ring theory] is the idea that we identify a property of the [48l integers], and work out what that property means in a more general setting.\nThe idea of the [euclidean_domain] captures the fact that in $\\mathbb{Z}$, we may perform the [-division_algorithm] (which can then be used to work out [5mw greatest common divisors] and other such nice things from $\\mathbb{Z}$).\nHere, we will prove that this simple property actually imposes a lot of structure on a ring: it forces the ring to be a [-5r5], so that every [ideal_ring_theory ideal] has just one generator.\n\nIn turn, this forces the ring to have [5vk unique factorisation] ([pid_implies_ufd proof]), so in some sense the [5rh Fundamental Theorem of Arithmetic] (i.e. the statement that $\\mathbb{Z}$ is a unique factorisation domain) is true entirely because the division algorithm works in $\\mathbb{Z}$.\n\nThis result is essentially why we care about Euclidean domains: because if we know a Euclidean function for an integral domain, we have a very easy way of recognising that the ring is a principal ideal domain.\n\n# Formal statement\n\nLet $R$ be a [euclidean_domain].\nThen $R$ is a [-5r5].\n\n# Proof\n\nThis proof essentially mirrors the first proof one might find in the concrete case of the integers, if one sat down to discover an integer-specific proof; but we cast it into slightly different language using an equivalent definition of "ideal", because it is a bit cleaner that way.\nIt is a very useful exercise to work through the proof, using $\\mathbb{Z}$ instead of the general ring $R$ and using "size" %%note:That is, if $n > 0$ then the size is $n$; if $n < 0$ then the size is $-n$. We just throw away the sign.%% as the Euclidean function.\n\nLet $R$ be a Euclidean domain, and say $\\phi: \\mathbb{R} \\setminus \\{ 0 \\} \\to \\mathbb{N}^{\\geq 0}$ is a Euclidean function.\nThat is,\n\n- if $a$ divides $b$ then $\\phi(a) \\leq \\phi(b)$;\n- for every $a$, and every $b$ not dividing $a$, we can find $q$ and $r$ such that $a = qb+r$ and $\\phi(r) < \\phi(b)$.\n\nWe need to show that every [ideal_ring_theory ideal] is principal, so take an ideal $I \\subseteq R$.\nWe'll view $I$ as the [5r6 kernel] of a [ring_homomorphism homomorphism] $\\alpha: R \\to S$; recall that this is the proper way to think of ideals. ([5r9 Proof of the equivalence.])\nThen we need to show that there is some $r \\in R$ such that $\\alpha(x) = 0$ if and only if $x$ is a multiple of $r$.\n\nIf $\\alpha$ only sends $0$ to $0$ (that is, everything else doesn't get sent to $0$), then we're immediately done: just let $r = 0$.\n\nOtherwise, $\\alpha$ sends something nonzero to $0$; choose $r$ to be nonzero with minimal $\\phi$.\nWe claim that this $r$ works.\n\nIndeed, let $x$ be a multiple of $r$, so we can write it as $ar$, say.\nThen $\\alpha(ar) = \\alpha(a) \\alpha(r) = \\alpha(a) \\times 0 = 0$.\nTherefore multiples of $r$ are sent by $\\alpha$ to $0$.\n\nConversely, if $x$ is *not* a multiple of $r$, then we can write $x = ar+b$ where $\\phi(b) < \\phi(r)$ and $b$ is nonzero. %%note: The fact that we can do this is part of the definition of the Euclidean function $\\phi$.%%\nThen $\\alpha(x) = \\alpha(ar)+\\alpha(b)$; we already have $\\alpha(r) = 0$, so $\\alpha(x) = \\alpha(b)$.\nBut $b$ has a smaller $\\phi$-value than $r$ does, and we picked $r$ to have the *smallest* $\\phi$-value among everything that $\\alpha$ sent to $0$; so $\\alpha(b)$ cannot be $0$, and hence nor can $\\alpha(x)$.\n\nSo we have shown that $\\alpha(x) = 0$ if and only if $x$ is a multiple of $r$, as required.\n\n# The converse is false\n\nThere do exist principal ideal domains which are not Euclidean domains: $\\mathbb{Z}[\\frac{1}{2} (1+\\sqrt{-19})]$ is an example. ([Proof.](http://www.maths.qmul.ac.uk/~raw/MTH5100/PIDnotED.pdf))\n',
  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: [
    'algebraic_ring'
  ],
  commentIds: [],
  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: '18734',
      pageId: 'euclidean_domain_is_pid',
      userId: 'PatrickStevens',
      edit: '5',
      type: 'newEdit',
      createdAt: '2016-08-14 17:43:26',
      auxPageId: '',
      oldSettingsValue: '',
      newSettingsValue: ''
    },
    {
      likeableId: '0',
      likeableType: 'changeLog',
      myLikeValue: '0',
      likeCount: '0',
      dislikeCount: '0',
      likeScore: '0',
      individualLikes: [],
      id: '18733',
      pageId: 'euclidean_domain_is_pid',
      userId: 'PatrickStevens',
      edit: '4',
      type: 'newEdit',
      createdAt: '2016-08-14 17:41:41',
      auxPageId: '',
      oldSettingsValue: '',
      newSettingsValue: ''
    },
    {
      likeableId: '0',
      likeableType: 'changeLog',
      myLikeValue: '0',
      likeCount: '0',
      dislikeCount: '0',
      likeScore: '0',
      individualLikes: [],
      id: '18726',
      pageId: 'euclidean_domain_is_pid',
      userId: 'PatrickStevens',
      edit: '3',
      type: 'newEdit',
      createdAt: '2016-08-14 11:05:18',
      auxPageId: '',
      oldSettingsValue: '',
      newSettingsValue: ''
    },
    {
      likeableId: '0',
      likeableType: 'changeLog',
      myLikeValue: '0',
      likeCount: '0',
      dislikeCount: '0',
      likeScore: '0',
      individualLikes: [],
      id: '18725',
      pageId: 'euclidean_domain_is_pid',
      userId: 'PatrickStevens',
      edit: '2',
      type: 'newEdit',
      createdAt: '2016-08-14 11:01:30',
      auxPageId: '',
      oldSettingsValue: '',
      newSettingsValue: ''
    },
    {
      likeableId: '0',
      likeableType: 'changeLog',
      myLikeValue: '0',
      likeCount: '0',
      dislikeCount: '0',
      likeScore: '0',
      individualLikes: [],
      id: '18724',
      pageId: 'euclidean_domain_is_pid',
      userId: 'PatrickStevens',
      edit: '0',
      type: 'newParent',
      createdAt: '2016-08-14 11:01:25',
      auxPageId: 'algebraic_ring',
      oldSettingsValue: '',
      newSettingsValue: ''
    },
    {
      likeableId: '3392',
      likeableType: 'changeLog',
      myLikeValue: '0',
      likeCount: '1',
      dislikeCount: '0',
      likeScore: '1',
      individualLikes: [],
      id: '18722',
      pageId: 'euclidean_domain_is_pid',
      userId: 'PatrickStevens',
      edit: '1',
      type: 'newEdit',
      createdAt: '2016-08-14 11:00:25',
      auxPageId: '',
      oldSettingsValue: '',
      newSettingsValue: ''
    }
  ],
  feedSubmissions: [],
  searchStrings: {},
  hasChildren: 'false',
  hasParents: 'true',
  redAliases: {},
  improvementTagIds: [],
  nonMetaTagIds: [],
  todos: [],
  slowDownMap: 'null',
  speedUpMap: 'null',
  arcPageIds: 'null',
  contentRequests: {}
}