Hacker Newsnew | past | comments | ask | show | jobs | submitlogin

Say m contains the prime factor p^i and n contains the prime factor p^j, then m^n will contain p^in and n^m will contain p^jm. For them to be equal we need in = jm or i/j = m/n but for a given solution m/n is constant and the prime factor multiplicity ratio must be equal to that. And that applies to all prime factors, their multiplicities must all have the same constant ratio, therefore the smaller of the two numbers must have smaller multiplicity for all prime factors and therefore divide the larger number. There is probably a simpler way to say this, this feels too complicated.


Focusing on v_x(p), the multiplicity of some prime p in the prime factorization of x:

  m = j p^a → v_m(p) = a

  n = k p^b → v_n(p) = b
p is not a factor of j or k

  m^n = j^n (p^a)^n
      = j^n p^(an)
      = k^m p^(bm)
      = …
      = n^m


  v_{m^n}(p) = an = bm
Note that a=0 iff b=0. This is the case where p is neither a factor of m nor n.

  b/a = m/n >=1
This ratio is the same for all primes, so every prime has:

  v_m(p) >= v_n(p)
so

  n | m
(We didn't need the ratio to be the same, but we did need the ratios to be all greater >= 1)




Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: