4
$\begingroup$

I considered an even number $n\geq 10$, where it is divisible by some positive integer $k$.

Also, $k$ divides $\frac{n}{2}$. Then $n = kq\implies k\cdot\frac{q}{2} = \frac{n}{2}$.

Can we say that $q$ is even in this case? Can anyone help to get it theoretically? Thanks a lot for the help.

PS.

From the answer given by Bill, it does not satisfy if we take $n=18,k=3,j=9.$ Kindly help. Let me rectify where I am going wrong. Please help.

$\quad\ \ \ \ \ \ \ \ \ $ If $\,\rm\ 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\,$]

This part is not satisfied.

$\endgroup$
3
  • 2
    $\begingroup$ Regarding the PS, the logical if-and-only-if assertion $3\mid2\iff9\mid6\iff27\mid18$ is vacuously true because all three parts of it, $3\mid2$, $9\mid6$, and $27\mid18$, are false. $\endgroup$ Apr 16, 2019 at 11:08
  • $\begingroup$ I am still unable to grasp it. I think my mind has stopped working :( $\endgroup$
    – monalisa
    Apr 16, 2019 at 11:44
  • 2
    $\begingroup$ It looks like you are under the misimpression that a logical statement of the form $P\iff Q$ is true if and only if $P$ and $Q$ are both true. That's not correct. $P\iff Q$ is also true when $P$ and $Q$ are both false. $\endgroup$ Apr 16, 2019 at 12:01

4 Answers 4

3
$\begingroup$

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).

$\endgroup$
1
  • $\begingroup$ Why the downvote? $\endgroup$
    – TheSimpliFire
    Apr 23, 2019 at 16:44
2
+50
$\begingroup$

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} $

$\endgroup$
7
  • $\begingroup$ $\quad\ \ \ \ \ $ Thus $\large \,\rm\ 2,K\mid N\,\ $ and $\large \rm\,\ \color{#c00}K\ {\LARGE \mid} {\Large \frac{N}{\color{#0a0}2}} \Longrightarrow\ \color{#0a0}2\ {\LARGE \mid} {\Large \frac{N}{\color{#c00}K}} = Q$ $\quad$ $\endgroup$ Apr 12, 2019 at 14:33
  • $\begingroup$ Can you please provide more info about divisor reciprocity. Please $\endgroup$
    – monalisa
    Apr 16, 2019 at 9:30
  • 2
    $\begingroup$ @monalisa $\rm\,P\!\iff\! Q\,$ is true precisely when $\rm P$ and $\rm Q$ have the same truth value, i.e. when they are both true or both false. You chose values where all the divisibilities are false, i.e. $\,\rm 3\mid 2\iff 9\mid 6\iff 27\mid 18.\ $ Generally both divisibilities are equivalent to $\, \rm JK\mid N,\,$ i.e. both are true if $\, \rm JK\mid N,\,$ and both are false if $\, \rm JK\nmid N,\,$ as follows by the chain of $3$ equivalences in my answer. $\endgroup$ Apr 16, 2019 at 14:42
  • 1
    $\begingroup$ @monalisa For example consider when $\,P\!\iff\! Q\ $ is $\ 2\mid a\!\iff\! 2\mid a\!+\!2n$. When $P,Q$ are both true this says $\,a\,$ is even $\iff a\!+\!2n\,$ is even. When $P,Q$ are both false it says $\,a\,$ is odd $\iff a+2n\,$ is odd. They are negations of each other since $\,P\!\iff\! Q\,$ is equivalent to $\,\lnot P\!\iff\! \lnot Q.\,$ Which is more natural (or convenient) depends on the context (e.g. even vs. odd above, i.e. divisible by $2,\,$ or not divisible by $2)\ \ $ $\endgroup$ Apr 16, 2019 at 14:58
  • 1
    $\begingroup$ @monalisa In the prior comment, that $P$ and $Q$ have the same truth value means that $\,a\,$ and $\,a+2n\,$ have the same parity, i.e. either both are divisible by $2$ (both even), or both are not divisible by $2$ (both odd). $\endgroup$ Apr 16, 2019 at 15:06
2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

Yes. Since $k \mid \frac{n}{2}$ then $\frac{n/2}{k} = \frac{q}{2}$ is an integer, so $q$ must have a factor of 2, and by definition is even.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .