Talk:Coprime integers

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
WikiProject Mathematics / Number (Rated C-class, High-Priority)
WikiProject iconThis article is within the scope of WikiProject Mathematics, a collaborative effort to improve the coverage of mathematics on Wikipedia. If you would like to participate, please visit the project page, where you can join the discussion and see a list of open tasks.
C-Class article C  This article has been rated as C-Class on the project's quality scale.
 High  This article has been rated as High-Priority on the project's priority scale.
Taskforce icon
This article is within the field of number theory.
 

Probability[edit]

The statement about probability of two integers being coprime is fairly misleading at the moment, as nothing has been said about how one chooses two integers "at random". Dmharvey Talk 5 July 2005 18:42 (UTC)

I added some details on the derivation of and what it means to choose two integers "at random." --Dantheox 20:51, 6 May 2006 (UTC)

There is a gap in the derivation which is easy to fill. To multiply the probabilities for distinct primes, we need to know these events are mutually independent. This is true precisely because we're talking about primes! —Preceding unsigned comment added by 70.49.117.165 (talk) 04:21, 2 April 2009 (UTC)

Properties of Coprimes[edit]

I'm very very far from being an expert on the subject, but I notice that the start of the section 'Properties' asserts:

There are a number of conditions which are equivalent to a and b being coprime:

