Difference between revisions of "1990 AHSME Problems/Problem 19"
Coolmath2017 (talk | contribs) (→Solution 2) |
Coolmath2017 (talk | contribs) (→Solution 2) |
||
Line 11: | Line 11: | ||
== Solution 1 == | == Solution 1 == | ||
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. Since from that statement <math>23</math> divides <math>m</math> evenly, <math>m</math> must be of the form <math>23x</math>, for some arbitrary integer <math>x</math>. After this, we can set <cmath>n+4=23x</cmath> 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>. | 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. Since from that statement <math>23</math> divides <math>m</math> evenly, <math>m</math> must be of the form <math>23x</math>, for some arbitrary integer <math>x</math>. After this, we can set <cmath>n+4=23x</cmath> 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 == |
Revision as of 10:21, 22 June 2020
Problem
For how many integers between and is the improper fraction in lowest terms?
Solution 1
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. Since from that statement divides evenly, must be of the form , for some arbitrary integer . After this, we can set 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.