In this article we will denote the greatest common divisor of two integers a and b as gcd ( a, b ).

* Every common divisor of a and b is a divisor of gcd ( a, b ).

* If a divides the product b · c, and gcd ( a, b ) =

* If m is a non-negative integer, then gcd ( m · a, m · b ) = m · gcd ( a, b ).

* If m is any integer, then gcd ( a + m · b, b ) = gcd ( a, b ).

* If m is a nonzero common divisor of a and b, then gcd ( a / m, b / m ) = gcd ( a, b )/ m.

In mathematics, the greatest common divisor ( gcd ), also known as the greatest common factor ( gcf ), or highest common factor ( hcf ), of two or more non-zero integers, is the largest positive integer that divides the numbers without a remainder.

Greatest common divisors can in principle be computed by determining the prime factorizations of the two numbers and comparing factors, as in the following example: to compute gcd ( 18, 84 ), we find the prime factorizations 18 = 2 · 3 < sup > 2 </ sup > and 84 = 2 < sup > 2 </ sup > · 3 · 7 and notice that the " overlap " of the two expressions is 2 · 3 ; so gcd ( 18, 84 ) = 6.

To compute gcd ( 48, 18 ), divide 48 by 18 to get a quotient of 2 and a remainder of 12.

gcd ( gcd ( a, b ), c ), or in some different way by applying commutativity and associativity.

:: gcd ( a, lcm ( b, c )) = lcm ( gcd ( a, b ), gcd ( a, c ))

:: lcm ( a, gcd ( b, c )) = gcd ( lcm ( a, b ), lcm ( a, c )).

* In a Cartesian coordinate system, gcd ( a, b ) can be interpreted as the number of points with integral coordinates on the straight line joining the points ( 0, 0 ) and ( a, b ), excluding ( 0, 0 ).

In this case the probability that the gcd equals d is d < sup >− 2 </ sup >/ ζ ( 2 ), and since ζ ( 2 ) = π < sup > 2 </ sup >/ 6 we have

In a ring all of whose ideals are principal ( a principal ideal domain or PID ), this ideal will be identical with the set of multiples of some ring element d ; then this d is a greatest common divisor of a and b. But the ideal ( a, b ) can be useful even when there is no greatest common divisor of a and b. ( Indeed, Ernst Kummer used this ideal as a replacement for a gcd in his treatment of Fermat's Last Theorem, although he envisioned it as the set of multiples of some hypothetical, or ideal, ring element d, whence the ring-theoretic term.

The two primes, p and q, should both be congruent to 3 ( mod 4 ) ( this guarantees that each quadratic residue has one square root which is also a quadratic residue ) and gcd ( φ ( p-1 ), φ ( q-1 )) should be small ( this makes the cycle length large ).

gcd ( lcm ( a, b ), LCM ( a, c )).

However, if gcd ( v, n ) is neither 1 nor n, then the-addition will not produce a meaningful point on the curve, which shows that our elliptic curve is not a group ( mod n ), but, more importantly for now, gcd ( v, n ) is a non-trivial factor of n.

It is related to their greatest common divisor, gcd ( n, k ), by the formula:

The center of the special unitary group has order gcd ( n, q + 1 ) and consists of those unitary scalars which also have order dividing n. The quotient of the unitary group by its center is called the projective unitary group, PU ( n, q² ), and the quotient of the special unitary group by its center is the projective special unitary group PSU ( n, q² ).

* gcd ( n, k ): the greatest common divisor of n and k, as a function of n, where k is a fixed integer.

But it then suffices to go back to the previous gcd term, where, and use the regular Rho algorithm from there.

The condition gcd is equivalent to requiring that the map on is one to one and its inverse is the map where is the multiplicative inverse of.

* The gcd is a multiplicative function in the following sense: if a < sub > 1 </ sub > and a < sub > 2 </ sub > are relatively prime, then gcd ( a < sub > 1 </ sub >· a < sub > 2 </ sub >, b ) = gcd ( a < sub > 1 </ sub >, b )· gcd ( a < sub > 2 </ sub >, b ).

This is multiplicative if the set C has the property that if a and b are in C, gcd ( a, b )= 1, than ab is also in C. This is the case if C is the set of squares, cubes, or higher powers, or if C is the set of square-free numbers.

< li > If gcd ( a, N ) ≠ 1, then there is a nontrivial factor of N, so we are done .</ li >

< li > gcd ( a < sup > r / 2 </ sup > ± 1, N ) is a nontrivial factor of N. We are done .</ li >

In number theory, Euler's totient or phi function, φ ( n ) is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then φ ( n ) is the number of integers k in the range 1 ≤ k ≤ n for which gcd ( n, k ) = 1.

Proof: Since p is a prime number the only possible values of gcd ( p < sup > k </ sup >, m ) are 1, p, p < sup > 2 </ sup >, ..., p < sup > k </ sup >, and the only way for gcd ( p < sup > k </ sup >, m ) to not equal 1 is for m to be a multiple of p. The multiples of p that are less than or equal to p < sup > k </ sup > are p, 2p, 3p, ..., p < sup > k − 1 </ sup > p = p < sup > k </ sup >, and there are p < sup > k − 1 </ sup > of them.

and a random integer, r, such that gcd ( r, q ) = 1 ( i. e. r and q are coprime ).

* If we encountered a gcd ( v, n ) at some stage that was neither 1 nor n, then we are done: it is a non-trivial factor of n.

So all prime numbers are of the form 30k + i for i = 1, 7, 11, 13, 17, 19, 23, 29 ( i. e. for i < 30 such that gcd ( i, 30 ) = 1 ).

* gcd ( m, n ) ( greatest common divisor of m and n ) is the product of all prime factors which are both in m and n ( with the smallest multiplicity for m and n ).

* m and n are coprime ( also called relatively prime ) if gcd ( m, n ) = 1 ( meaning they have no common prime factor ).

Note that gcd ( x, N )= 1 with overwhelming probability, which ensures that there are 4 square roots of x < sup > 2 </ sup > mod N.

Because gcd ( a, b ) is a divisor of both a and b, it's more efficient to compute the LCM by dividing before multiplying:

Because gcd ( a, b ) is a divisor of both a and b, the division is guaranteed to yield an integer, so the intermediate result can be stored in an integer.

When this is the case, kP does not exist on the original curve, and in the computations we found some v with either gcd ( v, p )= p or gcd ( v, q )= q, but not both.

# If u and v are both even, then gcd ( u, v ) =

# If u and v are both odd, and u ≥ v, then gcd ( u, v )

It may be constructed with gcd ( 8, 2 ) = 2 cycles ; see image.

Thus in the evaluation of quadratic Gauss sums one may always assume gcd ( a, c )= 1.