[Math] If two numbers are relatively prime, is their sum relatively prime to one of them under certain conditions

elementary-number-theorynumber theory

Let $p$ and $10^x$ be relatively prime, where $x \in \mathbb{N}$, $x > 0$ is some constant, and $p$ is prime, $p > 2$. Are $p + 10^x$ and $10^x$ relatively prime?

This isn't a homework question, but nonetheless if it's not against site etiquette it would be nice if you posted a comment before you answer, so that I can beware of spoilers. I'm stuck.

Thanks.

Best Answer

If two numbers are relatively prime, is their sum relatively prime to one of them under certain conditions?

The sum is relatively prime under all conditions.

Actually for your problem the only two prime factors of $10^x$ are $2,5$. And the only two factors of $p$ is $p$ and $1$. So do either $p,2,5$ divide $p + 10^x$?

But for a MUCH more general and more useful result, read on:

==========

If $W$ and $V$ have no factors (other than $1$) in common. And if $d\ne 1$ is a factor of $W$ then $d|W$ and $d\not \mid V$. So $W+V = d(\frac Wd + \frac Vd)$. $\frac Wd$ is an integer. $\frac Vd$ is not. So $d$ is not a factor of $W+V$.

So $W$ and $W +V$ have no non-zero factors in common.

....

Actually we can take it a step further that $\gcd(W,V) = \gcd(W, W \pm k*V) = \gcd(V, V \pm j*W)$ for any integers $j,k$. (But don't fall into the trap that $\gcd(V, W)= \gcd (kW \pm jV, lW\pm mV)$. That is simply false. Utterly false.)

I'll leave the proof of that as a research project.

Related Question