Let $d(n)$ be number of prime divisors of $n$. Prove that one can find $k,m$ positive integers for any positive integer $n$ such that $k-m=n$ and $d(k)-d(m)=1$
Problem
Source:
Tags: number theory, prime numbers
25.01.2018 21:03
Do you mean, for any given $n$; one can find such $k,m$, enjoying the conditions? If yes, then, here is a solution: $\bullet$ Case 1 : If $n$ is odd, then, take, $m=n$; and, $k=2n$. Clearly, $d(k)=d(n)+1$, hence, $d(k)-d(m)=1$. $\bullet$ Case 2: If $n$ is even, take, $p$ be the smallest prime, such that, $p\nmid n$. Note that, every prime divisor of $p-1$, must appear in $n$'s representation (otherwise, we would contradict with the minimality of $p$). With this, let, $m=(p-1)n$, and, $k=pn$. Clearly, $$ d(k)=1+d(n),\quad, d(m)=d(n), $$giving the result.
25.01.2018 21:07
grupyorum wrote: Do you mean, for any given $n$; one can find such $k,m$, enjoying the conditions? If yes, then, here is a solution: $\bullet$ Case 1 : If $n$ is odd, then, take, $m=n$; and, $k=2n$. Clearly, $d(k)=d(n)+1$, hence, $d(k)-d(m)=1$. $\bullet$ Case 2: If $n$ is even, take, $p$ be the smallest prime, such that, $p\nmid n$. Note that, every prime divisor of $p-1$, must appear in $n$'s representation (otherwise, we would contradict with the minimality of $p$). With this, let, $m=(p-1)n$, and, $k=pn$. Clearly, $$ d(k)=1+d(n),\quad, d(m)=d(n), $$giving the result. That's correct.