Communication
Install
Faster access than browser!

Greatest common divisor

In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest positive integer that divides the numbers without a remainder. [1]

81 relations: Addison-Wesley, Alexander Stepanov, An Introduction to the Theory of Numbers, Associative property, Asymptotically optimal algorithm, Bézout domain, Bézout's identity, Binary GCD algorithm, Cartesian coordinate system, Charles E. Leiserson, Charles University in Prague, Clifford Stein, Commensurability (mathematics), Commutative property, Commutative ring, Complete lattice, Concrete Mathematics, Coprime integers, D. C. Heath and Company, Decision problem, Distributive lattice, Distributive property, Division algorithm, Divisor, Donald Knuth, Entire function, Ernst Kummer, Euclidean algorithm, Euclidean domain, Euler's totient function, Expected value, Extended Euclidean algorithm, Fermat's Last Theorem, Field (mathematics), Fraction (mathematics), Fundamental theorem of arithmetic, Garrett Birkhoff, Gaussian integer, GCD domain, Harmonic series (mathematics), Ideal (ring theory), Integer, Integer factorization, Integer programming, Integral domain, Introduction to Algorithms, Irreducible fraction, J (programming language), Journal of Number Theory, Least common multiple, ... Expand index (31 more) »

Addison-Wesley is a publisher of textbooks and computer literature.

Alexander Stepanov

Alexander Alexandrovich Stepanov (Алекса́ндр Алекса́ндрович Степа́нов), born November 16, 1950 in Moscow, is the primary designer and implementer of the C++ Standard Template Library, which he started to develop around 1992 while employed at HP Labs.

An Introduction to the Theory of Numbers

An Introduction to the Theory of Numbers is a classic book in the field of number theory, by G. H. Hardy and E. M. Wright.

Associative property

In mathematics, the associative property is a property of some binary operations.

Asymptotically optimal algorithm

In computer science, an algorithm is said to be asymptotically optimal if, roughly speaking, for large inputs it performs at worst a constant factor (independent of the input size) worse than the best possible algorithm.

Bézout domain

In mathematics, a Bézout domain is a form of a Prüfer domain.

Bézout's identity

Bézout's identity (also called Bézout's lemma) is a theorem in the elementary theory of numbers: let a and b be nonzero integers and let d be their greatest common divisor.

Binary GCD algorithm

The binary GCD algorithm, also known as Stein's algorithm, is an algorithm that computes the greatest common divisor of two nonnegative integers.

Cartesian coordinate system

A Cartesian coordinate system is a coordinate system that specifies each point uniquely in a plane by a pair of numerical coordinates, which are the signed distances from the point to two fixed perpendicular directed lines, measured in the same unit of length.

Charles E. Leiserson

Charles Eric Leiserson is a computer scientist, specializing in the theory of parallel computing and distributed computing, and particularly practical applications thereof; as part of this effort, he developed the Cilk multithreaded language.

Charles University in Prague

Charles University in Prague (also simply Charles University; Univerzita Karlova v Praze; Universitas Carolina Pragensis; Karls-Universität Prag) is the oldest and largest university in the Czech Republic.

Clifford Stein

Clifford Seth Stein (born December 14, 1965), a computer scientist, is a professor of industrial engineering and operations research at Columbia University in New York, NY, where he also holds an appointment in the Department of Computer Science.

Commensurability (mathematics)

In mathematics, two non-zero real numbers a and b are said to be commensurable if a/b is a rational number.

Commutative property

In mathematics, a binary operation is commutative if changing the order of the operands does not change the result.

Commutative ring

In ring theory, a branch of abstract algebra, a commutative ring is a ring in which the multiplication operation is commutative.

Complete lattice

In mathematics, a complete lattice is a partially ordered set in which all subsets have both a supremum (join) and an infimum (meet).

Concrete Mathematics

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, is a textbook that is widely used in computer-science departments.

Coprime integers

In number theory, two integers a and b are said to be relatively prime, mutually prime, or coprime (also spelled co-prime) if the only positive integer that evenly divides both of them is 1.

D. C. Heath and Company

D.C. Heath and Company was an American publishing company located at 125 Spring Street in Lexington, Massachusetts, specializing in textbooks.

Decision problem

In computability theory and computational complexity theory, a decision problem is a question in some formal system with a yes-or-no answer, depending on the values of some input parameters.

Distributive lattice

In mathematics, a distributive lattice is a lattice in which the operations of join and meet distribute over each other.

Distributive property

In abstract algebra and formal logic, the distributive property of binary operations generalizes the distributive law from elementary algebra.

Division algorithm

A division algorithm is an algorithm which, given two integers N and D, computes their quotient and/or remainder, the result of division.

Divisor

In mathematics a divisor of an integer n, also called a factor of n, is an integer that can be multiplied by some other integer to produce n.

Donald Knuth

Donald Ervin Knuth (born January 10, 1938) is an American computer scientist, mathematician, and professor emeritus at Stanford University.

Entire function

In complex analysis, an entire function, also called an integral function, is a complex-valued function that is holomorphic over the whole complex plane.

Ernst Kummer

Ernst Eduard Kummer (29 January 1810 – 14 May 1893) was a German mathematician.

Euclidean algorithm

. EXAMPLES CAN BE FOUND BELOW, E.G., IN THE "Matrix method" SECTION.

Euclidean domain

In mathematics, more specifically in abstract algebra and ring theory, a Euclidean domain (also called a Euclidean ring) is a ring that can be endowed with a Euclidean function (explained below) which allows a suitable generalization of the Euclidean division of the integers.

Euler's totient function

In number theory, Euler's totient function (or Euler's phi function), denoted as or, is an arithmetic function that counts the positive integers less than or equal to n that are relatively prime to n. (These integers are sometimes referred to as totatives of n.) Thus, if n is a positive integer, then is the number of integers k in the range for which the greatest common divisor.

Expected value

In probability theory, the expected value of a random variable is intuitively the long-run average value of repetitions of the experiment it represents.

Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, which computes, besides the greatest common divisor of integers a and b, the coefficients of Bézout's identity, that is integers x and y such that It allows one to compute also, with almost no extra cost, the quotients of a and b by their greatest common divisor.

Fermat's Last Theorem

In number theory, Fermat's Last Theorem (sometimes called Fermat's conjecture, especially in older texts) states that no three positive integers a, b, and c can satisfy the equation an + bn.

Field (mathematics)

In abstract algebra, a field is a nonzero commutative division ring, or equivalently a ring whose nonzero elements form an abelian group under multiplication.

Fraction (mathematics)

A fraction (from fractus, "broken") represents a part of a whole or, more generally, any number of equal parts.

Fundamental theorem of arithmetic

In number theory, the fundamental theorem of arithmetic, also called the unique factorization theorem or the unique-prime-factorization theorem, states that every integer greater than 1Using the empty product rule one need not exclude the number 1, and the theorem can be stated as: every positive integer has unique prime factorization.

Garrett Birkhoff

Garrett Birkhoff (January 19, 1911 – November 22, 1996) was an American mathematician.

Gaussian integer

In number theory, a Gaussian integer is a complex number whose real and imaginary parts are both integers.

GCD domain

In mathematics, a GCD domain is an integral domain R with the property that any two non-zero elements have a greatest common divisor (GCD).

Harmonic series (mathematics)

In mathematics, the harmonic series is the divergent infinite series: Its name derives from the concept of overtones, or harmonics in music: the wavelengths of the overtones of a vibrating string are 1/2, 1/3, 1/4, etc., of the string's fundamental wavelength.

Ideal (ring theory)

In ring theory, a branch of abstract algebra, an ideal is a special subset of a ring.

Integer

An integer (from the Latin ''integer'' meaning "whole")Integer&#x2009;'s first, literal meaning in Latin is "untouched", from in ("not") plus tangere ("to touch").

Integer factorization

In number theory, integer factorization is the decomposition of a composite number into a product of smaller integers.

Integer programming

An integer programming problem is a mathematical optimization or feasibility program in which some or all of the variables are restricted to be integers.

Integral domain

In mathematics, and specifically in abstract algebra, an integral domain is a nonzero commutative ring in which the product of any two nonzero elements is nonzero.

Introduction to Algorithms

Introduction to Algorithms is a book by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein.

Irreducible fraction

An irreducible fraction (or fraction in lowest terms or reduced fraction) is a fraction in which the numerator and denominator are integers that have no other common divisors than 1 (and -1, when negative numbers are considered).

J (programming language)

The J programming language, developed in the early 1990s by Kenneth E. Iverson and Roger Hui, is a synthesis of APL (also by Iverson) and the FP and FL function-level languages created by John Backus.

Journal of Number Theory

The Journal of Number Theory is a mathematics journal that publishes a broad spectrum of original research in number theory.

Least common multiple

In arithmetic and number theory, the least common multiple (also called the lowest common multiple or smallest common multiple) of two integers a and b, usually denoted by LCM(a, b), is the smallest positive integer that is divisible by both a and b. Since division of integers by zero is undefined, this definition has meaning only if a and b are both different from zero.

