# Divisibility of a sum in terms of the divisibility of summands

Let $d(x) =_{df} \{y ~~|~~ \exists z: (y\cdot z) = x\}$, where $x,y,z \in \mathbb Z^+$. Informally, $d(x)$ is the set of integral factors of $x$. My question is rather elementary: is it true that $(\forall x,y)$:

$d(x + y) = d(x) \cap d(y)$?

If it is, how might we go about proving it? I unpacked the definitions, but can't seem to transform the right hand side in such a way as to obtain the $d(x+y)$ set.

-
Didn't anticipate so many helpful replies. I accepted the one that was offered first. They were all equally helpful to me. Thank you. – Readingtao May 1 '14 at 20:00

This is false. Consider $x=3,y=5$ then $d(3)=\{1,3\}$ and $d(5)=\{1,5\}$ but $d(3+5)=d(8)=\{1,2,4,8\}$.

Other neat examples include $x=y=1$ and more generally, $x=y$ (since $x+x\in d(x+x)\notin d(x)$), and so on.

-
What was I thinking! Thank you very much. – Readingtao May 1 '14 at 19:49
No problem. It's easy to forget the easy examples and focus on the examples we had in mind. – Asaf Karagila May 1 '14 at 19:50

It's true that

$$d(x)\cap d(y) \subset d(x+y)$$

but the inclusion doesn't usually go the other way.

-
After reading Asaf's answer I immediately thought that this is what I was thinking about actually. But now I was trying to prove this one to see if I'm also not mistaken about this. Thank you! – Readingtao May 1 '14 at 19:52
You're the author of the first volumes of What’s Happening in the Mathematical Sciences? – Andreas Caranti May 1 '14 at 19:54
@AndreasCaranti, I am. I'm also the author of Misteaks, and how to find them before the teacher does. – Barry Cipra May 1 '14 at 20:18
@Barry: Is there an edition for teachers which erases their ability for finding mistakes? What happens if you're a student and a teacher at the same time? – Asaf Karagila May 1 '14 at 20:25
Kudos! I enjoyed the What's Happening series, will take a look at Misteaks. – Andreas Caranti May 1 '14 at 20:32

We have $d(x) \cap d(y) = d(\gcd(x, y))$, and of course if $x, y$ are positive integers, then $\gcd(x, y) \le \min(x, y) < x + y$.

-
Thank you. This too is very helpful. – Readingtao May 1 '14 at 19:50
@Readingtao, you're very welcome. – Andreas Caranti May 1 '14 at 19:51