There exist integers x and y such that ax + by = 1 (see Bézout's identity).

Really? 213.70.98.2 15:21, 1 November 2007 (UTC)

Really. Do see Bézout's identity if you want more details. -- EJ 10:53, 2 November 2007 (UTC)

And for matrices?[edit]

I think the terms "left-coprime" and "right-coprime" for matrices should also be discussed? User:Nillerdk (talk) 08:01, 18 July 2008 (UTC)

Figure[edit]

I like the figure showing that x and y must be coprime to be visible from the origin. But why not modify it to also show some integers (e.g (1,3) and (2,6)) that are not coprime? —Preceding unsigned comment added by 151.65.233.84 (talk) 11:18, 10 August 2008 (UTC)

References[edit]

Some references would be good ... Hardy and Wright would be good, and there's a nice elementary proof of 1/ζ(2) in Niven and Zuckerman, but I don't have those to hand right now. I've added Guy for his notation. Richard Pinch (talk) 05:36, 28 August 2008 (UTC)

Two references from H+W: N+Z didn't have it after all. Richard Pinch (talk) 06:47, 30 August 2008 (UTC)

What about coprime infinite sets?[edit]

At the current state, the article states "The concept of being relatively prime can also be extended to any finite set of integers". Unless I'm terribly wrong, the concept can easily be extended to infinite sets as well, can it not? 188.169.229.30 (talk) 18:39, 11 September 2012 (UTC)

Yes, it can, but I don’t think this is in common use.—Emil J. 09:20, 12 September 2012 (UTC)

Merge from pairwise coprime[edit]

The following discussion is closed. Please do not modify it. Subsequent comments should be made in a new section. A summary of the conclusions reached follows.
The result was merge from Pairwise coprime. -- Bryanrutherford0 (talk) 21:07, 23 November 2013 (UTC)

Can you add something here about "pairwise coprime" vs. gcd(a,b,c)=1? user:chas_zzz_brown 17:56 7 Oct 02 (UTC)

Indeed, the freestanding article pairwise coprime should be merged here as a section, where it would go much more naturally. I've stuck on a template accordingly. Joel B. Lewis (talk) 00:12, 11 June 2012 (UTC)
I agree.—Emil J. 12:04, 14 February 2013 (UTC)
I agree too. The pairwise coprime is a stub. Instead of expanding it, I think that merging it into here is much better and is much efficient. Mikelam98 (talk) 05:10, 13 August 2013 (UTC)
Totally agree. This discussion has been open since mid-2012 with no disagreements. I'm new to editing - how can we make this happen? Marc renault (talk) 11:33, 16 November 2013 (UTC)
I also support; I'll try shortly. Bryanrutherford0 (talk) 20:27, 23 November 2013 (UTC)

The above discussion is closed. Please do not modify it. Subsequent comments should be made in a new section.

Image dimensions[edit]

Have anyone notice that the first image of the left is a 5 and 10 unit not, 9 and 4 units. have someone counted??? — Preceding unsigned comment added by 177.81.187.38 (talk) 20:24, 19 December 2013 (UTC)

The 4 and 9 units are the number of spaces between pairs of points, not the number of grid points. —David Eppstein (talk) 20:59, 19 December 2013 (UTC)

Revert of "All pairs of prime numbers are coprime, but not all coprimes are prime numbers."[edit]

@Wcherowi: You reverted my change to the lead where I added the sentence "All pairs of prime numbers are coprime, but not all coprimes are prime numbers" with the rationale "This is confusing; coprime is not a type of number, it is a relationship between numbers."

However, that's exactly why I added that sentence, to emphasize that this is a relational property, and has nothing directly to do with prime numbers. I came to this article from Core War, which used the term relatively prime. I was thinking, "Huh? Either a number is prime or it isn't − what does 'relatively prime' mean?" I am decent at math (e.g. had to take "upper-division" math courses for my computer science degree and did well in them), but I was confused when reading the first paragraph of the lead here. I was stuck on the notion of a "coprime" being a type of prime (or relationship between primes), and I was thinking, "Wait, but then all primes would be coprimes with each other — I don't get it."

I realize now that the definition refers to integers, not primes, but it wasn't until looking at the example a couple of times and then backtracking that I understood the definition. I think it's highly likely that other people who know what a prime is (perhaps due to having a vague understanding of their involvement in encryption), but not a coprime, would be similarly confused when prime numbers aren't mentioned at all until the "Properties" section. I think differentiating coprimes from primes in the lead would be valuable, especially for people whose math expertise is even less than mine. Thoughts? --Dan Harkless (talk) 03:39, 14 September 2017 (UTC)

I agree with Wcherowi. Your addition is confusing. The statement, ". . . not all coprimes are prime numbers" is incorrect: there is no such object as a "coprime." "Coprime" is a property of two integers, clearly defined in the first line of the lead. "Relatively prime" is also clearly defined in the first line.—Anita5192 (talk) 04:11, 14 September 2017 (UTC)
@Anita5192: I was thinking "pairs" (or "sets") could be implied, as in my wording. If that's not correct usage, then how about changing that to "...but not all coprime pairs are prime numbers"? I already agreed that when I went back and re-read again after looking at the examples, the definition was clear, but it wasn't when I first read it, because, as I said, I got mentally tripped up based on my prior knowledge of prime numbers. Thus my conclusion that a sentence in the lead explicitly differentiating from prime numbers would be of value to people in my same boat (or even leakier ones 😉).
From taking a quick look at your user page and Wcherowi's, it seems like both of you are "math-heads", so you may not be thinking of this from the perspective of a naïve reader, and Wikipedia policy is that articles are supposed to be accessible to non-experts in the respective field, especially in article leads. --Dan Harkless (talk) 16:17, 14 September 2017 (UTC)
@Dan Harkless: Some of us "math-heads" also have a lot of experience trying to convey the meaning of mathematical ideas to those who don't already know them (we call such people students Face-smile.svg). In the term "coprime" the "co-" is taken to mean complementary in the following sense: If two integers are coprime then any prime number that divides one of them does not divide the other. The term is old and a bit of a stretch which is why various authors have come up with alternatives (relatively prime being the most common alternative). Your proposed change, "...not all coprime pairs are prime numbers" while true, does not really say anything about coprime pairs. It is akin to saying something like, "...not all electrical wires are made of iron" and I don't see the value in saying that. The relationship to prime numbers underlies everything here, but it is a bit more subtle than you are trying to make it.--Bill Cherowitzo (talk) 18:37, 14 September 2017 (UTC)
@Wcherowi: I'm not implying any judgments on anyone in this thread, but it was my experience throughout my educational career that only a few rare math teachers were good at conveying mathematical ideas to the average student. Most taught in a manner that was only accessible to students whose brains were likewise pre-wired to be talented at math, and the other students basically had to teach themselves from the texts, teach other, or be tutored. I didn't find a ratio of generally effective to generally ineffective teachers like this for any other subject I studied (and since I did find a few math teachers to be extremely effective, I don't think it's just that I was "bad at math").
Your electrical wires example is not equivalent, and I think the value of differentiating explicitly from prime numbers in the lead is evident. I'm not trying to mischaracterize the relationship with prime numbers, I'm trying to make the relationship more clear. Currently primes aren't mentioned in the lead at all, and people who may at first not process the definition of relative primes properly due to confusion stemming from prior knowledge of prime numbers are left to fend for themselves.
If you think the "All As are Bs, but not all Bs are As" construct is not the best way to call attention to the difference between the concepts, I'd be open to all kinds of other wordings. For instance, after "...of the two numbers is 1.", a sentence could be inserted saying something similar to 'Unlike prime numbers, a single number cannot be "relatively prime"—the term inherently expresses a relative property between two integers.'. If you think differentiating between the concepts in the lead explicitly is redundant or stating the obvious, I don't think you're properly considering the case of the average reader. --Dan Harkless (talk) 22:54, 14 September 2017 (UTC)

I do think there's some value in explaining the similar terminology between this article and that of prime numbers, which we don't really do now. But I think your attempt at this confuses more than enlightens. The important points are

  • It is nonsensical to ask whether a single number is coprime. Coprimality is a relation between pairs of numbers, not a property of individual numbers.
  • Being prime does not tell you anything useful about being coprime. It is possible for two coprime numbers to both be composite, and it is possible for two numbers to be non-coprime even though one or both of them is prime.
  • Coprime pairs of numbers are called coprime or relatively prime because [insert reason for why the similar terminology]

Instead, your attempted explanation is technically incorrect (the pair p,p of two equal prime numbers is not coprime even though both numbers in the pair are prime), adds confusion over the first point, and by saying "it's sometimes the same and sometimes different" doesn't make the second point that it's different strongly enough. —David Eppstein (talk) 23:48, 14 September 2017 (UTC)

@David Eppstein: Thanks, David. The case of a pair of the same prime hadn't occurred to me. My original attempt definitely needed to be reverted, given that. So given your first sentence and your first bulletpoint, it sounds like you would support my most recent suggestion:
For instance, after "...of the two numbers is 1.", a sentence could be inserted saying something similar to 'Unlike prime numbers, a single number cannot be "relatively prime"—the term inherently expresses a relative property between two integers.'.
Unless anyone objects, I'll add that within the next day or so. Oh, and I'm not ignoring your second and third bulletpoints, but I'm not sure the second one needs to be in the lead, and I'm okay with the third one being implied rather than explicit, as long as there is some differentiating mention of prime numbers. At the risk of saying this before the discussion is actually over, thanks to all for your thoughts and your mathematical insight. --Dan Harkless (talk) 21:18, 15 September 2017 (UTC)
@Dan Harkless: I don't think your suggestion works, in part because you are trying to describe something by saying what it is not. (I know that you won't like this analogy any better, but ...) It's like describing a statue as a block of marble with some pieces missing. We can not hope to address every possible source of confusion of every reader and according to WP:NOTTEXTBOOK we shouldn't even try to do so. I also do not see the point that you are trying to make as a major stumbling block for readers coming to this page, but since the first three lines are very redundant we can probably sneak in some reference to primes that I hope will deal with your issue.--Bill Cherowitzo (talk) 22:02, 15 September 2017 (UTC)
I think the lead is clear as it currently is, but it is very redundant. All it really needs is the first line: "In number theory, two integers a and b are said to be relatively prime, mutually prime,[1] or coprime (also spelled co-prime) if the only positive integer (factor) that divides both of them is 1." —Anita5192 (talk) 22:43, 15 September 2017 (UTC)
Bill, I'm not trying to describe relative primes by saying what they're not. I'm just trying to allay possible confusion between relative primes and prime numbers early on, since prime numbers are a much more well-known concept, and the "relatively" in "relatively prime" can be misconstrued as a matter of degree rather than expressing a relation, as in the case that puzzled me and made come check out the page. And you're right, I think your analogy is again not applicable, because its purpose is not to prevent terminology confusion (e.g. between "marble" and "marbles"). Of course we can't hope to address every possible source of confusion, but I think putting in some mention of prime numbers for people familiar with them but not coprimes is not some incredibly niche case.
I agree that the second and third sentence of the lead (though not the following ones) are redundant with the first and don't particularly lend to increased understanding. How about if the second and third sentences were removed, and replaced with:
This relation between two integers is an extension of the concept of a prime number, which is a single integer greater than 1 that has no positive divisors other than 1 and itself.
That would also address David's third bulletpoint. --Dan Harkless (talk) 02:04, 16 September 2017 (UTC)
Greetings all. I have to agree with Anita5192; I think part of the confusion of the lead is the fact that there may be too much information in it rather than too little. The examples are good but I am not sure that they belong in the lead. Cthomas3 (talk) 02:16, 16 September 2017 (UTC)
Are these comments relative to the latest version of the lead? I've made some changes.--Bill Cherowitzo (talk) 03:09, 16 September 2017 (UTC)
Thanks, Bill. No, I'd reloaded the Talk page directly without looking at my Watchlist. First off, I'm glad you moved the notation discussion to down below the example, which I was thinking of suggesting. I'm happy to have any mention of prime numbers in the lead, but your "Consequently, any prime number that divides one does not divide the other." seems like it doesn't do anything to aid understanding, since the stated property is true of any positive integer greater than 1. I think my suggestion of:
This relation between two integers is an extension of the concept of a prime number, which is a single integer greater than 1 that has no positive divisors other than 1 and itself.
or something close to it would be more helpful to the average reader in aiding understanding. --Dan Harkless (talk) 01:00, 17 September 2017 (UTC)
Saying that it's "an extension of the concept of a prime number" requires a published source that clearly explains in what sense it is meant that it is an extension. Otherwise we would be doing original research. —David Eppstein (talk) 01:39, 17 September 2017 (UTC)

