Greatest common divisor

ImprimirCitar

In mathematics, the greatest common divisor (abbreviated GCD) of two or more integers is defined as the largest integer that divides them without leaving a remainder.

Precisions

The $a$ and $b$ two integers different from zero. If a number $c$ divide a $a$ and $b$ I mean, ${displaystyle c|a}$ and ${displaystyle c|b}$ We'll say $c$ That's it. common divider of $a$ and $b$ . Note that any two integers have common dividers. If the common dividers $a$ and $b$ It's only 1 and -1 then we'll say cousins among themselves.'

An integer d is called the greatest common divisor (G.C.D) of the numbers a and b when:

d is common divider of numbers a and b
d is divisible by any other common divider of numbers a and b.

Example:

12 is the mcd of 36 and 60. 12,36 and 12,60; in turn 12 is divisible by 1, 2, 3, 4, 6 and 12 that are common dividers of 36 and 60.

Calculation of the greatest common divisor

The three most commonly used methods for calculating the greatest common divisor of two numbers are:

By decomposition into prime factors

Main article: Integer factoring

The greatest common factor of two numbers can be found by determining the prime factorization of the two numbers and taking the common factors raised to the lowest power, the product of which will be the GCD.

Example: to calculate the greatest common divisor of 48 and 60, it is obtained by factoring them into prime factors.

{displaystyle {begin{array}{r|l}48&2\24&2\12&2\6&2\3&3\1&end{array}}}

{displaystyle 48=2^{4}cdot 3,}

{displaystyle {begin{array}{r|l}60&2\30&2\15&3\5&5\1&end{array}}}

{displaystyle 60=2^{2}cdot 3cdot 5,}

The GCD are the common factors with their smallest exponent, that is:

{displaystyle operatorname {MCD} (48;60)=2^{2}cdot 3=12}

In practice, this method only works for small numbers, generally taking too long to compute the prime factorization of any two numbers.

Using Euclid's algorithm

Main article: Euclides Algorithm

A more efficient method is Euclid's algorithm, which uses the division algorithm together with the fact that the GCD of two numbers also divides the remainder obtained from dividing the largest by the smallest.

Example 1:

If 60 is divided by 48 giving a quotient of 1 and a remainder of 12, the GCD will therefore be a divisor of 12. Then 48 is divided by 12 giving a remainder of 0, which means that 12 is the GCD. It can formally be described as:

{displaystyle operatorname {mcd} (a,0)=a}

{displaystyle operatorname {mcd} (a,b)=operatorname {mcd} (b,a,mathrm {mod} ,b).}

Example 2:

The GCD of 42 and 56 is 14. Indeed:

{displaystyle operatorname {mcd} (42,56)=14,}

operand:

{displaystyle {frac {42}{14}}=3;,quad {frac {56}{14}}=4}

Using the Least Common Multiple

The greatest common factor can also be calculated using the least common multiple. If a and b are nonzero, then the greatest common factor of a and b is obtained by following formula, involving the least common multiple of a and b:

{displaystyle operatorname {MCD} (250,150,320)={frac {acdot b}{operatorname {mcm} (a,b)}}}

GCD of three or more numbers

The common divisor maximum of three or more numbers can be defined using recursively: ${displaystyle operatorname {MCD} (a,b,c)=operatorname {MCD} (a,operatorname {MCD} (b,c))}$ .

Properties

