11159
EXPLORE
LATEST
ABOUT
AUTHORING AREA
PARTICIPATE
Your browser does not support JavaScript or it may be disabled!
Finding the Greatest Common Divisor of Two Numbers by Factoring
You can find the greatest common divisor (GCD) of two numbers by multiplying together all the prime factors they have in common.
Contributed by:
Jesse Nochella
SNAPSHOTS
DETAILS
A much more efficient way of computing GCDs has been known for the past 2300 years. Named the Euclidean Algorithm, it is one of the oldest mathematical procedures known, appearing in Euclid's
Elements
around 300 BC.
RELATED LINKS
Divisor
(
Wolfram
MathWorld
)
Greatest Common Divisor
(
Wolfram
MathWorld
)
Euclidean Algorithm
(
Wolfram
MathWorld
)
PERMANENT CITATION
"
Finding the Greatest Common Divisor of Two Numbers by Factoring
" from
the Wolfram Demonstrations Project
http://demonstrations.wolfram.com/FindingTheGreatestCommonDivisorOfTwoNumbersByFactoring/
Contributed by:
Jesse Nochella
Share:
Embed Interactive Demonstration
New!
Just copy and paste this snippet of JavaScript code into your website or blog to put the live Demonstration on your site.
More details »
Download Demonstration as CDF »
Download Author Code »
(preview »)
Files require
Wolfram
CDF Player
or
Mathematica
.
Related Demonstrations
More by Author
Finding the Least Common Multiple of Two Numbers by Factoring
Jesse Nochella
The Euclidean Algorithm and Simple Continued Fractions
?tefan Porubský
Extended Euclidean Algorithm
?tefan Porubský
The Euclidean Algorithm
Matthew Szudzik
Euclidean Algorithm Steps
Michael Trott
Relatively Prime Numbers and Zeta(2)
Okay Arik
Factor Trees
Jesse Nochella
Proposition 30, Book XI, Euclid's Elements
Izidor Hafner
Proposition 29, Book XI, Euclid's Elements
Izidor Hafner
Proposition 7, Book XII, Euclid's Elements
Izidor Hafner
Related Topics
Euclid's Elements
Greek Mathematics
Number Theory
Elementary School 3-5 Mathematics
Browse all topics
Related Curriculum Standards
US Common Core State Standards, Mathematics
4.OA.B.4
6.NS.B.4
Note: To run this Demonstration you need Mathematica 7+ or the free Mathematica Player 7EX
Download or upgrade to
Mathematica Player 7EX
I already have
Mathematica Player
or
Mathematica 7+