Difference between revisions of "2019 AIME I Problems/Problem 7"

(Solution)
(Solution 6 (Official MAA))
(30 intermediate revisions by 14 users not shown)
Line 1: Line 1:
==Problem 7==
+
==Problem==
There are positive integers <math>x</math> and <math>y</math> that satisfy the system of equations <cmath>\log_{10} x + 2 \log_{10} (\gcd(x,y)) = 60</cmath><cmath>\log_{10} y + 2 \log_{10} (\text{lcm}(x,y)) = 570.</cmath> Let <math>m</math> be the number of (not necessarily distinct) prime factors in the prime factorization of <math>x</math>, and let <math>n</math> be the number of (not necessarily distinct) prime factors in the prime factorization of <math>y</math>. Find <math>3m+2n</math>.
+
There are positive integers <math>x</math> and <math>y</math> that satisfy the system of equations  
 +
<cmath>
 +
\begin{align*}
 +
\log_{10} x + 2 \log_{10} (\text{gcd}(x,y)) &= 60\\
 +
\log_{10} y + 2 \log_{10} (\text{lcm}(x,y)) &= 570.
 +
\end{align*}
 +
</cmath>
 +
Let <math>m</math> be the number of (not necessarily distinct) prime factors in the prime factorization of <math>x</math>, and let <math>n</math> be the number of (not necessarily distinct) prime factors in the prime factorization of <math>y</math>. Find <math>3m+2n</math>.
  
==Solution==
+
==Solution 1==
 
Add the two equations to get that <math>\log x+\log y+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>.
 
Add the two equations to get that <math>\log x+\log y+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>.
 
Then, we use the theorem <math>\log a+\log b=\log ab</math> to get the equation, <math>\log (xy)+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>.
 
Then, we use the theorem <math>\log a+\log b=\log ab</math> to get the equation, <math>\log (xy)+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630</math>.
Line 8: Line 15:
 
This can easily be simplified to <math>\log(xy)=210</math>, or <math>xy = 10^{210}</math>.
 
This can easily be simplified to <math>\log(xy)=210</math>, or <math>xy = 10^{210}</math>.
  
<math>10^{210}</math> can be factored into <math>2^{210} \cdot 5^{210}</math>, and <math>m+n</math> equals to the sum of the exponents of 2 and 5, which is <math>210+210 = 420</math>.
+
<math>10^{210}</math> can be factored into <math>2^{210} \cdot 5^{210}</math>, and <math>m+n</math> equals to the sum of the exponents of <math>2</math> and <math>5</math>, which is <math>210+210 = 420</math>.
 
Multiply by two to get <math>2m +2n</math>, which is <math>840</math>.
 
Multiply by two to get <math>2m +2n</math>, which is <math>840</math>.
Then, use the first equation (<math>\log x + 2\log(\gcd(x,y)) = 60</math>) to show that x has to have lower degrees of 2 and 5 than y. Therefore, making the <math>gcd x</math>. Then, turn the equation into <math>3\log x = 60</math>, which yields <math>\log x = 20</math>, or <math>x = 10^20</math>.
+
Then, use the first equation (<math>\log x + 2\log(\gcd(x,y)) = 60</math>) to show that <math>x</math> has to have lower degrees of <math>2</math> and <math>5</math> than <math>y</math>  (you can also test when <math>x>y</math>, which is a contradiction to the restrains you set before). Therefore, <math>\gcd(x,y)=x</math>. Then, turn the equation into <math>3\log x = 60</math>, which yields <math>\log x = 20</math>, or <math>x = 10^{20}</math>.
Factor this into <math>2^{20} \cdot 5^{20}</math>, and add the two 20's, resulting in m, which is 40.
+
Factor this into <math>2^{20} \cdot 5^{20}</math>, and add the two 20's, resulting in <math>m</math>, which is <math>40</math>.
Add <math>m</math> to <math>2m + 2n</math> (which is 840) to get <math>40+840 = \boxed{880}</math>.
+
Add <math>m</math> to <math>2m + 2n</math> (which is <math>840</math>) to get <math>40+840 = \boxed{880}</math>.
  
==Solution 2 (Crappier Solution)==
+
==Solution 2 (Bashier Solution)==
  
 
First simplifying the first and second equations, we get that  
 
