Difference between revisions of "1990 AHSME Problems/Problem 19"
Coolmath2017 (talk | contribs) (→Solution 2) |
(→Solution) |
||
(One intermediate revision by one other user not shown) | |||
Line 9: | Line 9: | ||
\text{(E) } 105</math> | \text{(E) } 105</math> | ||
− | == Solution | + | == Solution == |
− | What we want to know is for how many <math>n</math> is <cmath>\gcd(n^2+7, n+4) > 1.</cmath> We start by setting <cmath>n+4 \equiv 0 \mod m</cmath> for some arbitrary <math>m</math>. This shows that <math>m</math> evenly divides <math>n+4</math>. Next we want to see under which conditions <math>m</math> also divides <math>n^2 + 7</math>. We know from the previous statement that <cmath>n \equiv -4 \mod m</cmath> and thus <cmath>n^2 \equiv (-4)^2 \equiv 16 \mod m.</cmath> Next we simply add <math>7</math> to get <cmath>n^2 + 7 \equiv 23 \mod m.</cmath> However, we also want <cmath>n^2 + 7 \equiv 0 \mod m</cmath> which leads to <cmath>n^2 + 7\equiv 23 \equiv 0 \mod m</cmath> from the previous statement. | + | What we want to know is for how many <math>n</math> is <cmath>\gcd(n^2+7, n+4) > 1.</cmath> We start by setting <cmath>n+4 \equiv 0 \mod m</cmath> for some arbitrary <math>m</math>. This shows that <math>m</math> evenly divides <math>n+4</math>. Next we want to see under which conditions <math>m</math> also divides <math>n^2 + 7</math>. We know from the previous statement that <cmath>n \equiv -4 \mod m</cmath> and thus <cmath>n^2 \equiv (-4)^2 \equiv 16 \mod m.</cmath> Next we simply add <math>7</math> to get <cmath>n^2 + 7 \equiv 23 \mod m.</cmath> However, we also want <cmath>n^2 + 7 \equiv 0 \mod m</cmath> which leads to <cmath>n^2 + 7\equiv 23 \equiv 0 \mod m</cmath> from the previous statement. From that statement, we get that <math>m</math> divides <math>23</math> evenly. Since <math>23</math> is prime and we're looking for a GCD greater than 1, <math>m</math> must be <math>23</math>. Going back to our original statement, we can set <cmath>n+4=23x</cmath> for some positive integer x, and <cmath>n=23x-4.</cmath> Finally, we must find the largest <math>x</math> such that <cmath>23x-4<1990.</cmath> This is a simple linear inequality for which the answer is <math>x=86</math>, or <math>\fbox{B}</math>. |
== See also == | == See also == |
Latest revision as of 01:24, 9 August 2022
Problem
For how many integers between
and
is the improper fraction
in lowest terms?
Solution
What we want to know is for how many is
We start by setting
for some arbitrary
. This shows that
evenly divides
. Next we want to see under which conditions
also divides
. We know from the previous statement that
and thus
Next we simply add
to get
However, we also want
which leads to
from the previous statement. From that statement, we get that
divides
evenly. Since
is prime and we're looking for a GCD greater than 1,
must be
. Going back to our original statement, we can set
for some positive integer x, and
Finally, we must find the largest
such that
This is a simple linear inequality for which the answer is
, or
.
See also
1990 AHSME (Problems • Answer Key • Resources) | ||
Preceded by Problem 18 |
Followed by Problem 20 | |
1 • 2 • 3 • 4 • 5 • 6 • 7 • 8 • 9 • 10 • 11 • 12 • 13 • 14 • 15 • 16 • 17 • 18 • 19 • 20 • 21 • 22 • 23 • 24 • 25 • 26 • 27 • 28 • 29 • 30 | ||
All AHSME Problems and Solutions |
The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions.