Talk:Greatest common divisor

1. REDIRECT Template:Archives

Adding new "other method"

Hello, there is another way of expressing the gcd of two natural numbers a and b.

$\gcd (a,b)=a-b-ab+2\sum _{k=1}^a\lfloor \frac{b}{a}k\rfloor$

I give a source. Some people claim it can´t be verified. But give a couple of sources.

Youtube-Video -> not accepted PDF -> not accepted Blogpost on a webpage -> not accepted

Other mathematical articles have also youtube sources. But they exist. — Preceding unsigned comment added by Scityscit (talk • contribs) 18:12, 18 March 2021 (UTC)

What do I have to do that my editing will be accpeted? Is it okay, if I put a "Proof"-Box in the article?

Or can I create a entry in "proofwiki"?

Best regards

--Scityscit (talk) 19:00, 18 March 2021 (UTC)

There are countless results about GCD. It would be pointless to include all of them. We rely on coverage by reliable sources to guide our editorial judgement about which ones to include in the article. If most treatments of GCD mention Pick's Theorem, then that's a good sign that we should include it here. As far as I can tell, that is not the case. Conversely, if only a few reliable sources mention them together, we probably shouldn't cover them together.

You should also be aware of WP's rules about constructive and collaborative editing. If there is a disagreement about the content of a page, you should discuss it on the Talk page, and not repeatedly re-insert your preferred version, especially when three different editors object. See Wikipedia:Edit warring... but apparently you're aware of WP:3RR, because you stopped after three reverts. --Macrakis (talk) 20:04, 18 March 2021 (UTC)

Name for a number's set of prime factors?

Isn't there a name for the set comprising a number's prime factors (e.g., the two sets shown in the Venn diagram of in the "Using prime factorizations" subsection)? I see nothing in the various prime/composite-related articles. BMJ-pdx (talk) 14:37, 26 July 2021 (UTC)

"The prime divisors of Template:Mvar" is a phrase that is commonly considered as convenient. Not all sets needs to be named, and using too much set theory leads to pedantry. Compare "Template:Mvar is a prime divisor of Template:Mvar" and "Template:Mvar is a member of the set of the prime divisors of Template:Mvar". Both sentences are correct, but the second one requires to know what is a set in mathematics, and what is a member of a set. Note that the concept of set is less than 150 years old, while the concept of prime divisor is more than 2000 years old. D.Lazard (talk) 15:12, 26 July 2021 (UTC)

My motivation came from how simple a definition of GCD could be with a simple name for such: "GCD is the product of the members of the intersection of ..." (much simpler still in symbolic form). Also, it could be used in a relatively simple proof that the square root of 2 (et. al) is irrational. Granted, all possible without a nice terse name. BMJ-pdx (talk) 15:48, 3 August 2021 (UTC)

"the two sets shown in the Venn diagram of in the "Using prime factorizations" subsection": This Venn diagramm does not show any set, but multisets, as there are repeated elements in them, which is not possible for sets. Another example that using set theory when it is not needed may be confusing. D.Lazard (talk) 16:10, 3 August 2021 (UTC)

I stand corrected. However, I don't share your apparent disdain of set theory :-) (As an aside, introduction to set theory was a feature of the "New Math" that started to be taught in the 1960's, and was musically satirized by mathematician Tom Lehrer.) BMJ-pdx (talk) 16:38, 3 August 2021 (UTC)

"Grootste gemene deler" listed at Redirects for discussion

File:Information.svg An editor has identified a potential problem with the redirect Grootste gemene deler and has thus listed it for discussion. This discussion will occur at Wikipedia:Redirects for discussion/Log/2022 February 13#Grootste gemene deler until a consensus is reached, and readers of this page are welcome to contribute to the discussion. ~~~~
User:1234qwer1234qwer4 (talk) 02:40, 13 February 2022 (UTC)

gcd(0,0)

I always thought $\gcd (0,0)=1$, but anyway Properties 3 and 5 are conflicting.

3) gcd(a, 0) = |a|, for a ≠ 0, since any number is a divisor of 0, and the greatest divisor of a is |a|.[2][5] This is usually used as the base case in the Euclidean algorithm.

5) If m is a non-negative integer, then gcd(m⋅a, m⋅b) = m⋅gcd(a, b).

Darcourse (talk) 10:20, 21 February 2022 (UTC)

There is no conflict. However the second assertion supposes that gcd(0, 0) is defined as being 0. So, I have replaced "non-negative" by "positive" in the article. If gcd(0, 0) would be defined as 0, the second assertion could be left as it was, and "for a ≠ 0" could be removed from the first one.

Note that when gcd(0, 0) is defined, this is always as 0, as this is the only value that allows extending all properties to this case. D.Lazard (talk) 11:22, 21 February 2022 (UTC)

Euclid's algorithm principle

Let a and b be distinct natural numbers. Then gcd(a, b) =gcd(|a-b|, min(a, b)) 202.168.85.234 (talk) 05:04, 13 June 2022 (UTC)

Why not state the (extremely simple) formulas in generality?

The section Using prime factorizations begins with this:

" Greatest common divisors can be computed by determining the prime factorizations of the two numbers and comparing factors. For example, to compute Template:Math, we find the prime factorizations 48 = 2⁴ · 3¹ and 180 = 2² · 3² · 5¹; the GCD is then 2^min(4,2) · 3^min(1,2) · 5^min(0,1) = 2² · 3¹ · 5⁰ = 12 The corresponding LCM is then 2^max(4,2) · 3^max(1,2) · 5^max(0,1) = 2⁴ · 3² · 5¹ = 720."

But the formulas for GCD and LCM of two integers are very important in number theory.

