Markov's conjecture on integral necklaces