See here http://www.mathlinks.ro/Forum/viewtopic.php?search_id=784323867&t=112155&sid=83def756750109c33923a40316d62c68 .

We will prove that $n$ is the power of an odd prime. 1) If possible, let $n$ have $2$ distinct prime divisors. Let $p$ be the smallest (odd) prime dividing $n$. Then we may write $n=p^km$, with $k$ and $m$ positive integers, $m>1$ such that $p\nmid m$. 2) $p$ and $m$ are relatively prime divisors of $n$, so $p+m-1\mid n$. We will show that $p+m-1$ is a power of $p$. Indeed, if $m$ and $p+m-1$ had something in common then a prime divisor of $m$ (say $q$) would divide $p+m-1$, but $m<p+m-1<m+q$, so $p+m-1$ can be caught between $2$ consecutive multiples $q$, impossible. So take $p+m-1=p^a$ for $a$ a positive integer. 3) Again, $p^a$ and $m$ are relatively prime divisors of $n$. Hence $p^a+m-1\mid n$. But $p^a+m-1=2p^a-p$ (by 2). So $2p^a-p\mid n=p^km$, implying $2p^{a-1}-1\mid p^{k-1}m$. As $p$ and $2p^{a-1}-1$ have nothing in common, we have $2p^{a-1}-1\mid m$. 4) Using $m=p^a-p+1$, we get $2p^{a-1}-1\mid p^a-p+1\longrightarrow 2p^{a-1}-1\mid p(2p^{a-1}-1)-2(p^a-p+1)=p-2$. But evidently, $2p^{a-1}-1>p-2$, a contradiction. $\blacksquare$

let $n=P1^L1P2^L2...Ps^Ls$such that $Pi$ for all$i$ is prime and let $Pn>Pn-1>...>P2>P1$ we know that $P1+P2-1$ divides $n$ and easy to see $P1+P2-1=P^r$ such that $P$ is a prime number and we know that $P<P2$ because iff $P=>P2$ so ther exist number $u$ for wich $u$ divised $P1+P2-1$ and so $u$ divised $k$ such that $k=<a-1$ this is Contradiction. so $s=<2$ 1-iff $s=0$ then n=1 2-iff $s=1$ then $n=P^j$ such that 1<j 3-iff $s=2$ then $n=p1^K1.P2^K2$ such that $P2=P1^t-P1+1$

Consider the smallest prime divisor of $n$, $p$. Let $p^{e_1}|n$ with $e_1$ maximal. Then we have $$\frac{n}{p^{e_1}}+p-1 | n$$ Since $p-1$ is relatively prime to $n$, and $\frac{n}{p^{e_1}}$ has all prime divisors of $n$ expect for $p$, $\frac{n}{p^{e_1}}+p-1=p^{e_2}$ with $e_2<e_1$. Next we have that $\frac{n}{p^{e_1}}+p^2-1|n$ if $p^2|n$. Then $\frac{n}{p^{e_1}}+(p-1)(p+1)$. However, since $p-1,p+1$ are both relatively prime to $n$ as $n$ is odd, again we have that $\frac{n}{p^{e_1}}+p^2-1=p^{e_3}$ with $e_1>e_3>e_2$. This means that $p^{e_3}-p^{e_2}=p^2-p$, which is only true for $e_3=2$ and $e_2=1$, or in fact $\frac{n}{p^{e_1}}=1$, implying that $n$ is a power of $p$. If $p^2$ does not divide $n$, then $\frac{n}{p^{e_1}}+p-1=p$ and we have the same result.

Note: If we exclude the condition of being odd, then we also get $6, 12, 24$ and $48$ as solutions!

