Gcd VI

Owning Palette: Discrete Math VIs

Requires: Full Development System

Computes the greatest common divisor of the input values.

Details  

Add to the block diagram

Find on the palette

	x is an integer.
	y is an integer.
	gcd(x,y) returns the greatest common divisor of x and y.

Gcd Details

gcd(x,y) is the largest divisor common to x and y.

To compute gcd(x,y), consider the prime factorizations of x and y:

x = Π_i p_i^a_i

y = Π_i p_i^b_i

where p_i are all the prime factors of x and y. If p_i does not occur in a factorization, the corresponding exponent is 0. gcd(x,y) then is given by:

gcd(x,y) = Π_i p_i^{min(a_i , b_i)}

For example, the prime factorizations of 12 and 30 are given by:

12 = 2² × 3¹ × 5⁰

30 = 2¹ × 3¹ × 5¹

so

gcd(12, 30) = 2¹ × 3¹ × 5⁰ = 6