You're on the right track, however:
Looking at your $ S = p_1 ^a \times p_2 ^b$ hypothesis, we want to solve the general equation:
$$(a + \alpha_1 + 1)(b+\alpha_2 + 1 ) Y = (a+\beta_1 + 1 ) ( b+ \beta_2 + 1 ) Z.$$
For $\alpha_1 > \beta_1$, we have $ 1 < \frac{ a +\alpha_1 + 1 } { a + \beta_1 + 1 } \leq \frac{ \alpha_1 + 1 }{\beta_1 + 1 }.$
For $ \alpha_2 < \beta_2$, we have $ \frac{\alpha_2 + 1 } { \beta_2 + 1 } \leq \frac{ b +\alpha_2 + 1 } { b + \beta_2 + 1 } < 1 $.
So, if a solution exists, we require $ \frac{\alpha_2 + 1 } { \beta_2 + 1 } < \frac{Z}{Y} < \frac{ \alpha_1 + 1 }{\beta_1 + 1 }$.
There are clearly counter examples to this constraint, thus the simplistic $ S = p_1 ^a \times p_2 ^b$ isn't sufficient.
In particular, this argument strongly suggests that we want to bound the "leftover term $\frac{Z}{Y}$" very closely to 1, which happens when all of the prime factors are involved.
If you haven't already done this, I strongly suggest showing that an $s$ exists for the small cases $ (n,k) = (2, 3), (4, 3), (12, 18), (6,5), (30, 7), (30, 77)$.
It is from working with these cases that I found the following solution.
There are 3 types of primes to consider:
- Set A: Those that appear more often in $n$ than in $k$.
- Set B: Those that appear more often in $k$ than in $n$.
- Set C: Those that appear equal often in $k$ and $n$. -> These do not matter. We can ignore them (EG Primes that occur in neither).
As you realized, a necessary condition is $ n \not \mid k, k \not \mid n$.
This means that sets $A$, $B$ are non-empty, which is crucial.
As it turns out, the necessary condition is also a sufficient condition (to be shown).
Claim: There exists a $D$ such that for any $d \geq D$, we can find integers $\alpha_i$ such that
$$ \prod_{p_i \in A} \frac{ v_{p_i} (n) + \alpha_i + 1 } { v_{p_i} (k) + \alpha_i + 1 } = \frac{d+1}{d}. $$
Likewise, there exists a $E$ such that for any $ e \geq E$, we can find integers $\beta_j$ such that
$$ \prod_{q_j \in B} \frac{ v_{q_j} (k) + \beta_j + 1 } { v_{q_j} (n) + \beta_j + 1 } = \frac{e+1}{e}. $$
Corollary: Take $d= e = \max(D, E)$ and the corresponding integers.
Then for $s = \prod p_i ^ {\alpha_i} \times \prod q_j^{\beta_j}$, we get that $\sigma(sn) = \sigma(sk)$.
So the condition $ n\not\mid k, k\not\mid n$ is sufficient.
Proof of claim: Try this for yourself. If you're stuck, state what you've tried.
As a cryptic hint, set up a another claim in a similar manner to the claim.
Best Answer
We use the fact $p_1^{\alpha_1}p_2^{\alpha_2}\dots p_n^{\alpha_n}$ has $(\alpha_1+1)(\alpha_2+1)\dots(\alpha_n+1)$ divisors, and check minimum integer for each factorization, the possible factorizations for $24=2\cdot2\cdot2\cdot3$ are the following:
$2\cdot2\cdot2\cdot3$ minimum for this factorization is $2^2\cdot3\cdot5\cdot7=420$
$6\cdot2\cdot2$ minimum is $2^5\cdot3\cdot5=480$
$4\cdot2\cdot3$ minimum is $2^3\cdot3^2\cdot5=360$
$4\cdot 6$ minimum is $2^5\cdot3^3=864$
$12\cdot 2$ minimum is $2^{11}\cdot3>1000$
$8\cdot 3$ minimum is $2^{7}\cdot3^2>1000$
$24$ minimum is $2^{23}>1000000$
the minimum of the numbers in the right is $360$, which is our answer.