Wait a minute, I don't see how $6,24,48$ be solutions when $2+3-1$ does not divide $6$,$2^3+3-1$ does not divide $24,48$. So, I would post my solution. We observe that if $p \mid n$ and $v_p(n)=x$ then $\frac{n}{p^x}+p^x-1\mid p^{2x}-p^x$. And $AM-GM$ gives $p^x>\sqrt[4]{n}$. so $n$ can't have more than $3$. distinct prime factors. We consider the following three cases: Case $1$. If $n$ is a prime power. No work to do at all since these are solutions(yay).$\square$ Case $2$ If $n=p^aq^b$ where $p,q$ are distinct primes and $a,b\ge 1$. Assume w.l.o.g $p<q$. $p+q-1\mid n$ and so since $q$ can't $p-1$ we must have $q=p^x-p+1$ for some integer $x\ge 2$(Therefore, $a\ge 2$) Now, $p^2+q-1 \mid n$ and so $p^2+p^x-p$ divides $n$ which means that since $v_p(p^2+p^x-p)=1$, we must have $q \mid p+-1$ and so $p<q\le q+1$ which means $q=3,p=2$. Now, $3=2^x-2+1$ and so $x=2$. Moreover since if $a>2$ then $2^3+3-1$ would divide$n$ giving another prime factor and so $a=2$ and also $b$ can be at most $1$ since otherwise $2+3^2-1 \mid n$ gives another prime divisor. So only $n=12$ works in this case. Case-$3$ If $n=p^aq^br^c$ where $a,b,c\ge 1$. and $p,q,r$ are distinct primes. Assume w.l.o.g. $p<q<r$. Now, $p+qr-1 \mid n$ and since $q,r$ can't divide it so we must have $qr=p^x-p+1$ for some integer $x$. Moreover, $p^x>qr>p^2$ so $x\ge 3$. Now, $p^2+qr-1=p^x-p^2+p=p(p^{x-1}-p+1) \mid n$ and therefore, a prime other than $p$ divides $p^2+qr-1$. Sub case a.) If $r$ divides $p^2+qr-1$. So $r\mid p^2-1$ and this gives $p<q<r\le p+1$. Clearly, a contradiction. Sub case b.) If $q$ divides $p^2+qr-1$. This immediately gives $q=p+1$ and so $p=2,q=3$. Now, $2^3+3-1 \mid n$ and so $r=5$. However, $3+5-1=7 \mid n$. giving another prime divisor a contradiction. So the only positive integers satisfying this are the prime powers and $12$.$\square$.

nice :v

Gotta take this one back...

My solution seems slightly sketchy... Could someone check whether it is correct or not? The answer is all $p^k$ for odd prime $p$ and $k$ a positive integer. To check that these work, note that the factors are $1, p, p^2, ..., p^k$. The pairs not including $1$ aren't relatively prime, and it is clear that the pairs with $1$ invovled work, so all of these satisfy the condition. Now we prove these are the only ones. Consider a number not in that form. Then it contains at least $2$ distinct prime factors. Consider the largest two prime factors, let them be $p$ and $q$ where $p > q$. Then we know that $p+q-1 | n$. Notice that $p+q-1$ cannot be a prime factor of $n$ because it is too large. This means that there exists another prime $r$ where $r<q$ such that $r|p+q-1$, or $q|p+q-1$. The second case is impossible because that would imply $q|p-1$, forcing $q = 2$. For the first case, we can deduce that $r+p-1$ is a factor of $n$, and is composite because $r+p-1 > p$ but $p$ is the largest prime factor. Therefore we can again have a prime $s<r$ such that $s|r+p-1$, or $r|r+p-1$. We can see that because a number can only have a finite amount of prime factors, we will always reach a point where we have a prime factor equivalent $2$. Therefore, numbers not in form $p^k$ are impossible, so we are done. $\blacksquare$