First simplifying the first and second equations, we get that  
Line 23: Line 30:
  
 
Thus, when the two equations are added, we have that
 
Thus, when the two equations are added, we have that
<cmath>\log_{10}(x\cdot y\cdot\text{gcd}\cdot\text{lcm}^2)=630</cmath>
+
<cmath>\log_{10}(x\cdot y\cdot\text{gcd}^2\cdot\text{lcm}^2)=630</cmath>
 
When simplified, this equals  
 
When simplified, this equals  
 
<cmath>\log_{10}(x^3y^3)=630</cmath>
 
<cmath>\log_{10}(x^3y^3)=630</cmath>
Line 34: Line 41:
  
 
Please remember that you should only assume on these math contests because they are timed; this would technically not be a valid solution.
 
Please remember that you should only assume on these math contests because they are timed; this would technically not be a valid solution.
 +
 +
==Solution 3 (Easy Solution)==
 +
Let <math>x=10^a</math> and <math>y=10^b</math> and <math>a<b</math>. Then the given equations become <math>3a=60</math> and <math>3b=570</math>. Therefore, <math>x=10^{20}=2^{20}\cdot5^{20}</math> and <math>y=10^{190}=2^{190}\cdot5^{190}</math>. Our answer is <math>3(20+20)+2(190+190)=\boxed{880}</math>.
 +
 +
==Solution 4 ==
 +
We will use the notation <math>(a, b)</math> for <math>\gcd(a, b)</math> and <math>[a, b]</math> as <math>\text{lcm}(a, b)</math>.
 +
We can start with a similar way to Solution 1. We have, by logarithm properties, <math>\log_{10}{x}+\log_{10}{(x, y)^2}=60</math> or <math>x(x, y)^2=10^{60}</math>. We can do something similar to the second equation and our two equations become <cmath>x(x, y)^2=10^{60}</cmath> <cmath>y[x, y]^2=10^{570}</cmath>Adding the two equations gives us <math>xy(x, y)^2[x, y]^2=10^{630}</math>. Since we know that <math>(a, b)\cdot[a, b]=ab</math>, <math>x^3y^3=10^{630}</math>, or <math>xy=10^{210}</math>. We can express <math>x</math> as <math>2^a5^b</math> and <math>y</math> as <math>2^c5^d</math>. Another way to express <math>(x, y)</math> is now <math>2^{min(a, c)}5^{min(b, d)}</math>, and <math>[x, y]</math> is now <math>2^{max(a, c)}5^{max(b, d)}</math>. We know that <math>x<y</math>, and thus, <math>a<c</math>, and <math>b<d</math>. Our equations for <math>lcm</math> and <math>gcd</math> now become <cmath>2^a5^b(2^a5^a)^2=10^{60}</cmath> or <math>a=b=20</math>. Doing the same for the <math>lcm</math> equation, we have <math>c=d=190</math>, and <math>190+20=210</math>, which satisfies <math>xy=210</math>. Thus, <math>3m+2n=3(20+20)+2(190+190)=\boxed{880}</math>.
 +
~awsomek
 +
 +
==Solution 5==
 +
Let <math>x=d\alpha, y=d\beta, (\alpha, \beta)=1</math>. Simplifying, <math>d^3\alpha=10^{60}, d^3\alpha^2\beta^3=10^{510} \implies \alpha\beta^3 = 10^{510}=2^{510} \cdot 5^{510}</math>. Notice that since <math>\alpha, \beta</math> are coprime, and <math>\alpha < 5^{90}</math>(Prove it yourself !) , <math>\alpha=1, \beta = 10^{170}</math>. Hence, <math>x=10^{20}, y=10^{190}</math> giving the answer <math>\boxed{880}</math>.
 +
 +
(Solution by Prabh1512)
 +
==Solution 6 (Official MAA)==
 +
