A simple doubt in number theory problem.

We are given that

  • $\sf{n=qk}$ as $\sf{k\mid n}$, and

  • $\sf{\frac n2=rk}\implies n=2rk$ as $\sf{k\mid\frac n2}$ for some integers $\sf{q,r}$.

Equating gives $\sf{qk=2rk}$ and thus $\sf{q=2r}$ since $\sf{k\ne0}$. As $\sf{r}$ is an integer, $\sf{q}$ must be divisible by $\sf{2}$ and is thus even.


It seems that you have misunderstood the claim in Bill Dubuque's answer. You are correct that the different (fragment) claim $\sf{j,k\mid n}\implies k\mid\frac nj$ is not necessarily true by itself. Let

  • $\sf n=\prod\limits_{i=1}^n p_i^{a_i}$ where $\sf p_i$ are distinct prime numbers and $\sf a_i$ are non-negative integers,

  • $\sf j=\prod\limits_{i=1}^n p_i^{b_i}$ where $\sf b_i$ are non-negative integers such that for each $\sf i$, $\sf b_i\le a_i$, and

  • $\sf k=\prod\limits_{i=1}^n p_i^{c_i}$ where $\sf c_i$ are non-negative integers such that for each $\sf i$, $\sf c_i\le a_i$.

Then clearly the condition that $\sf j,k\mid n$ is satisfied, since $\sf{\prod\limits_{i=1}^n p_i^{a_i-b_i},\prod\limits_{i=1}^n p_i^{a_i-c_i}\in\Bbb Z^+}$. The statement that $\sf k\mid\frac nj$ means that for some integer $\sf{d}$, $$\sf\prod\limits_{i=1}^n p_i^{a_i-b_i}=d\prod\limits_{i=1}^n p_i^{c_i}\implies d=\prod\limits_{i=1}^n p_i^{a_i-b_i-c_i}$$ but the inequality that $\sf a_i-b_i-c_i\ge 0\implies b_i+c_i\le a_i$ may not always hold.

However, Bill's complete claim is that if $\sf{j,k\mid n}$ then $\sf{ k\mid\frac nj\!\iff\! j\mid\frac nk}$. This means that

  • if $\sf j,k\mid n$ then $\sf k\mid\frac nj$ if $\sf j\mid\frac nk$ (equivalent to: if $\sf j,k\mid n$ and $\sf j\mid\frac nk$ then $\sf k\mid\frac nj$), and

  • if $\sf j,k\mid n$ then $\sf j\mid\frac nk$ if $\sf j\mid\frac nk$ (equivalent to: if $\sf j,k\mid n$ and $\sf k\mid\frac nj$ then $\sf j\mid\frac nk$).

It can be easily proven that these two statements are true, and $\sf jk\mid n$ follows. In general the statement $\sf x\implies y\iff z$ means that $\sf x$ implies $\sf y$ is true if $\sf z$ is true, and that $\sf x$ implies $\sf z$ is true if $\sf y$ is true.

Now you give the example $\sf n=18, k=3, j=9$. This is not a valid counterexample as it in fact satisfies neither $\sf j\mid \frac nk$ (needed for the first bullet point) nor $\sf k\mid \frac nj$ (needed for the second bullet point).


We can. Probably better to start with the second part, though: $\frac{n}{2} = k p$ where $p$ is integer. Therefore $kq = n = k\cdot (2p)$, so $q = 2p$ and therefore $q$ is even.


It's a special case of the below divisor $\rm\color{#c00}{recip}\color{#0a0}{rocity}\ % divisor reciprocity $ (put $\rm\ J = 2).\,$ Here $\rm\, x\mid y\, $ means $\,\rm x$ divides $\rm y$.

$\ \rm Suppose\,\ \ J,K\mid N.\,\ Then \ \rm\ \ \color{#c00}K\ {\LARGE \mid} {\Large \frac{N}{\color{#0a0}J}}\! \!\iff\!\color{#0a0}J\ {\LARGE \mid} {\Large \frac{N}{\color{#c00}K}} \rm\!\!\iff\!\! JK\mid N$

${\bf Proof}\ \ \text{Note the fractions}\ \rm\ (N/J)/K =\rm\, (N/K)/J = N/(KJ)\,$ are equal. Each divisibility above is equivalent to the fraction below it being an integer. $\ $ QED $\ \ $ You have $\,\rm J = 2\,$ so it speciallizes to

$\ \rm Suppose\,\ \ 2,K\mid N.\ $ Then $\,\rm\ \ \color{#c00}K\ {\LARGE \mid} {\Large \frac{N}{\color{#0a0}2}}\! \!\iff\!{\color{#0a0}2\ {\LARGE \mid} \Large \frac{N}{\color{#c00}K}}\!=\!Q $

$\begin{align}\rm\text{Hence, we conclude that }\,\ \ \ &\rm \color{#c00}K\ {\LARGE \mid} { \frac{N}{\color{#0a0}2}}\ \Longrightarrow\ \dfrac{N}K\! =\! Q\,\ is\ even\ \ [this\ question]\\[.8em] &\rm\color{#c00}K\ {\LARGE \nmid} { \frac{N}{\color{#0a0}2}}\ \Longrightarrow\ \dfrac{N}K\! =\! Q\ \,is\ odd\ \ \ [next\ question]\end{align} $