Given the binary relation $ \sim $ on $\mathbb N^*$ where $ a \sim b \text{ if and only if } \frac{a}{gcd(a,b)} \text{ has the same parity as } \frac{b}{gcd(a,b)}$ . Prove that $ \sim $ is transitive.
I have defined $p:\mathbb N^* \to \{0,1\}$, $p(n) = \begin{cases} 0, \text{ n is even} \\ 1, \text{n is odd} \end{cases} $
Thus, given $ a \sim b $ and $ b \sim c $, I need to prove that $ a \sim c$ which means $ p\left(\frac{a}{gcd(a,c)}\right) = p\left(\frac{c}{gcd(a,c)}\right)$ . I am stuck here. Does anyone have any idea?
Let $f\colon\mathbb{N}\longrightarrow\mathbb N$ be the function defined by$$f(n)=\text{greatest $k\in\mathbb{Z}_+$ such that }2^k\mid n.$$Then$$\tag{1}a\sim b\iff f(a)=f(b)$$ and therefore $\sim$ is transitive: every binary relation $\sim$ for which there is a function $f$ such that $(1)$ holds is transitive (and, in fact, an equivalence relation).