The two equations are equivalent to <math>x(\gcd(x,y))^2=10^{60}</math> and <math>y(\operatorname{lcm}(x,y))^2=10^{570}</math> respectively. Multiplying corresponding sides of the equations leads to <math>xy(\gcd(x,y)\operatorname{lcm}(x,y))^2=(xy)^3=10^{630}</math>, so <math>xy=10^{210}</math>. It follows that there are nonnegative integers <math>a,\,b,\,c,</math> and <math>d</math> such that <math>(x,y)=(2^a5^b,2^c5^d)</math> with <math>a+c=b+d=210</math>. Furthermore, <cmath>\frac{(\operatorname{lcm}(x,y))^2}{x}=\frac{y(\operatorname{lcm}(x,y))^2}{xy}=\frac{10^{570}}{10^{210}}=10^{360}.</cmath> Thus <math>\max(2a,2c)-a=\max(2b,2d)-b=360.</math> Because neither <math>2a-a</math> nor <math>2b-b</math> can equal <math>360</math> when <math>a+c=b+d=210,</math> it follows that <math>2c-a=2d-b=360</math>. Hence <math>(a,b,c,d)=(20,20,190,190</math>, so the prime factorization of <math>x</math> has <math>20+20=40</math> prime factors, and the prime factorization of <math>y</math> has <math>190+190=380</math> prime factors. The requested sum is <math>3\cdot40+2\cdot380=880.</math>
 +
 +
==Video Solution(Pretty Straightforward) ==
 +
https://www.youtube.com/watch?v=NOLk9-A4eDo
 +
Remember to subscribe!
 +
 +
~North America math Contest Go Go Go
  
 
==See Also==
 
==See Also==
 
{{AIME box|year=2019|n=I|num-b=6|num-a=8}}
 
{{AIME box|year=2019|n=I|num-b=6|num-a=8}}
 +
 +
[[Category:Intermediate Number Theory Problems]]
 
{{MAA Notice}}
 
{{MAA Notice}}

Revision as of 18:01, 14 March 2021

Problem

There are positive integers $x$ and $y$ that satisfy the system of equations \begin{align*} \log_{10} x + 2 \log_{10} (\text{gcd}(x,y)) &= 60\\ \log_{10} y + 2 \log_{10} (\text{lcm}(x,y)) &= 570. \end{align*} Let $m$ be the number of (not necessarily distinct) prime factors in the prime factorization of $x$, and let $n$ be the number of (not necessarily distinct) prime factors in the prime factorization of $y$. Find $3m+2n$.

Solution 1

Add the two equations to get that $\log x+\log y+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630$. Then, we use the theorem $\log a+\log b=\log ab$ to get the equation, $\log (xy)+2(\log(\gcd(x,y))+\log(\text{lcm}(x,y)))=630$. Using the theorem that $\gcd(x,y) \cdot \text{lcm}(x,y)=x\cdot y$, along with the previously mentioned theorem, we can get the equation $3\log(xy)=630$. This can easily be simplified to $\log(xy)=210$, or $xy = 10^{210}$.

$10^{210}$ can be factored into $2^{210} \cdot 5^{210}$, and $m+n$ equals to the sum of the exponents of $2$ and $5$, which is $210+210 = 420$. Multiply by two to get $2m +2n$, which is $840$. Then, use the first equation ($\log x + 2\log(\gcd(x,y)) = 60$) to show that $x$ has to have lower degrees of $2$ and $5$ than $y$ (you can also test when $x>y$, which is a contradiction to the restrains you set before). Therefore, $\gcd(x,y)=x$. Then, turn the equation into $3\log x = 60$, which yields $\log x = 20$, or $x = 10^{20}$. Factor this into $2^{20} \cdot 5^{20}$, and add the two 20's, resulting in $m$, which is $40$. Add $m$ to $2m + 2n$ (which is $840$) to get $40+840 = \boxed{880}$.

Solution 2 (Bashier Solution)

First simplifying the first and second equations, we get that

\[\log_{10}(x\cdot\text{gcd}(x,y)^2)=60\] \[\log_{10}(y\cdot\text{lcm}(x,y)^2)=570\]


Thus, when the two equations are added, we have that \[\log_{10}(x\cdot y\cdot\text{gcd}^2\cdot\text{lcm}^2)=630\] When simplified, this equals \[\log_{10}(x^3y^3)=630\] so this means that \[x^3y^3=10^{630}\] so \[xy=10^{210}.\]

Now, the following cannot be done on a proof contest but let's (intuitively) assume that $x<y$ and $x$ and $y$ are both powers of $10$. This means the first equation would simplify to \[x^3=10^{60}\] and \[y^3=10^{570}.\] Therefore, $x=10^{20}$ and $y=10^{190}$ and if we plug these values back, it works! $10^{20}$ has $20\cdot2=40$ total factors and $10^{190}$ has $190\cdot2=380$ so \[3\cdot 40 + 2\cdot 380 = \boxed{880}.\]

Please remember that you should only assume on these math contests because they are timed; this would technically not be a valid solution.

Solution 3 (Easy Solution)

Let $x=10^a$ and $y=10^b$ and $a<b$. Then the given equations become $3a=60$ and $3b=570$. Therefore, $x=10^{20}=2^{20}\cdot5^{20}$ and $y=10^{190}=2^{190}\cdot5^{190}$. Our answer is $3(20+20)+2(190+190)=\boxed{880}$.

Solution 4

We will use the notation $(a, b)$ for $\gcd(a, b)$ and $[a, b]$ as $\text{lcm}(a, b)$. We can start with a similar way to Solution 1. We have, by logarithm properties, $\log_{10}{x}+\log_{10}{(x, y)^2}=60$ or $x(x, y)^2=10^{60}$. We can do something similar to the second equation and our two equations become \[x(x, y)^2=10^{60}\] \[y[x, y]^2=10^{570}\]Adding the two equations gives us $xy(x, y)^2[x, y]^2=10^{630}$. Since we know that $(a, b)\cdot[a, b]=ab$, $x^3y^3=10^{630}$, or $xy=10^{210}$. We can express $x$ as $2^a5^b$ and $y$ as $2^c5^d$. Another way to express $(x, y)$ is now $2^{min(a, c)}5^{min(b, d)}$, and $[x, y]$ is now $2^{max(a, c)}5^{max(b, d)}$. We know that $x<y$, and thus, $a<c$, and $b<d$. Our equations for $lcm$ and $gcd$ now become \[2^a5^b(2^a5^a)^2=10^{60}\] or $a=b=20$. Doing the same for the $lcm$ equation, we have $c=d=190$, and $190+20=210$, which satisfies $xy=210$. Thus, $3m+2n=3(20+20)+2(190+190)=\boxed{880}$. ~awsomek

Solution 5

Let $x=d\alpha, y=d\beta, (\alpha, \beta)=1$. Simplifying, $d^3\alpha=10^{60}, d^3\alpha^2\beta^3=10^{510} \implies \alpha\beta^3 = 10^{510}=2^{510} \cdot 5^{510}$. Notice that since $\alpha, \beta$ are coprime, and $\alpha < 5^{90}$(Prove it yourself !) , $\alpha=1, \beta = 10^{170}$. Hence, $x=10^{20}, y=10^{190}$ giving the answer $\boxed{880}$.

(Solution by Prabh1512)

Solution 6 (Official MAA)

The two equations are equivalent to $x(\gcd(x,y))^2=10^{60}$ and $y(\operatorname{lcm}(x,y))^2=10^{570}$ respectively. Multiplying corresponding sides of the equations leads to $xy(\gcd(x,y)\operatorname{lcm}(x,y))^2=(xy)^3=10^{630}$, so $xy=10^{210}$. It follows that there are nonnegative integers $a,\,b,\,c,$ and $d$ such that $(x,y)=(2^a5^b,2^c5^d)$ with $a+c=b+d=210$. Furthermore, \[\frac{(\operatorname{lcm}(x,y))^2}{x}=\frac{y(\operatorname{lcm}(x,y))^2}{xy}=\frac{10^{570}}{10^{210}}=10^{360}.\] Thus $\max(2a,2c)-a=\max(2b,2d)-b=360.$ Because neither $2a-a$ nor $2b-b$ can equal $360$ when $a+c=b+d=210,$ it follows that $2c-a=2d-b=360$. Hence $(a,b,c,d)=(20,20,190,190$, so the prime factorization of $x$ has $20+20=40$ prime factors, and the prime factorization of $y$ has $190+190=380$ prime factors. The requested sum is $3\cdot40+2\cdot380=880.$

Video Solution(Pretty Straightforward)

https://www.youtube.com/watch?v=NOLk9-A4eDo Remember to subscribe!

~North America math Contest Go Go Go

See Also

2019 AIME I (ProblemsAnswer KeyResources)
Preceded by
Problem 6
Followed by
Problem 8
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
All AIME Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png