4
$\begingroup$

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?

3 Answers 3

5

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.

  • 0
    How about if $x=5$ and $y=25$?2011-10-14
1

HINT $\rm\quad (x,\:y)\ |\ (x^2,\:y)\ |\ (x,\:y)^2\! = (x^2,\:x\:y,\:y^2)$

1

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$.