# Assume $d\mid n$ and $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$.

Let $d,n\in\mathbb Z_{>0}$ with $d\mid n$. Let $a\in\mathbb Z$ such that $\gcd(a,d)=1$. Let $t$ be the product of prime numbers that divide $n$, but don’t divide $a$. Show: $\gcd(a+td,n)=1$.

Assume $r\mid a+td$ and $r\mid n$. We want to show that $r=1$. I am trying to show that $r\mid a+td\implies r\mid a$ and $r\mid d$, because this will yield $r=1$.

I'm not sure how to do this. I was thinking of assuming $r\nmid d$, which would hopefully lead to a contradiction, so I would have $r\mid a$. The only thing I can think of, is that we need $r\nmid t+d$. Is this the right way? Any help would be appreciated.

• Hint: Let $p$ be a prime dividing that gcd. Then we know that $p$ divides $n$ so either $p$ divides $a$ or $p$ divides $t$ but not both. – lulu Mar 20 '17 at 14:05
• Which $\gcd$? I'm assuming $\gcd(a+td,n)$ – Sha Vuklia Mar 20 '17 at 14:08
• Yes, that's what I mean. – lulu Mar 20 '17 at 14:09
• @lulu Ah right, I think I got it: Assume $p$ is a prime number that divides $a+td$ and $n$. Either $p\mid a$ or $p\nmid a$. Assume $p\mid a$. Then $p$ is not a factor in $t$. We need that $p\mid d$, however, $\gcd(a,d)=1$, so this contradicts the fact that $p$ is prime. Now assume $p\nmid a$. Therefore $p$ is a factor in $t$. This means that $p\mid td$. But then $p\nmid a+td$. Contradiction. We conclude that no prime number divides $a+td$ and $n$. Therefore $\gcd(a+td,n)=1$. – Sha Vuklia Mar 20 '17 at 14:28
• Looks good to me! – lulu Mar 20 '17 at 14:29