Difference between revisions of "Greatest common divisor"
m |
m |
||
| (2 intermediate revisions by the same user not shown) | |||
| Line 2: | Line 2: | ||
==Definition== | ==Definition== | ||
| − | {{ | + | Given two positive integers, {{M|a,b\in\mathbb{N}_+}}, the ''greatest common divisor'' of {{M|a}} and {{M|b}}<ref name="Crypt">The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho</ref> is the greatest positive integer, {{M|d}}, that [[Divisor|divides]] both {{M|a}} and {{M|b}}. We write: |
| + | * {{M|1=d=\text{gcd}(a,b)}} | ||
| + | |||
| + | ==Proper definition - UNCONFIRMED== | ||
| + | ===This section is Alec's own speculation - not yet verified=== | ||
| + | Using the [[Well-ordered principle]] (given the set of divisors is a finite set, the set has a maximum element, and the maximum is the same as the {{M|\text{Sup} }} of the set) we can state the {{M|\text{gcd} }} as follows: | ||
| + | * <math>\text{gcd}(a,b)=\text{sup}(\{n\in\mathbb{N}|n\text{ divides } a\}\cap\{n\in\mathbb{N}|n\text{ divides } b\})</math> | ||
| + | '''End of the unconfirmed part''' | ||
| + | ==Terminology== | ||
| + | ===Co-prime=== | ||
| + | If for {{M|a,b\in\mathbb{N}_+}} we have {{M|1=\text{gcd}(a,b)=1}} then {{M|a}} and {{M|b}} are said to be ''co-prime''<ref name="Crypt"/> | ||
| + | ====Coprime==== | ||
| + | Coprime is used by some authors, co-prime by others. I prefer the hyphenated form because to be ''co-something'' implies more than one thing is involved. You cannot have "a coprime number" but you can have a pair of co-prime numbers. | ||
| + | ==See next== | ||
| + | * [[Euclidean algorithm]] | ||
| + | |||
| + | ==See also== | ||
| + | * [[Division algorithm]] | ||
| + | * [[Divisor]] | ||
| + | |||
| + | ==References== | ||
| + | <references/> | ||
{{Definition|Number Theory}} | {{Definition|Number Theory}} | ||
Latest revision as of 08:33, 21 May 2015
Note: requires knowledge of what it means for a number to be a divisor of another.
Contents
Definition
Given two positive integers, [ilmath]a,b\in\mathbb{N}_+[/ilmath], the greatest common divisor of [ilmath]a[/ilmath] and [ilmath]b[/ilmath][1] is the greatest positive integer, [ilmath]d[/ilmath], that divides both [ilmath]a[/ilmath] and [ilmath]b[/ilmath]. We write:
- [ilmath]d=\text{gcd}(a,b)[/ilmath]
Proper definition - UNCONFIRMED
This section is Alec's own speculation - not yet verified
Using the Well-ordered principle (given the set of divisors is a finite set, the set has a maximum element, and the maximum is the same as the [ilmath]\text{Sup} [/ilmath] of the set) we can state the [ilmath]\text{gcd} [/ilmath] as follows:
- [math]\text{gcd}(a,b)=\text{sup}(\{n\in\mathbb{N}|n\text{ divides } a\}\cap\{n\in\mathbb{N}|n\text{ divides } b\})[/math]
End of the unconfirmed part
Terminology
Co-prime
If for [ilmath]a,b\in\mathbb{N}_+[/ilmath] we have [ilmath]\text{gcd}(a,b)=1[/ilmath] then [ilmath]a[/ilmath] and [ilmath]b[/ilmath] are said to be co-prime[1]
Coprime
Coprime is used by some authors, co-prime by others. I prefer the hyphenated form because to be co-something implies more than one thing is involved. You cannot have "a coprime number" but you can have a pair of co-prime numbers.