Line segment

In geometry, a line segment is a part of a line that is bounded by two distinct end points, and contains every point on the line between its end points.

Long division

In arithmetic, long division is a standard division algorithm suitable for dividing multidigit numbers that is simple enough to perform by hand.

Lowest common denominator

In mathematics, the lowest common denominator or least common denominator (abbreviated LCD) is the least common multiple of the denominators of a set of fractions.

Mathematics

Mathematics (from Greek μάθημα máthēma, “knowledge, study, learning”) is the study of topics such as quantity (numbers), structure, space, and change.

Maximal common divisor

In abstract algebra, particularly ring theory, maximal common divisors are an abstraction of the number theory concept of greatest common divisor (GCD).

Multiplicative function

In number theory, a multiplicative function is an arithmetic function f(n) of the positive integer n with the property that f(1).

Natural number

In mathematics, the natural numbers (sometimes called the whole numbers): "whole number An integer, though sometimes it is taken to mean only non-negative integers, or just the positive integers." give definitions of "whole number" under several headwords: INTEGER … Syn. whole number.

NC (complexity)

In complexity theory, the class NC (for "Nick's Class") is the set of decision problems decidable in polylogarithmic time on a parallel computer with a polynomial number of processors.

NL (complexity)

In computational complexity theory, NL (Nondeterministic Logarithmic-space) is the complexity class containing decision problems which can be solved by a nondeterministic Turing machine using a logarithmic amount of memory space.

NP-completeness

In computational complexity theory, a decision problem is NP-complete when it is both in NP and NP-hard.

Oxford University Press

Oxford University Press (OUP) is the largest university press in the world, and the second-oldest, after Cambridge University Press.

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is one of the most fundamental complexity classes.

P-complete

In complexity theory, the notion of P-complete decision problems is useful in the analysis of both.

Parallel random-access machine

In computer science, a parallel random-access machine (PRAM) is a shared-memory abstract machine.

Polynomial greatest common divisor

In algebra, the greatest common divisor (frequently abbreviated as GCD) of two polynomials is a polynomial, of the highest possible degree, that is a factor of both the two original polynomials.

Prentice Hall

Prentice Hall is a major educational publisher owned by Pearson PLC.

Principal ideal domain

In abstract algebra, a principal ideal domain, or PID, is an integral domain in which every ideal is principal, i.e., can be generated by a single element.

Ramanujan's sum

In number theory, a branch of mathematics, Ramanujan's sum, usually denoted cq(n), is a function of two positive integer variables q and n defined by the formula where (a, q).

Randomized algorithm

A randomized algorithm is an algorithm that employs a degree of randomness as part of its logic.

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction p/q of two integers, p and q, with the denominator q not equal to zero.

Remainder

In mathematics, the remainder is the amount "left over" after performing some computation.

Riemann zeta function

The Riemann zeta function or Euler–Riemann zeta function, ζ(s), is a function of a complex variable s that analytically continues the sum of the infinite series which converges when the real part of s is greater than 1.

Ron Rivest

Ronald Linn Rivest (born May 6, 1947) is a cryptographer and an Institute Professor at MIT.

Saunders Mac Lane

Saunders Mac Lane (4 August 1909 – 14 April 2005) was an American mathematician who co-founded category theory with Samuel Eilenberg.

The Art of Computer Programming

The Art of Computer Programming (sometimes known by its initials TAOCP) is a comprehensive monograph written by Donald Knuth that covers many kinds of programming algorithms and their analysis.

Thomae's function

Thomae's function, named after Carl Johannes Thomae, has many names: the popcorn function, the raindrop function, the countable cloud function, the modified Dirichlet function, the ruler function, the Riemann function, or the Stars over Babylon (John Horton Conway's name).

Thomas H. Cormen

Thomas H. Cormen is the co-author of Introduction to Algorithms, along with Charles Leiserson, Ron Rivest, and Cliff Stein.

Time complexity

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

Unique factorization domain

In mathematics, a unique factorization domain (UFD) is a commutative ring in which every non-zero non-unit element can be written as a product of prime elements (or irreducible elements), uniquely up to order and units, analogous to the fundamental theorem of arithmetic for the integers.

University of West Georgia

The University of West Georgia is a comprehensive doctoral-granting university in Carrollton, Georgia, approximately 45 miles (80 km) west of Atlanta, Georgia.

Venn diagram

A Venn diagram or set diagram is a diagram that shows all possible logical relations between a finite collection of different sets.

References

Hey! We are on Facebook now! »