What are some real-life applications of gcd? I am looking for a motivating way of introducing this topic in an elementary number theory course.
$\begingroup$
$\endgroup$
5
-
1$\begingroup$ I'm not sure what you mean. I mean ... pretty much everything in number theory depends in one way or another on this concept. I often tell classes that even if people hadn't discovered prime numbers, they would have had to discover relatively prime as a concept. $\endgroup$– kcrismanCommented Mar 10, 2017 at 5:03
-
6$\begingroup$ "Simplifying a fraction" is essentially dividing numerator and denominator by their gcd, e.g., simplifying $12/18$ is done by dividing numerator and denominator by $\gcd\{12, 18\} = 6$ to get $2/3$. $\endgroup$– Benjamin DickmanCommented Mar 10, 2017 at 6:25
-
1$\begingroup$ As mentioned in the answers below, computing the gcd is equivalent to computing the lcm, and the lcm shows up whenever you have 2 (or more) periodic occurrences; the lcm tells you how often they happen together. So everything from analyzing sinusoidal waves to determining the next time you will run out of both peanut butter and jelly involves the lcm (and hence the gcd). $\endgroup$– AerykCommented Mar 11, 2017 at 19:13
-
5$\begingroup$ Am I the last person on this planet who thinks that people who don't know applications of greatest common divisors should not be teaching number theory? $\endgroup$– Franz LemmermeyerCommented Mar 12, 2017 at 22:29
-
6$\begingroup$ @FranzLemmermeyer I am not sure what the intent of your comment is. OP actively seeks to educate themselves on the subject, in that sense it seems they agree that it is good to know this when teaching ENT. Further, it is not uncommon that instructors learn a subject they teach 'on the fly' (either by choice or as circumstances dictate it); this can work well. I would like to invite you to express your thoughts on the subject in a more constructive and supportive way. $\endgroup$– quidCommented Mar 14, 2017 at 12:15
Add a comment
|
6 Answers
$\begingroup$
$\endgroup$
Another classic is the following:
A rectangular floor measures $300 \text{ cm} \times 195 \text{ cm}$. What is the largest square tiles that can be used to cover the floor exactly?
answered Mar 12, 2017 at 15:49
$\begingroup$
$\endgroup$
2
Going back to Euclid, I have found questions such as `Given a large supply of rods of length $15$ and $21$, what lengths can be measured?' can appeal to students. This also motivates the result $\gcd(a,b) = ra+sb$ of the (extended) Euclidean Algorithm.
-
$\begingroup$ Can also apply to stamp or coin problems. $\endgroup$ Commented May 18, 2017 at 18:05
-
$\begingroup$ Also applies to liquid measurement given too containers, say of 5 and 7 gallons. Advantage: you can invoke Die Hard 3. $\endgroup$ Commented May 19, 2017 at 21:17
$\begingroup$
$\endgroup$
1
Some nice geometrical applications arise in the analysis of periodical curves such as Roulettes (Spirograph curves), Star Polygons, etc. Concrete experience with implementations in toys like Spirograph also provides excellent motivation for more abstract concepts such as cyclic groups.
answered May 16, 2017 at 18:11
-
2$\begingroup$ This is a good one, and it's how I introduced $\gcd$ to a class of education students. I drew a couple of $\{n/k\}$ star polygons and handed out a sheet with 12 sets of 12 vertices of a regular dodecagon for creating the various $\{12/k\}$. It was moderately successful, asking them to figure out how many "pieces" the star polygons would have, and what relationship between $n$ and $k$ would cause the star to be connected. $\endgroup$– pjs36Commented May 17, 2017 at 13:10
$\begingroup$
$\endgroup$
1
Here's a word problem for the greatest common divisor:
12 boys and 15 girls are to march in a parade. The organizer wants them to march in rows, with each row having the same number of children, and with each row composed of children with the same gender. What is the largest number of children per row that satisfies these constraints?
There should be $\operatorname{gcd}(12,15)=3$ children per row ($4$ rows of boys and $5$ rows of girls).
Also, I know that you didn't ask for it, but when I teach the gcd I also teach the least common multiple. Here's a word problem for the lcm.
A child is having a birthday party and knows that either 12 or 15 guests would attend it. The child's father wants to buy candies for the guests, with each guest having the same number of candies, but doesn't want to buy more candies than is necessary. What is the minimum number of candies that the father should buy?
The father should buy $\operatorname{lcm}(12,15)=60$ candies, so that if $12$ friends come, they each get $5$ candies, and if $15$ come, they each get $4$.
-
4$\begingroup$ I'm not sure if my "contrived" examples can be considered "applications," but they might inspire more "realistic" examples. $\endgroup$– JRNCommented Mar 11, 2017 at 5:32
$\begingroup$
$\endgroup$
I think for the most elementary level of introduction Joel and Benjamin has provided good examples. I think I should try too.
$1.$ When we have a linear diophantine equation like $ax+by=c$ where $a,b \ and \ c$ are integers, we get integer solutions in $x,y$ iff $(a,b)|c$.
$2.$ As a rearrangement of a well theorem of divisibility, we know that for two numbers $a,b$ we have $[a,b]=\frac{|ab|}{(a,b)}$. So, ultimately knowing G.C.D. of two numbers give us their L.C.M and vice versa.
$3.$ This one may overflow for a high school student because the way it is designed, consider the question:
Two regular polygons are inscribed in the same circle. The first polygon have $1982$ sides and second have $2973$ sides. If polygons have any numbers of common vertices, how many such vertices there will be??
The solution is simply the common roots of the equation $z^{1982}-1=0$ and $z^{2973}-1=0$ which in turn equals gcd$(1982,2973)=991$.
$\begingroup$
$\endgroup$
The special case of $gcd(a,b) = 1$ (i.e. $a,b$ are relatively prime) is in its own right an important motivation for $gcd(a,b)$, especially if you link it with the (extended) Euclidian algorithm. Students tend to like the idea of secret codes. You can connect the notion of being relatively prime with the notion of a number $a$ being invertible mod $b$ and show how the Euclidean algorithm can efficiently compute this modular inverse, and then point out how this is the crucial step in computing private/public key pairs in RSA encryption.