Yeah. ${displaystyle operatorname {MCD} (a,b)=d}$ then. ${displaystyle operatorname {MCD} left({frac {a}{d}},{frac {b}{d}}right)=1}$
Yeah. ${displaystyle min mathbb {Z} }$ , ${displaystyle operatorname {MCD} (ma,mb)=|m|cdot operatorname {MCD} (a,b)}$
Yeah. ${displaystyle p}$ It's a prime number, then. ${displaystyle operatorname {MCD} (p,m)=p}$ or ${displaystyle operatorname {MCD} (m,p)=1}$
Yeah. ${displaystyle d=operatorname {MCD} (m,n), m=d'm'', n=d'n'', operatorname {MCD} (m'',n'')=1}$ , then ${displaystyle d=d'}$
Yeah. ${displaystyle d'}$ is a common divider $m$ and $n$ , then ${displaystyle d'mid operatorname {MCD} (m,n)}$
Yeah. ${displaystyle m=nq+r}$ , then ${displaystyle operatorname {MCD} (m,n)=operatorname {MCD} (n,r)}$
Yeah. ${displaystyle m=p_{1}^{alpha _{1}}cdots p_{k}^{alpha _{k}};,mathrm {y} ;,n=p_{1}^{beta _{1}}cdots p_{k}^{beta _{k}},;,alpha _{i},beta _{i}geq 0,;,i=1,...,k}$ , then:

{displaystyle operatorname {MCD} (m,n)=p_{1}^{operatorname {min} (alpha _{1},beta _{1})}cdots p_{k}^{operatorname {min} (alpha _{k},beta _{k})}}

The last property indicates that the greatest common divisor of two numbers is the product of their common prime factors raised to the lowest exponent.

Geometrically, the greatest common divisor of a and b is the number of integer coordinate points in the segment joining the points (0,0) and (a,b), excluding the (0,0).

Propositions

${displaystyle forall a, bin mathbb {Z} }$ ${displaystyle ni }$ ${displaystyle a, bneq 0}$ $exists !$ d ≥ 1 ${displaystyle ni }$ MCD(a, b) = d.
The M.C.D. of numbers a and b can be represented in linear combination of these numbers. This is (a, b) = ax + by
If two whole numbers are cousins to each other, i.e. your MCD = 1 or another notation (a,b) = 1, then there is representation Ma + nb = 1 where m and n are integers (Bézout Identity).
Yeah. a日本語bc and (a,b#1 will be a日本語c. In other words, if a number a divides a product from another two numbers and is pressed with one of them, then necessarily divides the other number or factor.
MCD(a, m) = 1 $land$ MCD((a) = 1 ${displaystyle Longrightarrow }$ MCD(a, (mn) = 1.
(a,b) is divisor of (a, bc)
t(a,b) = (ta, tb) for all t
Yes (m, b)= 1 then (am, b)= (a, b)
Yes (m,b)= 1, (am, n) = 1 then (am, bn) = (a, b)
For all x, (a, b) = (b, a) = (a, -b) = (a, b + ax)
" By definition, (0, 0) = 0 ". Thus the mcd would be defined in all ZxZ.
(a, b) = b if only b Δ a, (i.e. a multiple b).
Yes (a,b)= D, then (aⁿ, bⁿ) = Dⁿ
mZ + nZ = (m,n)Z. If we add multiple sendos of two integers it is the same as considering the multiples of their maximum common divisor.
${displaystyle (a^{2},ab,b^{2})=(a,b)^{2}}$

MCD as internal operation

The MCD can be structured as an operation in Z in this way to any pair of integers, that is to a Sporting element assigns a single element of Z
For any pair of integers (a,b) there is a non-negative integer d which is its maximum common divisor. This is a*b = (a,b) = d
The MCD enjoys associative property, such as commutative property.
The MCD has an identity element, the zero, so that (a, 0)= (0,a)= a
The MCD has a dual behavior that the multiple common minimum and non-negative integers to and b the ab equation = (a,b)[a,b]
Property 1: (a,1) = 1 for any integer to

Applications

The MCD is used to simplify fractions. For example, to simplify the fraction ${displaystyle scriptstyle {frac {48}{60}}}$ is calculated first the mcd(60, 48) = 12, dividing the numerator and the denominator of the initial fraction by 12 to obtain the simplified fraction ${displaystyle scriptstyle {frac {4}{5}}}$ .

The MCD is also used to calculate the minimum common multiple of two numbers. In fact, the product of the two numbers is equal to the product of its maximum common divider by its minimum common multiple. Thus, to calculate the minimum common multiple of 48 and 60, we first calculate its mcd, 12, being its minimum common multiple ${displaystyle scriptstyle {frac {48cdot 60}{12}}=240}$ .

The GCD and Euclid's algorithm are used to solve linear Diophantine equations with two unknowns.

Euclid's algorithm is used to develop a rational number as a continued fraction (sic).

Contenido relacionado

Más resultados...