Say we have two integers, $x$ and $y$. If $\gcd(x,y)=5$, how can we find every value for $\gcd(x^2,y)$? If you can find a list of every value, can you prove that this list is complete?
Tricky GCD problem
3 Answers
Here is something to consider: Can $\gcd(x^2,y)$ be divisible by any primes other than 5? (Note that if $p$ is any prime number, then $p$ divides $x^2$ if and only if $p$ divides $x$.)
Do you think $5^{100000}$ is a possible value for $\gcd(x^2,y)$? Why or why not? If you try to make your intuition precise about this, that should take you the rest of the way.
-
0How about if $x=5$ and $y=25$? – 2011-10-14
HINT $\rm\quad (x,\:y)\ |\ (x^2,\:y)\ |\ (x,\:y)^2\! = (x^2,\:x\:y,\:y^2)$
If $(x,y)=5$, then $5$ is the only common prime in the factorizations of $x$ and $y$. So $5$ has order $1$, (that means it's power in the factorization is $1$) in at least one of the factorizations. If the order were greater in both, then $(x,y)$ would be greater than $5$. If $5$ has order $1$ in $y$, then squaring $x$ is not going to introduce any new factors of $5$ in $y$, so $(x^2,y)=5$ again. If $5$ has order $1$ in $x$, then it has order $2$ in $x^2$. So depending on the order of $5$ in $y$, $(x^2,y)$ could be $5$ or $25$.