So as always choose $N=p^k m$ with $k \ge 1$ and $\gcd(m,p)=1$ by the fundamental theorem of arithmetic. Now by the condition $p+m-1|n$. Note that:-$\gcd(p+m-1,m)=\gcd(p-1,m)|\gcd(p-1,n)=1$,thus $p+m-1|p^k$ hence $p+m-1=p^l$ for some $l \le k$ Suppose that $k \ge 2$,then $p^2+m-1|n$ and similarly $\gcd(p^2+m-1,m)=\gcd(p^2-1,m)|\gcd(p^2-1,n)=1$ As above,we deduce that $p^2+m-1=p^j$ But we are already done since $m-1=p^j-p^2=p^l-p$ Now since $p^j-p^2=p^l-p=>p^2(p^{j-2}-1)=p(p^{l-1}-1)$,implying $p|p^{l-1}-1$ or $l=1$ with $m=1$,so if $m>2$ then the only solutions are odd powers of primes and clearly by a similar argument $p$ works but $p^2$ doesn't,hence the answer is all odd powers of primes.

What if a=7,b=9 and n=315,a+b-1=15|315,but 315 is not a prime power?? This sum is really meaningless.

Claim: all $n$ such that $n$ is a power of an odd prime works Proof The multiset of factors of $n$ is $\{ 1, p, p^2, ... , p^k\}$ and choosing $(a,b) = (1, p^m)$ for some $1 \leq m \leq k$ gives us $$\begin{align*} a+b-1 &= 1+p^m-1 \\ &= p^m | n \end{align*}$$ Now, it suffices to show all $n$ with more than $2$ odd prime factors don't work. Assume for the sake of contradiction that $n$ does. Let $p, q$ be two distinct prime factors of $n$ and let $(a,b) = (p,q).$ We have $p+q-1|n.$ Claim: There exists some prime $r$ not equal to $p,q$ such that $r|p+q-1.$ Assume FTSOC that there doesn't exist such an $r.$ Then, we must have the $$p+q-1 = \{1, p, q, pq\}$$ as the set of cases. Clearly, the first three cases are impossible. If $p+q-1 = pq$, we have $(p-1)(q-1)=0$, so $p$ or $q$ is $1.$ This is a contradiction. Therefore, our claim is true. By our claim, we have shown that $n$ must have only one odd prime factor. We also showed that all such $n$ with one odd prime factors work. Therefore, all $n$ with one odd prime factor work. $\blacksquare$.

remark

Edit: this is flawed. $p+q-1=p^xq^y$ works

minimal prime divisor.

anantmudgal09 wrote: Wait a minute, I don't see how $6,24,48$ be solutions when $2+3-1$ does not divide $6$,$2^3+3-1$ does not divide $24,48$. So, I would post my solution. We observe that if $p \mid n$ and $v_p(n)=x$ then $\frac{n}{p^x}+p^x-1\mid p^{2x}-p^x$. And $AM-GM$ gives $p^x>\sqrt[4]{n}$. so $n$ can't have more than $3$. distinct prime factors. We consider the following three cases: Case $1$. If $n$ is a prime power. No work to do at all since these are solutions(yay).$\square$ Case $2$ If $n=p^aq^b$ where $p,q$ are distinct primes and $a,b\ge 1$. Assume w.l.o.g $p<q$. $p+q-1\mid n$ and so since $q$ can't $p-1$ we must have $q=p^x-p+1$ for some integer $x\ge 2$(Therefore, $a\ge 2$) Now, $p^2+q-1 \mid n$ and so $p^2+p^x-p$ divides $n$ which means that since $v_p(p^2+p^x-p)=1$, we must have $q \mid p+-1$ and so $p<q\le q+1$ which means $q=3,p=2$. Now, $3=2^x-2+1$ and so $x=2$. Moreover since if $a>2$ then $2^3+3-1$ would divide$n$ giving another prime factor and so $a=2$ and also $b$ can be at most $1$ since otherwise $2+3^2-1 \mid n$ gives another prime divisor. So only $n=12$ works in this case. Case-$3$ If $n=p^aq^br^c$ where $a,b,c\ge 1$. and $p,q,r$ are distinct primes. Assume w.l.o.g. $p<q<r$. Now, $p+qr-1 \mid n$ and since $q,r$ can't divide it so we must have $qr=p^x-p+1$ for some integer $x$. Moreover, $p^x>qr>p^2$ so $x\ge 3$. Now, $p^2+qr-1=p^x-p^2+p=p(p^{x-1}-p+1) \mid n$ and therefore, a prime other than $p$ divides $p^2+qr-1$. Sub case a.) If $r$ divides $p^2+qr-1$. So $r\mid p^2-1$ and this gives $p<q<r\le p+1$. Clearly, a contradiction. Sub case b.) If $q$ divides $p^2+qr-1$. This immediately gives $q=p+1$ and so $p=2,q=3$. Now, $2^3+3-1 \mid n$ and so $r=5$. However, $3+5-1=7 \mid n$. giving another prime divisor a contradiction. So the only positive integers satisfying this are the prime powers and $12$.$\square$. Why n/p^x +p^x -1 | p^2x -p^x . Can u explain, please?