Hmm. I didn't think that'd be a controversial wording. If you go back to Euclid's Elements, he defines them as (Richard Fitzpatrick translation):

11. A prime number is one (which is) measured by a unit alone.
12. Numbers prime to one another are those (which are) measured by a unit alone as a common measure.

So it seems reasonable to me to consider the n-item prôtos case an extension of the one-item prôtos case. If that seems like original research to you, though, we could just say:

This relation between two integers is similar to the concept of a prime number, which is a single integer greater than 1 that has no positive divisors other than 1 and itself.

Or "resembles" instead of "is similar to", if you prefer. --Dan Harkless (talk) 02:51, 17 September 2017 (UTC)

I am getting confused by your insistence on this point. Being relatively prime is a very simple concept and your attempt to tie it to a generalization of primes is a very abstract way of looking at the situation. You are doing no reader any service by this. David is correct in that this would require a citation to show that it was not original research, and I don't think you will be able to find any. My inclusion of primes in the second sentence was meant to make the term "coprime" seem like a reasonable choice and it is no more than a paraphrase of the first property given in the next section. The more general statement follows from it by applying the Fundamental Theorem of Arithmetic, which I assume that anyone familiar with prime numbers would be aware of, and these are the readers that you seemed to be concerned about.--Bill Cherowitzo (talk) 04:48, 17 September 2017 (UTC)
I think your confusion stems from the fact that you are stuck on the notion that I'm trying to define coprimes with my sentence. I am not. I am comparing and contrasting with "prime number", which is a very similar term with a similar definition, to help prevent confusion and ensure that the definition of coprimes is properly processed by readers who don't consider each new concept in a vacuum.
Do you honestly believe that my revised version, "This relation between two integers is similar to the concept of a prime number, which is a single integer greater than 1 that has no positive divisors other than 1 and itself.", would require a citation to not be considered original research...? I don't see how the property in your sentence shows that "coprime" is natural terminology. If that is your intent with that sentence, that seems much more like original research than simply acknowledging that the two similarly named concepts also have similar definitions (with an important distinguishing difference). --Dan Harkless (talk) 09:41, 17 September 2017 (UTC)
Similarity appears to be in the eyes of the beholder. I understand what you are saying and I am not claiming that it is incorrect, however, if it was a good clarifying statement I am sure that some author would have used it by now (given that the concept has been around since Euclid). I see nothing in the literature and I do not see any support for your position on this talk page. I think it is time to give it a rest. --Bill Cherowitzo (talk) 18:34, 17 September 2017 (UTC)