There's nothing wrong with examples, but:

Why not just state the general formulas for GCD and LCM instead of solely giving examples???

I hope someone knowledgeable about this subject can fix this.

The the dismissive last sentence of this section:

"In practice, this method is only feasible for small numbers, as computing prime factorizations takes too long"

is wholly inappropriate since "practice" means entirely different things — especially in a case like this — to pure mathematicians as compared with applied mathematicians.

I hope someone knowledgeable about this subject can fix this, too. 2601:200:C082:2EA0:19F5:EB17:C336:8B35 (talk) 05:13, 18 March 2024 (UTC)

HCF (abbreviation)

I was surprised to see in the edit history that the abbreviation HCF had been removed from the article. It's very common here in the UK, as a quick web search reveals, though I wouldn't like to say whether it's more or less common than GCD. (When I see GCD, I have to remind myself that it's a synonym for HCF.)

It was clumsily introduced in the article, and doesn't need actually using in the text, but I think its existence needs at least mentioning. Maybe it's less common among academic mathematicians than the general public—I've no idea—but it's a term I think plenty of readers will be familiar with and indeed be looking up when they land on this article. Musiconeologist (talk) 00:43, 3 April 2024 (UTC), ed. 01:38, 3 April 2024 (UTC)

Imprecise definition

The article defines the GCD as "the largest positive integer that divides each of the integers."; this is fatally incomplete because any number is divisible by any number, say 8 is divisible by 500; the result is not an integer but the definition in the article does not state this. The definition is more precisely stated as "the largest positive integer that divides each of the integers into integers." — Preceding unsigned comment added by 37.152.237.108 (talk) 09:06, 10 July 2024 (UTC)

The definition is unambiguous, since the word "divides" is linked to a definition that excludes divisions with non-integer results. D.Lazard (talk) 09:30, 10 July 2024 (UTC)

Sum GCD function

Should this property be included? The summatory function is called Pillai's arithmetical function apparently. https://oeis.org/A018804

$\sum _{k=1}^n\gcd (k,n)=\sum _{d|n}d\phi \left(\frac{n}{d}\right)=\mathrm{Id}*\phi$

https://cs.uwaterloo.ca/journals/JIS/VOL4/BROUGHAN/gcdsum.pdf Wqwt (talk) 04:50, 30 July 2024 (UTC)

Existence of GCD and LCM

Let $a,b$ be two elements in an integral domain. Consider the following properties:

(i) The ideal $(a,b)$ is principal (i.e., $a,b$ has a GCD in the sense of Bézout);

(ii) $a,b$ has a LCM;

(ii') The ideal $(a)\cap (b)$ is principal;

(iii) $a,b$ has a GCD,

then we have (i)$\Rightarrow$(ii)$\Rightarrow$(iii), and (ii)$\iff$(ii').

Proof. (i)$\Rightarrow$(ii). Write $(a,b)=(c)$, then $(a),(b)\subset (c)$ implies that $c\mid a,b$, so we can write $a=a^{\prime }c$ and $b=b^{\prime }c$. Let's show that the LCM of $a,b$ is $a^{\prime }{b}^{\prime }c$, which is already a common multiple of $a$ and of $b$. WLOG suppose that $c\ne 0$ (otherwise we have $a=0$, $b=0$). There exists $x,y$ such that $ax+by=c$, so $a^{\prime }x+b^{\prime }y=1$ since we are in an integral domain. Suppose that $a\mid m$ and $b\mid m$. Write $m=a{m}^{\prime }$, then we have $b^{\prime }c\mid a^{\prime }c{m}^{\prime }$ (again because we are in an integral domain), so $b^{\prime }\mid a^{\prime }{m}^{\prime }$, which implies that $b^{\prime }\mid m^{\prime }(a^{\prime }x+b^{\prime }y)=m^{\prime }$. We conclude that $a^{\prime }{b}^{\prime }c\mid m$.

(ii)$\Rightarrow$(iii). If $m$ is a LCM of $a$ and $b$, then we can verify that $ab/m$ is a GCD of $a$ and $b$.

(ii)$\Rightarrow$(ii'). Let $m$ be a LCM of $a$ and $b$, then let's show that $(a)\cap (b)=(m)$. We have $(m)\subset (a),(b)$, so $(m)\subset (a)\cap (b)$. Conversely, if $m^{\prime }\in (a)\cap (b)$, then $a,b\mid m^{\prime }$, so $m\mid m^{\prime }$, which implies that $m^{\prime }\in (m)$.

(ii')$\Rightarrow$(ii). Let $(a)\cap (b)=(m)$, then let's show that $m$ be a LCM of $a$ and $b$, which is evidently a common multiple of $a$ and of $b$. Suppose that $a,b\mid m^{\prime }$, then $m^{\prime }\in (m)$, so $m\mid m^{\prime }$.

In general, neither converse of (i)$\Rightarrow$(ii)$\Rightarrow$(iii) is true.

(ii) does not imply (i): In $\mathbb{\mathbb{Z}}[X]$, the ideal $(2,X)$ is not princpal.

(iii) does not imply (ii): In $\mathbb{\mathbb{Q}}[X^2,X^3]$, the elements $X^2$ and $X^3$ have GCD $1$, but they don't have a LCM: if they had one, then that LCM must be divisible by $X^5$ and by $X^6$, but $X^5$ and $X^6$ have GCD $1$.

An integer domain where (i) is true for every pair of elements is called a Bézout domain. It turns out (a nontrivial result!) that if (iii) is true for every pair of elements, then this is also the case for (ii). Such an integer domain is called a GCD domain. 129.104.241.34 (talk) 19:04, 29 November 2024 (UTC)