Very cute problem! Let $n=\prod_{k=1}^{t}p_k^{x_k}$ Also let $a=p_1^{x_1}=\min \{p_k^{x_k} | 1 \le k \le t \}$ We choose $a$ and $\frac{n}{a}$ to be our $a,b$. $$a+\frac{n}{a}-1 | n \implies a^2-a+n | an \implies a^2-a+n | a^3-a^2$$ $$\implies n \le a(a-1)^2 < a^3$$ Also $n > a^t$. Therefore we have $$t<3 \implies t \in \{0,1,2\}$$ For $t=0$, we have $n=1$ which is not desired as an answer. For $t=1$, we have $n=p^x$ for odd primes $p$ and positive integer $x$. For $t=2$, we take $n=p^xq^y$ for distinct primes $p,q$. We assume $p<q$. Taking $a,b$ as $p,q$, we see $p+q-1 | n$ Thus $q|p-1$ which is absurd as $p<q$. Hence $p+q-1 = p^z \implies q=p^z-p+1$ Taking $a,b$ as $p^2,q$ we see $p^2+q-1 | n$ Thus $p^z+p^2-p | n$ $\implies p^{z-1}+p-1 | n$ $gcd(p^{z-1}+p-1,p^x)=1$ Hence $p^{z-1}+p-1=q^{\gamma}=(p^z-p+1)^{\gamma}$ Clearly $z>1$(else $q=1$). Checking (mod p) on this equation gives $$-1 \equiv 1 \mod p \implies p|2$$ which is a contradiction to the fact that $p$ is odd. Hence the solution is the set $\boxed{p^m | p \text{ is odd prime }, m \in \mathbb{N}}$

Really cool problem; the natural solution comes from using the condition $n$ odd in a clever manner. The answer is powers of odd primes only, which clearly work. Now, let $p_1 < p_2 < \cdots < p_k$ be the primes that divides $n$. Let $\nu_{p_1}(n) = \alpha$. By the given condition, $p_1+\frac n{p_1^\alpha} - 1$ divides $n$. Observe that by minimality, $p_i \nmid p_1 - 1$ for any $i \geq 2$. Thus, the expression must be a power of $p_1$ less than $\alpha$. If $\alpha = 1$, then $n = p_1^\alpha$, which is a contradiction. Else, we cleverly write $$p_i \nmid p_1^2 - 1 + \frac n{p_1^\alpha},$$ as $p_i \nmid p_1^2 - 1$ in general as well. But now, this implies that $$p_1^2 - p_1 = p_1^{k_1} - p_1^{k_2}$$ for some positive integers $k_1, k_2$. Obviously, $(k_1, k_2) = (2, 1)$ is the only solution, but this yields $n = p_1^\alpha$ again, contradiction.

