I'm struggling to show that the following function on $\mathbb{Z}$ is a metric: specifically, showing the triangle inequality.
Fix an odd prime $p,$ and define $d:\mathbb{Z}\times\mathbb{Z}\rightarrow\mathbb{R}$ by $$d(m,n)=0 {\text{ if }} m-n=0,$$ or as $$d(m,n)=\frac{1}{r+1} {\text{ if }} p^r {\text{ is the largest power of }} p {\text{ which divides }} m-n.$$ In my attempt to show $d(x,z)\leq d(x,y)+d(y,z),$ I took distinct $x,y,z\in\mathbb{Z}$ and supposed that $p^t$ was the largest power of $p$ which divided $x-z,$ so $d(x,z)=\frac{1}{t+1}.$ I tried to write $$p^t\hspace{0.1cm}|\hspace{0.1cm}x-z\implies p^t\hspace{0.1cm}|\hspace{0.1cm}(x-y)+(y-z),$$but this does not necessarily imply that $p^t\hspace{0.1cm}|\hspace{0.1cm}x-y$ and $p^t\hspace{0.1cm}|\hspace{0.1cm}y-z.$
I understand that writing $x-z=(x-y)+(y-z)$ makes the two individual differences smaller and thus a smaller power of $p$ can divide them, resulting in their distance $\frac{1}{r+1}$ to be larger, but I am having trouble making this explicit.
Am I thinking about this the wrong way? Any guidance is appreciated.
Thank you.
Best Answer
I think you're thinking about it wrong. It's not about the size of the difference $n - m$, it's about the highest power of $p$ which divides it. You're right to consider the decomposition $$ x - z = (x - y) + (y - z).$$ The key observation is if $p^r$ divides both $x - y$ and $y - z$ then $p^r$ divides $x - z$. In particular take $p^r$ to be the highest power of $p$ such that $p^r$ divides both $x - y$ and $y - z$. Can you show that $$ d(x, z) \leq \frac{1}{r + 1} \leq d(x, y) + d(y, z) ? $$