enigma123 wrote:
If x and y are positive integers such that x = 8y + 12, what is the greatest common divisor of x and y?
(1) x = 12u, where u is an integer.
(2) y = 12z, where z is an integer.
\(\left\{ \begin{gathered}
x,y\,\, \geqslant \,\,1\,\,{\text{ints}} \hfill \\
x - 8y = 12\,\,\,\,\,\left( * \right) \hfill \\
\end{gathered} \right.\,\,\,\,\,\,\,\,\,;\,\,\,\,\,\,\,?\,\, = \,\,GCD\left( {x,y} \right)\)
\(\left( 1 \right)\,\,\,x = 12u\,\,,\,\,\,u\,\,\operatorname{int} \,\,\,\,\,\,\mathop \Rightarrow \limits^{\left( * \right)} \,\,\,\,\,\,8y = 12\left( {u - 1} \right)\)
\(\,\left\{ \begin{gathered}
\,{\text{Take}}\,\,u = 3\,\,\,\,\,\,\,\,\,\mathop \Rightarrow \limits^{\left( * \right)} \,\,\,\,\,\,\,\,y = 3\,\,\,\,\, \Rightarrow \,\,\,\,\,\,\left( {x,y} \right) = \left( {12 \cdot 3\,,\,3} \right)\,\,\,\,\,\,\, \Rightarrow \,\,\,\,\,\,? = 3 \hfill \\
\,{\text{Take}}\,\,u = 5\,\,\,\,\,\,\,\,\,\mathop \Rightarrow \limits^{\left( * \right)} \,\,\,\,\,\,\,\,y = 6\,\,\,\,\, \Rightarrow \,\,\,\,\,\,\left( {x,y} \right) = \left( {12 \cdot 5\,,\,6} \right)\,\,\,\,\,\,\, \Rightarrow \,\,\,\,\,\,? = 6\,\, \hfill \\
\end{gathered} \right.\)
\(\left( 2 \right)\,\,\,y = 12z\,\,,\,\,\,z\,\,\operatorname{int} \,\,\,\,\,\,\mathop \Rightarrow \limits^{\left( * \right)} \,\,\,\,\,\,x = 12 + 8 \cdot 12 \cdot z = 12\left( {8z + 1} \right)\,\,\,\,\,\mathop \Rightarrow \limits^{\left( {**} \right)} \,\,\,\,\,\,? = 12\)
\(\left( {**} \right)\,\,\,GCD\,\,\left( {z\,,\,8z + 1} \right) = \,\,k \geqslant 1\,\,\,{\text{int}}\,\,\,\, \Rightarrow \,\,\,\,\,\left\{ \begin{gathered}
\,\frac{z}{k} = {\text{in}}{{\text{t}}_{\text{1}}} \hfill \\
\,\frac{{8z + 1}}{k} = {\operatorname{int} _2}\,\,\,\,\, \hfill \\
\end{gathered} \right. \Rightarrow \,\,\,\,\,\,\,\,\frac{1}{k} = {\operatorname{int} _2} - 8\left( {\frac{z}{k}} \right) = {\operatorname{int} _2} - 8 \cdot {\operatorname{int} _1} = \operatorname{int} \,\,\,\,\,\,\,\mathop \Rightarrow \limits^{k\, \geqslant \,1\,\,\,{\text{int}}} \,\,\,\,\,k = 1\)
This solution follows the notations and rationale taught in the GMATH method.
Regards,
Fabio.
_________________
Fabio Skilnik ::
GMATH method creator (Math for the GMAT)
Our high-level "quant" preparation starts here:
https://gmath.net
close