Assume that $n$ has at least two prime divisor, and let $p$ be the smallest among those and write $n=p^\alpha m$, where $(p,m)=1$. Then $x\coloneq p+m-1\mid n$. Suppose $x$ has a prime divisor $q\mid n$ not equal to $p$, which implies that $q\mid m$. Then we must have $q\mid p-1$, contradicting the minimality of $p$. Therefore, $x$ must be a power of $p$. Then, write $p+m-1=p^\beta$. This forces $p\mid m-1$. However, then $p^\beta+m-1=2p^\beta-p\mid p^\alpha m$ which implies $2p^{\beta-1}-1\mid m=p^\beta-p+1$. But now, $$2p^{\beta-1}-1\mid p(2p^{\beta-1}-1)-2(p^\beta-p+1)=p-2,$$ which is clearly impossible.

Nice problem. Let $p$ be the smallest odd prime factor of $n$ .Let $n = p^{\alpha} m$ where $p \nmid m$ Now note that $p+m-1 \mid n$ so $p+m-1 = p^k d$ where $d$ is some factor of $m$ and $k$ is some natural number less or equal to $\alpha$ Now we claim that $d = 1$ Proof : $d \mid m$ and hence $d \mid p+m-1$ and hence $d \mid p-1$ so $p-1\ge d$ and note that as $d$ is odd (as $n$ is odd ) it has to have some odd prime factor less than $p$ and as $d \mid n$ so it brings contradiction to the minimality of $p$ . Now note that $p+m-1 = p^k$ and so $gcd(p+m-1,m) =1$ and so $p+2m-2 \mid n$ and similarly $p+2m-2 = p^l$ $2p+2m-2 = 2p^k \implies p+2m-2 = p^l \implies p = 2p^k-p^l$ and $p^l \mid p$ as $p > 0 \implies 2p^k > p^l \implies p^k \ge p^l$ and so $l =1= k$ by comparing the powers of $p$ in lhs and rhs and note that $l ,k$ can not be $0$. and so $p+m-1 = p$ and so $m=1$ and hence proved that $n= p^{\alpha}$

Let $n=p^\alpha\cdot k$ with $p$ being the smallest prime divisor of $n$ $$(p,k)=1\hspace{0.2cm} \Rightarrow\hspace{0.2cm} p+k-1\mid n\hspace{0.2cm}\Rightarrow\hspace{0.2cm} p+k-1=p^\theta\cdot k_1\hspace{0.2cm} \Rightarrow\hspace{0.2cm} k_1\mid p+k-1 \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \boxed{k_1\mid p-1\hspace{0.2cm} \text{and} \hspace{0.2cm} k_1\mid n}$$ Which implies $k_1=1$ because the minimality of $p$, so $p+k-1=p^\theta$ $$(p+k-1,k)=1 \hspace{0.2cm}\Rightarrow\hspace{0.2cm} p+2k-2\mid n \hspace{0.2cm}\text{Anagously}\hspace{0.2cm} p+2k-2=p^\gamma$$ so, by $p+k-1=p^\theta$ and $p+2k-2=p^\gamma$ we get $p=2p^\theta-p^\gamma \hspace{0.2cm}\Rightarrow\hspace{0.2cm} \theta=\gamma=1$ so $k=1$ and $\boxed{n=p^\alpha}$

I claim that all positive integer powers of odd primes only work. Indeed, verifying this claim is true. Let $p, q$ be primes that divide an integer $n$ with $p$ the smallest prime dividing $n$. Then observe that $q \equiv 1 \pmod p$ and $p \equiv 1 \pmod q$. However the second congruence would yield $p = 1$, so we only have $q \equiv 1 \pmod p$. Then $q = pk + 1$, for some $k \in \mathbb{Z^+}$. Then $p + q - 1 = p(k + 1) \mid n$, and we must have $k + 1 \geq p$, or else this contradicts the minimality of $p$. Hence $k + 1 = p^a N$, for $N$ is odd and divides $n$ while $p \nmid N$. Then $$\begin{align*} pk + 1 &= p(p^aN - 1) + 1 \\ &= p^{a + 1}N - p + 1 \\ \implies q + p - 1 &= p^{a + 1}N, \text{ and } N \geq q \\ \implies q + p - 1 &= p^{a + 1}N \geq p^{a + 1}q, \end{align*}$$ which is a contradiction for $p, q > 2$. Hence $k + 1 = 1$, so that $q = 1$, and the only prime that divides $n$ is $p$, in particular, $n = p^m$, for some positive integer $m$. $\blacksquare$

We claim that $n$ is any power of an odd prime. We prove these satisfy the conditions. Let $n = p^k$. Since any divisor of $n$ is of the form $p^i$, it will only be coprime to 1. Since, $$p^i + 1 -1 = p^i \mid p^k$$ We prove these satisfy the conditions. Now we prove these are the only ones. We assume for the sake of contradiction that $n = p^{\alpha}m$ where $p$ is the smallest prime divisor of $n$. Since $p$ is coprime to $m$, $$p + m -1 \mid n = p^{\alpha}m$$ $\textbf{Claim 1}$: We claim that $\gcd(p+k(m-1),m) = \gcd(p-k,m) = 1$ for $1\leq k <p$. We know that prime factorisation of $p-k$ contains all the primes $< p$ whereas $m$ conatins all the primes $> p$ because $p$ was assumed to be the smallest prime divisor of $n$. So, our claim follows. From our claim we can say that, $p + m -1 \mid p^{\alpha}$. Now we can write $$\begin{align} p + m -1 = p^{\beta} \text{ where } 1<\beta\leq \alpha \end{align}$$ Since $\gcd(p^{\beta}, m) = 1$ so, $$p^{\beta} + m-1\mid p^{\alpha}m$$ Substituting the value of $p^{\beta}$ we get, $$p + 2(m-1)\mid p^{\alpha}m$$ From our claim, $\gcd(p+2(m-1), m) = 1$, so $$p +2(m+1)\mid p^{\alpha}$$ From equation (1) we get, $$2p^{\beta} - p \mid p^{\alpha}$$ $$2p^{\beta -1} -1\mid p^{\alpha -1}$$ which is a contradiction! Hence, $n$ is any power of an odd prime.

We claim $n$ is the power of an odd prime. Clearly these work. Assume FTSOC $n$ has $\geq 2$ prime factors. Let $p\geq 3$ be the smallest prime factor of $n$. Let $n=:p^km$ for $k,m\in\mathbb{Z}^+$ where $p\nmid m$. Note that $m>1$. Then $m+p-1$ divides $n$. Since $\gcd(m,m+p-1)=\gcd(m,p-1)=1$ by the minimality of $p$, it follows that $m+p-1=p^l$ for a positive integer $2\leq l\leq k$. Since $m+p^k-1=p^k+p^l-p$ divides $n$, it follows that $p^{k-1}+p^{l-1}-1\mid n$. Since $p$ is relatively prime with $p^{k-1}+p^{l-1}-1$, it follows that $p^{k-1}+p^{l-1}-1\mid m=p^l-p+1$. By size reasons, we must have $l=k$. Hence $2p^{k-1}-1\mid p^k-p+1$ so $(2p^{k-1}-1)d=p^k-p+1$. Since $k\geq 2$, taking mod $p$ gives $d\equiv -1\pmod{p}$ so $d\geq p-1$. It follows that $p^k-p+1\geq(p-1)(2p^{k-1}-1)$ so $p\leq 2$, a contradiction. $\square$

anantmudgal09 wrote: Wait a minute, I don't see how $6,24,48$ be solutions when $2+3-1$ does not divide $6$,$2^3+3-1$ does not divide $24,48$. So, I would post my solution. We observe that if $p \mid n$ and $v_p(n)=x$ then $\frac{n}{p^x}+p^x-1\mid p^{2x}-p^x$. And $AM-GM$ gives $p^x>\sqrt[4]{n}$. so $n$ can't have more than $3$. distinct prime factors. We consider the following three cases: Case $1$. If $n$ is a prime power. No work to do at all since these are solutions(yay).$\square$ Case $2$ If $n=p^aq^b$ where $p,q$ are distinct primes and $a,b\ge 1$. Assume w.l.o.g $p<q$. $p+q-1\mid n$ and so since $q$ can't $p-1$ we must have $q=p^x-p+1$ for some integer $x\ge 2$(Therefore, $a\ge 2$) Now, $p^2+q-1 \mid n$ and so $p^2+p^x-p$ divides $n$ which means that since $v_p(p^2+p^x-p)=1$, we must have $q \mid p+-1$ and so $p<q\le q+1$ which means $q=3,p=2$. Now, $3=2^x-2+1$ and so $x=2$. Moreover since if $a>2$ then $2^3+3-1$ would divide$n$ giving another prime factor and so $a=2$ and also $b$ can be at most $1$ since otherwise $2+3^2-1 \mid n$ gives another prime divisor. So only $n=12$ works in this case. Case-$3$ If $n=p^aq^br^c$ where $a,b,c\ge 1$. and $p,q,r$ are distinct primes. Assume w.l.o.g. $p<q<r$. Now, $p+qr-1 \mid n$ and since $q,r$ can't divide it so we must have $qr=p^x-p+1$ for some integer $x$. Moreover, $p^x>qr>p^2$ so $x\ge 3$. Now, $p^2+qr-1=p^x-p^2+p=p(p^{x-1}-p+1) \mid n$ and therefore, a prime other than $p$ divides $p^2+qr-1$. Sub case a.) If $r$ divides $p^2+qr-1$. So $r\mid p^2-1$ and this gives $p<q<r\le p+1$. Clearly, a contradiction. Sub case b.) If $q$ divides $p^2+qr-1$. This immediately gives $q=p+1$ and so $p=2,q=3$. Now, $2^3+3-1 \mid n$ and so $r=5$. However, $3+5-1=7 \mid n$. giving another prime divisor a contradiction. So the only positive integers satisfying this are the prime powers and $12$.$\square$. How did you find that $p^x>\sqrt[4]{n}$ ???

We claim that $n$ is a power of an odd prime, or $n = p^k$ where $p$ is some prime, for some positive integer $k$. Note that this solution works: $p^t+1-1 = p^t|n=p^k$ for $t \le n$ (note that: $(p^t, 1)=1$). FTSOC, assume that $n=p^a m$ where $p$ is the smallest prime divisor of $n$ and $p \nmid m$, where $a$ is some positive integer. Consider $p+m-1|n$. Since $(m, p+m-1) = (m, p-1) = 1$ as $p$ is the smallest prime divisor of $n$, $p+m-1=p^t$ for some integer $t \le a$. Note that: $m=p^t-p+1$. Thus: $m+p^a-1 = p^t+p^a-p|n$ which implies: $p^{t-1}+p^{a-1}-1|n = p^a m \implies p^{t-1}+p^{a-1}-1|m = p^t-p+1$. Due to the size argument: we should have $t=a$ (consider $t \le a-1$ which implies $p^{a-2}+p^{a-1}-1 \ge p^{t-1}+p^{a-1}-1 > p^{a-1}-p+1$ which doesnt satisfy the condition). Thus: $$2 \cdot p^{a-1}-1| p^{a}-p+1.$$ Note that: $p^{a}-p+1 = d \cdot (2 \cdot p^{a-1}-1).$ Considering $\pmod p$ we have: $d \equiv -1 \pmod p$ which implies $d \ge p-1$. Therefore: $p^{a}-p+1 = d \cdot (2 \cdot p^{a-1}-1) \ge (p-1)(2 \cdot p^{a-1}-1)$ which implies $p \le 2$. Thus, we have contradiction.