Difference between revisions of "Greatest common divisor"
From Maths
m |
m |
||
| 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)}} | ||
| + | |||
| + | ==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"/> | ||
| + | |||
| + | ==See next== | ||
| + | * [[Euclidean algorithm]] | ||
| + | |||
| + | ==See also== | ||
| + | * [[Division algorithm]] | ||
| + | * [[Divisor]] | ||
| + | |||
| + | ==References== | ||
| + | <references/> | ||
{{Definition|Number Theory}} | {{Definition|Number Theory}} | ||
Revision as of 08:25, 21 May 2015
Note: requires knowledge of what it means for a number to be a divisor of another.
Definition
Given two positive integers, a,b∈N+, the greatest common divisor of a and b[1] is the greatest positive integer, d, that divides both a and b. We write:
- d=gcd(a,b)
Terminology
Co-prime
If for a,b∈N+ we have gcd(a,b)=1 then a and b are said to be co-prime[1]
See next
See also
References
- ↑ Jump up to: 1.0 1.1 The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho
