Logo
Unionpedia
Communication
Get it on Google Play
New! Download Unionpedia on your Android™ device!
Free
Faster access than browser!
 

Greatest common divisor

+ Save concept

In mathematics, the greatest common divisor (gcd) of two or more integers, which are not all zero, is the largest positive integer that divides each of the integers. [1]

86 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, Bit, Cartesian coordinate system, Charles E. Leiserson, Charles University, Clifford Stein, Commensurability (mathematics), Commutative property, Commutative ring, Complete lattice, Computational complexity, Concrete Mathematics, Coprime integers, D. C. Heath and Company, Decision problem, Distributive lattice, Distributive property, Division (mathematics), Division algorithm, 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, Journal of Number Theory, ..., Least common multiple, Line segment, Long division, Lowest common denominator, Mathematics, Maximal common divisor, Model of computation, Multiplication algorithm, Multiplicative function, Multitape Turing machine, Natural number, NC (complexity), NL (complexity), Oxford University Press, P (complexity), P-complete, Parallel algorithm, Parallel random-access machine, Polynomial greatest common divisor, Prentice Hall, Principal ideal domain, Ramanujan's sum, Random-access machine, Randomized algorithm, Rational number, Riemann zeta function, Ron Rivest, Saunders Mac Lane, The Art of Computer Programming, Thomae's function, Thomas H. Cormen, Time complexity, Unique factorization domain, University of West Georgia, Venn diagram, Wolfram Demonstrations Project. Expand index (36 more) »

Addison-Wesley

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

New!!: Greatest common divisor and Addison-Wesley · See more »

Alexander Stepanov

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

New!!: Greatest common divisor and Alexander Stepanov · See more »

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.

New!!: Greatest common divisor and An Introduction to the Theory of Numbers · See more »

Associative property

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

New!!: Greatest common divisor and Associative property · See more »

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.

New!!: Greatest common divisor and Asymptotically optimal algorithm · See more »

Bézout domain

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

New!!: Greatest common divisor and Bézout domain · See more »

Bézout's identity

In elementary number theory, Bézout's identity (also called Bézout's lemma) is the following theorem: The integers x and y are called Bézout coefficients for (a, b); they are not unique.

New!!: Greatest common divisor and Bézout's identity · See more »

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.

New!!: Greatest common divisor and Binary GCD algorithm · See more »

Bit

The bit (a portmanteau of binary digit) is a basic unit of information used in computing and digital communications.

New!!: Greatest common divisor and Bit · See more »

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 to the point from two fixed perpendicular directed lines, measured in the same unit of length.

New!!: Greatest common divisor and Cartesian coordinate system · See more »

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.

New!!: Greatest common divisor and Charles E. Leiserson · See more »

Charles University

Charles University, known also as Charles University in Prague (Univerzita Karlova; Universitas Carolina; Karls-Universität) or historically as the University of Prague (Universitas Pragensis), is the oldest and largest university in the Czech Republic. Founded in 1348, it was the first university in Central Europe. It is one of the oldest universities in Europe in continuous operation and ranks in the upper 1.5 percent of the world’s best universities. Its seal shows its protector Emperor Charles IV, with his coats of arms as King of the Romans and King of Bohemia, kneeling in front of St. Wenceslas, the patron saint of Bohemia. It is surrounded by the inscription, Sigillum Universitatis Scolarium Studii Pragensis (Seal of the Prague academia).

New!!: Greatest common divisor and Charles University · See more »

Christmas

Christmas is an annual festival commemorating the birth of Jesus Christ,Martindale, Cyril Charles.

New!!: Greatest common divisor and Christmas · See more »

Christmas and holiday season

The Christmas season, also called the festive season, or the holiday season (mainly in the U.S. and Canada; often simply called the holidays),, is an annually recurring period recognized in many Western and Western-influenced countries that is generally considered to run from late November to early January.

New!!: Greatest common divisor and Christmas and holiday season · See more »

Christmas Eve

Christmas Eve is the evening or entire day before Christmas Day, the festival commemorating the birth of Jesus.

New!!: Greatest common divisor and Christmas Eve · See more »

Christmas traditions

Christmas traditions vary from country to country.

New!!: Greatest common divisor and Christmas traditions · See more »

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.

New!!: Greatest common divisor and Clifford Stein · See more »

Commensurability (mathematics)

In mathematics, two non-zero real numbers a and b are said to be commensurable if their ratio is a rational number; otherwise a and b are called incommensurable.

New!!: Greatest common divisor and Commensurability (mathematics) · See more »

Commutative property

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

New!!: Greatest common divisor and Commutative property · See more »

Commutative ring

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

New!!: Greatest common divisor and Commutative ring · See more »

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).

New!!: Greatest common divisor and Complete lattice · See more »

Computational complexity

In computer science, the computational complexity, or simply complexity of an algorithm is the amount of resources required for running it.

New!!: Greatest common divisor and Computational complexity · See more »

Concrete Mathematics

Concrete Mathematics: A Foundation for Computer Science, by Ronald Graham, Donald Knuth, and Oren Patashnik, first published in 1989, is a textbook that is widely used in computer-science departments as a substantive but light-hearted treatment of the analysis of algorithms.

New!!: Greatest common divisor and Concrete Mathematics · See more »

Coprime integers

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

New!!: Greatest common divisor and Coprime integers · See more »

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.

New!!: Greatest common divisor and D. C. Heath and Company · See more »

Decision problem

In computability theory and computational complexity theory, a decision problem is a problem that can be posed as a yes-no question of the input values.

New!!: Greatest common divisor and Decision problem · See more »

Distributive lattice

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

New!!: Greatest common divisor and Distributive lattice · See more »

Distributive property

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

New!!: Greatest common divisor and Distributive property · See more »

Division (mathematics)

Division is one of the four basic operations of arithmetic, the others being addition, subtraction, and multiplication.

New!!: Greatest common divisor and Division (mathematics) · See more »

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.

New!!: Greatest common divisor and Division algorithm · See more »

Donald Knuth

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

New!!: Greatest common divisor and Donald Knuth · See more »

Entire function

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

New!!: Greatest common divisor and Entire function · See more »

Ernst Kummer

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

New!!: Greatest common divisor and Ernst Kummer · See more »

Euclidean algorithm

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

New!!: Greatest common divisor and Euclidean algorithm · See more »

Euclidean domain

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

New!!: Greatest common divisor and Euclidean domain · See more »

Euler's totient function

In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to.

New!!: Greatest common divisor and Euler's totient function · See more »

Expected value

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

New!!: Greatest common divisor and Expected value · See more »

Extended Euclidean algorithm

In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor of integers a and b, also the coefficients of Bézout's identity, which are integers x and y such that This is a certifying algorithm, because the gcd is the only number that can simultaneously satisfy this equation and divide the inputs.

New!!: Greatest common divisor and Extended Euclidean algorithm · See more »

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,, and satisfy the equation for any integer value of greater than 2.

New!!: Greatest common divisor and Fermat's Last Theorem · See more »

Field (mathematics)

In mathematics, a field is a set on which addition, subtraction, multiplication, and division are defined, and behave as when they are applied to rational and real numbers.

New!!: Greatest common divisor and Field (mathematics) · See more »

Fraction (mathematics)

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

New!!: Greatest common divisor and Fraction (mathematics) · See more »

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 1 either is a prime number itself or can be represented as the product of prime numbers and that, moreover, this representation is unique, up to (except for) the order of the factors.

New!!: Greatest common divisor and Fundamental theorem of arithmetic · See more »

Garrett Birkhoff

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

New!!: Greatest common divisor and Garrett Birkhoff · See more »

Gaussian integer

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

New!!: Greatest common divisor and Gaussian integer · See more »

GCD domain

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

New!!: Greatest common divisor and GCD domain · See more »

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,,, etc., of the string's fundamental wavelength.

New!!: Greatest common divisor and Harmonic series (mathematics) · See more »

Ideal (ring theory)

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

New!!: Greatest common divisor and Ideal (ring theory) · See more »

Integer

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

New!!: Greatest common divisor and Integer · See more »

Integer factorization

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

New!!: Greatest common divisor and Integer factorization · See more »

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.

New!!: Greatest common divisor and Integer programming · See more »

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.

New!!: Greatest common divisor and Integral domain · See more »

Introduction to Algorithms

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

New!!: Greatest common divisor and Introduction to Algorithms · See more »

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).

New!!: Greatest common divisor and Irreducible fraction · See more »

Journal of Number Theory

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

New!!: Greatest common divisor and Journal of Number Theory · See more »

Least common multiple

In arithmetic and number theory, the least common multiple, 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.

New!!: Greatest common divisor and Least common multiple · See more »

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 endpoints.

New!!: Greatest common divisor and Line segment · See more »

Long division

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

New!!: Greatest common divisor and Long division · See more »

Lowest common denominator

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

New!!: Greatest common divisor and Lowest common denominator · See more »

Mathematics

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

New!!: Greatest common divisor and Mathematics · See more »

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).

New!!: Greatest common divisor and Maximal common divisor · See more »

Model of computation

In computer science, and more specifically in computability theory and computational complexity theory, a model of computation is a model which describes how a set of outputs are computed given a set of inputs.

New!!: Greatest common divisor and Model of computation · See more »

Multiplication algorithm

A multiplication algorithm is an algorithm (or method) to multiply two numbers.

New!!: Greatest common divisor and Multiplication algorithm · See more »

Multiplicative function

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

New!!: Greatest common divisor and Multiplicative function · See more »

Multitape Turing machine

A multi-tape Turing machine is like an ordinary Turing machine with several tapes.

New!!: Greatest common divisor and Multitape Turing machine · See more »

Natural number

In mathematics, the natural numbers are those used for counting (as in "there are six coins on the table") and ordering (as in "this is the third largest city in the country").

New!!: Greatest common divisor and Natural number · See more »

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.

New!!: Greatest common divisor and NC (complexity) · See more »

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.

New!!: Greatest common divisor and NL (complexity) · See more »

New Year

New Year is the time or day at which a new calendar year begins and the calendar's year count increments by one.

New!!: Greatest common divisor and New Year · See more »

New Year's Day

New Year's Day, also called simply New Year's or New Year, is observed on January 1, the first day of the year on the modern Gregorian calendar as well as the Julian calendar.

New!!: Greatest common divisor and New Year's Day · See more »

New Year's Eve

In the Gregorian calendar, New Year's Eve (also known as Old Year's Day or Saint Sylvester's Day in many countries), the last day of the year, is on 31 December which is the seventh day of Christmastide.

New!!: Greatest common divisor and New Year's Eve · See more »

Oxford University Press

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

New!!: Greatest common divisor and Oxford University Press · See more »

P (complexity)

In computational complexity theory, P, also known as PTIME or DTIME(nO(1)), is a fundamental complexity class.

New!!: Greatest common divisor and P (complexity) · See more »

P-complete

In complexity theory, a decision problem is P-complete (complete for the complexity class '''P''') if it is in P and every problem in P can be reduced to it by an appropriate reduction.

New!!: Greatest common divisor and P-complete · See more »

Parallel algorithm

In computer science, a parallel algorithm, as opposed to a traditional serial algorithm, is an algorithm which can be executed a piece at a time on many different processing devices, and then combined together again at the end to get the correct result.

New!!: Greatest common divisor and Parallel algorithm · See more »

Parallel random-access machine

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

New!!: Greatest common divisor and Parallel random-access machine · See more »

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.

New!!: Greatest common divisor and Polynomial greatest common divisor · See more »

Prentice Hall

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

New!!: Greatest common divisor and Prentice Hall · See more »

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.

New!!: Greatest common divisor and Principal ideal domain · See more »

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).

New!!: Greatest common divisor and Ramanujan's sum · See more »

Random-access machine

In computer science, random-access machine (RAM) is an abstract machine in the general class of register machines.

New!!: Greatest common divisor and Random-access machine · See more »

Randomized algorithm

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

New!!: Greatest common divisor and Randomized algorithm · See more »

Rational number

In mathematics, a rational number is any number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator.

New!!: Greatest common divisor and Rational number · See more »

Riemann zeta function

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

New!!: Greatest common divisor and Riemann zeta function · See more »

Ron Rivest

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

New!!: Greatest common divisor and Ron Rivest · See more »

Saunders Mac Lane

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

New!!: Greatest common divisor and Saunders Mac Lane · See more »

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.

New!!: Greatest common divisor and The Art of Computer Programming · See more »

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).

New!!: Greatest common divisor and Thomae's function · See more »

Thomas H. Cormen

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

New!!: Greatest common divisor and Thomas H. Cormen · See more »

Time complexity

In computer science, the time complexity is the computational complexity that describes the amount of time it takes to run an algorithm.

New!!: Greatest common divisor and Time complexity · See more »

Unique factorization domain

In mathematics, a unique factorization domain (UFD) is an integral domain (a non-zero commutative ring in which the product of non-zero elements is non-zero) 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.

New!!: Greatest common divisor and Unique factorization domain · See more »

University of West Georgia

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

New!!: Greatest common divisor and University of West Georgia · See more »

Venn diagram

A Venn diagram (also called primary diagram, set diagram or logic diagram) is a diagram that shows all possible logical relations between a finite collection of different sets.

New!!: Greatest common divisor and Venn diagram · See more »

Wolfram Demonstrations Project

The Wolfram Demonstrations Project is an organized, open-source collection of small (or medium-size) interactive programs called Demonstrations, which are meant to visually and interactively represent ideas from a range of fields.

New!!: Greatest common divisor and Wolfram Demonstrations Project · See more »

2018

2018 has been designated as the third International Year of the Reef by the International Coral Reef Initiative.

New!!: Greatest common divisor and 2018 · See more »

2019

2019 (MMXIX) will be a common year starting on Tuesday of the Gregorian calendar, the 2019th year of the Common Era (CE) and Anno Domini (AD) designations, the 19th year of the 3rd millennium, the 19th year of the 21st century, and the 10th and last year of the 2010s decade.

New!!: Greatest common divisor and 2019 · See more »

Redirects here:

B Q Over M, Common Factor, Common divisor, Common factor, Greatest Common Divisor, Greatest Common Factor, Greatest common denominator, Greatest common factor, Greatest common measure, Grootste gemene deler, Highest common denominator, Highest common divisor, Highest common factor, NWD (mathematics), Q B Over M.

References

[1] https://en.wikipedia.org/wiki/Greatest_common_divisor

OutgoingIncoming
Hey! We are on Facebook now! »