Difference between revisions of "Greatest common divisor"

From Maths
Jump to: navigation, search
m
m
Line 8: Line 8:
 
===Co-prime===
 
===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"/>
 
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==
 
==See next==
 
* [[Euclidean algorithm]]
 
* [[Euclidean algorithm]]

Revision as of 08:28, 21 May 2015

Note: requires knowledge of what it means for a number to be a divisor of another.

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]

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.

See next

See also

References

  1. 1.0 1.1 The mathematics of ciphers, Number theory and RSA cryptography - S. C. Coutinho