Add gcd and lcm for Rational

[Paalon]

There are no functions for Rational.

gcd(x::Rational, y::Rational) = gcd(x.num, y.num) // lcm(x.den, y.den)
lcm(x::Rational, y::Rational) = lcm(x.num, y.num) // gcd(x.den, y.den)

gcd(a::Rational, b::Rational...) = gcd(a, gcd(b...))
lcm(a::Rational, b::Rational...) = lcm(a, lcm(b...))

[thofma]

Why not gcd(x::Rational, y::Rational) = one(typeof(x)) and lcm(x::Rational, y::Rational) = one(typeof(x))?

[Paalon]

I can't grasp what you mean. If we define gcd(x::Rational, y::Rational) = one(typeof(x)) then gcd(1//3, 2//5) == 1//1 but gcd(1//3, 2//5) == 1//15.

https://en.wikipedia.org/wiki/Least_common_multiple#Formulas

[thofma]

Since the rationals are a field, the gcd will always be 1 (we can multiply the gcd with units).

[thofma]

The Wikipedia page describes the gcd and lcm of positive rational integers. This is unrelated.

[Paalon]

OK, I understand. Julia's Rational is the rational field, so gcd and lcm of them are trivial but I want to denote the gcd and lcm of rationals as gcd domain (I don't know how to say).

[sostock]

FWIW, I think implementing gcd/gcdx/lcm like originally suggested (so that gcd(1//3, 2//5) == 1//15) would be worthwhile because it should lead to the correct behavior of intersect(::StepRange, ::StepRange), which currently errors for StepRange{<:Rational}:

julia> intersect(1//3:2//3:11//3, 0//1:1//2:4//1) # should be 1//1:2//1:3//1
ERROR: MethodError: no method matching lcm(::Rational{Int64}, ::Rational{Int64})

However, for this to work, one would also need to implement gcdx(::Rational, ::Rational), not just gcd and lcm.

[KlausC]

See this gcd-stackexchange-2012, specially the last article about extension of gcd to rationals and more general:

Yes, your formula yields the unique extension of gcd from integers to rationals (fractions), presuming the natural extension of the divisibility relation from integers to rationals, i.e. for rationals r,s, we define r divides s, if s/r is an integer, in symbols r|s ⟺ s/r∈Z.

Wolfram Alpha/Mathematica seem to go follow the same way: gcd(1/3, 2/5)

[waldyrious]

IIUC #33910 implemented this. Can someone with the right permissions close the issue?