References

  1. ^ Eaton, James S. Treatise on Arithmetic. 1872. May be downloaded from: https://archive.org/details/atreatiseonarit05eatogoog

Awkward wording (a.k.a., "Huh?!" )[edit]

From the text:

"...As specific examples, 14 and 25 are coprime, being commonly divisible only by 1, while 14 and 21 are not coprime, because they are both divisible by 7..."

Huh?!?! If you're trying to say that "14 and 25 are coprime, sharing no factors in common between them except 1," then for God's sake, please say that! I puzzled over that text uncomprehendingly for a good two minutes, trying to decipher the odd phrase commonly divisible, which I recall seeing nowhere else; it was only when I stopped ruminating on the first example long enough to take in the second, counterexample, that understanding finally came. Good grief! The Grand Rascal (talk) 08:31, 28 September 2020 (UTC)

TheGrandRascal, I agree. "Commonly divisible" is not a common phrase for saying "having a common divisor". I have fixed it. D.Lazard (talk) 08:51, 28 September 2020 (UTC)
[a] By chance, I read that a few days ago and found it perfectly understandable. The "proposed" version is also ok. [b] commonly divisible seems to be used: see (https://www.khanacademy.org/math/pre-algebra/pre-algebra-factors-multiples/pre-algebra-prime-factorization-prealg/v/common-divisibility-examples). LMSchmitt 09:33, 28 September 2020 (UTC)
Indeed, that's because it's a completely standard English language construction -- there's nothing jargony or obscure at all about it. --JBL (talk) 11:32, 28 September 2020 (UTC)
JayBeeEll, it is grammatically correct, but semantically confusing. In mathematics, one must always take care when words have a mathematical meaning that differ from their common (usual) meaning. In the case of "common divisor", "common" refers to "common to two integers". In "commonly divisible", "commonly" is not used in its common meaning, but is used in place of "simultaneously divisible". So the formulation is confusing. By the way Khan Academy is not a reliable source for attesting a common use of "commonly divisible" D.Lazard (talk) 14:35, 28 September 2020 (UTC)
To be clear: this is just forum-y chatting, I am not trying to get anyone to change the article. The most common meaning of "common" is probably "widespread; public". The second-most common meaning of "common" is "shared; joint". Both of these can be turned into an adverb: "commonly" meaning "frequently; often; usually" and "commonly" meaning "in common; jointly". The phrase "greatest common divisor" uses the second meaning of the adjective "common", and the phrase "commonly divisible" uses the corresponding adverbial form. Anyone who understands the phrase "greatest common divisor" should, by applying standard rules of English, be able to convert it to the corresponding adverbial form, and vice-versa. P.S. I feel like it is strangely common (at least, this is not the first time) for you, a PhD mathematician who writes English well but not fluently, to lecture me, a PhD mathematician who writes English fluently, on basic points of English grammar and its use in mathematics. I promise that I will never attempt to lecture you on fine points of French usage or grammar! --JBL (talk) 12:51, 29 September 2020 (UTC)

Well. It may not be my recommended wording, but at least it's a lot clearer than it was! Thanks. 😊 The Grand Rascal (talk) 09:13, 28 September 2020 (UTC)