{"action":"created","issue":{"url":"https://api.github.com/repos/non/spire/issues/568","repository_url":"https://api.github.com/repos/non/spire","labels_url":"https://api.github.com/repos/non/spire/issues/568/labels{/name}","comments_url":"https://api.github.com/repos/non/spire/issues/568/comments","events_url":"https://api.github.com/repos/non/spire/issues/568/events","html_url":"https://github.com/non/spire/issues/568","id":151315645,"number":568,"title":"\"Fields are euclidean rings\" and the lawless % operator","user":{"login":"denisrosset","id":93707,"avatar_url":"https://avatars.githubusercontent.com/u/93707?v=3","gravatar_id":"","url":"https://api.github.com/users/denisrosset","html_url":"https://github.com/denisrosset","followers_url":"https://api.github.com/users/denisrosset/followers","following_url":"https://api.github.com/users/denisrosset/following{/other_user}","gists_url":"https://api.github.com/users/denisrosset/gists{/gist_id}","starred_url":"https://api.github.com/users/denisrosset/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/denisrosset/subscriptions","organizations_url":"https://api.github.com/users/denisrosset/orgs","repos_url":"https://api.github.com/users/denisrosset/repos","events_url":"https://api.github.com/users/denisrosset/events{/privacy}","received_events_url":"https://api.github.com/users/denisrosset/received_events","type":"User","site_admin":false},"labels":[],"state":"open","locked":false,"assignee":null,"milestone":null,"comments":7,"created_at":"2016-04-27T07:18:47Z","updated_at":"2016-05-09T11:40:45Z","closed_at":null,"body":"I realized that the inclusion \"every field is an Euclidean domain\" means that all methods on `EuclideanRing` should have default implementations to satisfy the yet-to-be-tested algebraic laws on these structures.\r\n\r\nI'm not an expert in ring structures and the introductory (e.g. Wikipedia) leave me somewhat unsatisfied.\r\n\r\nI'm opening this issue to do a bit of brainstorming and clean-up. After discussion, I'll propose a PR incorporating the definition and tests.\r\n\r\nEvery field is an Euclidean domain, and as `x/y` can be computed for any `y!=0`, `mod` is always equal to 0. See discussion [here](http://math.stackexchange.com/questions/1691254/how-to-show-every-field-is-a-euclidean-domain), mathematical definition [here](https://en.wikipedia.org/wiki/Euclidean_domain), also [discussion here](http://math.stackexchange.com/questions/246049/how-do-i-prove-whether-something-is-a-euclidean-domain).\r\n\r\nThus the implementations of `mod`, `quot` and `quotmod` become trivial.\r\n\r\nNow, I could not find resources on how to define `gcd` and `lcm`. What I know:\r\n\r\n- there is a universal construction for all fields, as the inclusion shows. This inclusion can use all properties of fields, including the existence of a unit for multiplication, and the fact that all non-zero elements have a multiplicative inverse.\r\n\r\n- we cannot assume the existence of an order, because the same construction should apply to non-ordered fields such as the complex numbers.\r\n\r\nI would be tempted to define `gcd(x,y) = 1`  and `lcm(x,y) = x * y` to satisfy the axioms of [GCD domains](https://en.wikipedia.org/wiki/GCD_domain).\r\n\r\nProblem: this clashes with the usual definition of the `%` for doubles, which is inspired by a generalization of the property \"how many times this quantity fits in that quantity\" on floating point numbers.\r\n\r\nI'm not sure what's the best way to proceed here. If we come to the conclusion that `def mod(x: Double, y: Double) = 0.0` is the only construction that obey the GCD domain laws, then the result is going to be quite confusing for users.\r\n\r\nOn the other hand, `EuclideanRing` does not have any laws yet, which should be corrected."},"comment":{"url":"https://api.github.com/repos/non/spire/issues/comments/217842219","html_url":"https://github.com/non/spire/issues/568#issuecomment-217842219","issue_url":"https://api.github.com/repos/non/spire/issues/568","id":217842219,"user":{"login":"denisrosset","id":93707,"avatar_url":"https://avatars.githubusercontent.com/u/93707?v=3","gravatar_id":"","url":"https://api.github.com/users/denisrosset","html_url":"https://github.com/denisrosset","followers_url":"https://api.github.com/users/denisrosset/followers","following_url":"https://api.github.com/users/denisrosset/following{/other_user}","gists_url":"https://api.github.com/users/denisrosset/gists{/gist_id}","starred_url":"https://api.github.com/users/denisrosset/starred{/owner}{/repo}","subscriptions_url":"https://api.github.com/users/denisrosset/subscriptions","organizations_url":"https://api.github.com/users/denisrosset/orgs","repos_url":"https://api.github.com/users/denisrosset/repos","events_url":"https://api.github.com/users/denisrosset/events{/privacy}","received_events_url":"https://api.github.com/users/denisrosset/received_events","type":"User","site_admin":false},"created_at":"2016-05-09T11:40:45Z","updated_at":"2016-05-09T11:40:45Z","body":"See [work in progress here](https://github.com/denisrosset/algebra/blob/master/EuclidianRing.md)\r\n"}}